2011-10-08 2011-10-08 ■ [GCJ]Google Code Jam Japan 2011 決勝 19:59 A 最初、角度可変で最適な配置を求める問題だと誤読して「いやそれ無理ゲーでしょ」と焦る 読み直したら等間隔だった。よかった 直感では、どうせソートして順番に使うんじゃないの？ という気がする 少し考えてみると、たとえば a>b>c のとき ab+bc+cd+da > ac+cb+bd+da なので、大きいの同士を組み合わせるのが最適 JAG合宿の魔法少女の問題 http://atcoder.jp/problem/detail/111 が頭にあったので、それと同じように上下どちらにくっつけていくかをDPした Greedyでもよかったみたい B 栗まんじゅう問題が思い起こされる設定 とりあえずフェルマーの小定理方面を考えてみる Cが素数ではないとかAとCが互いに素じゃないとかいろいろ難しそう Cを素数のべき乗に分解してそれぞれで解いてから中国剰余定理で合成すればいい！ とか思ってたけど的外れな方針だった 剰余がループするとかその辺の発想もわずかにはあったが発展させられなかった 最後にsmall狙いでBigInteger使って愚直なコードを書いた べき乗を自分で実装したらスタックオーバーフローしたので慌ててBigInteger#modpow()メソッドに変えたら大丈夫だった。流石GCJの数論は解けたためしがない C smallは10文字なのでパターンにどの文字を残すか2^10通り全部試せば良い ちょっと背徳感あるがJavaのregexライブラリ使うとかなり実装が楽 問題文に「あなたの挑戦は（中略）片方だけにマッチする最短のパターンを求めること」とあったので、AにマッチしてBにマッチしない場合とその逆との両方を考えないといけないと誤読 無駄にclarを投げてしまった 誤読に気づいて直したら正解 軽く解説聞いた感じではlargeをやるにはまだ実力が足りなそう D smallは全探索書くだけだ 書いた。通った。ちょっとバグったけどまあ問題なし。 なんでこれ11点もあるの… 正解者数が少ないのは点数が高くて手を出すのためらった人が多いからかなあ E 読んだだけ smallは実装メイン？ 結果As+Al+Bs+Cs+Ds 42pts 14位やっぱり賞金には少し足りなかったけどまずまず
