AtCoder Beginner Contest 172の感想

Twitterに垂れ流すと遡るのが大変なのでブログに書くことにした

100-200-300-0(1)-0-0 で3完600点。

All Submissions - AtCoder Beginner Contest 172

A

atcoder.jp
式をそのまま書く。足し算よりかけ算の方が優先順位が高いのでa + a*a + a*a*aみたいに愚直に書く。

B

atcoder.jp
操作回数の最小値を求めるということは、なるべく操作回数を少なくしたいという事。S[i]とT[i]が同じ時、S[i]を変更する必要はない。逆にS[i]とT[i]が異なるときはS[i]を変更しないと問題の条件を満たせない。
つまりS[i]とT[i]を比較したとき、異なる文字となっているようなiの個数を求めればよい。

C

atcoder.jp
最初stackを書いてそれぞれのtopを見て読むのにかかる時間が短い方を取る愚直解を書いていたが、どちらも同じ時間かかるときにその下に積まれている本によってどちらの机から読めばよいかが変わってくることに気付き一度全消し(10分ロス)。

それぞれの机A, Bについて、積まれた本を上からi冊読んだ時かかる時間を累積和の要領で配列に保存する。
机Aに対して上からi冊読むと仮定すると、机Bに積まれている本のうちあとどれだけ上から読めるかは二分探索で求められる（境界値の扱いに注意）。iを全探索して、読める本の冊数の最大値を求める。

D

atcoder.jp
以下の解法でTLE：
素数をエラトステネスの篩により[O(N\log \log N)]で列挙する。KからNまでの数全てに対して約数を求め、愚直に計算し総和を求める。一つの数に対して約数を求めるのにかかるので、全体としてかかるためTLE。

ここで考えるのをやめた（この時点で600点獲得しており、他の問題を解けると仮定すればDを捨てるデメリットが存在しない）。

E

atcoder.jp
「ではない」という条件より「である」という条件の方が考えやすい、というところから包除原理が見えたが、詳しい解法を考える前にFを覗いた。F問題が解けそうだったのもあり、結局それきりE問題は考察していない。

F

atcoder.jp
いわゆるNimと呼ばれるゲームであり、ゲーム開始時点での石の数のXORをとると勝敗がわかるようになっている。
後者が勝つためには総XORが0である必要がある。また今回はA_1とA_2以外の数は変動しないのでA_3以降の数のXORをXとしておく。するとA_1とA_2の値を1ずつ増減させて実際にXORを取りXと一致するか全探索することを思いつくがA_i<10^12なので間に合わない。ところでA_1とA_2に操作を加えても総和は変わらないのでA_1+A_2をSとする。すると
P xor Q = X
P + Q = S
という式を満たすP, Qを求める問題となる（ほかにも大小関係などの条件はあるが省略）。イメージとしては、A_1,A_2がどんな値であるかは一旦忘れて条件を満たす数をある程度絞れないか考える感じ。あとはbitごとに独立に考えるのがXORの定石で…

というところでコンテストが終了した。DとFは解けそうで、Eはなにかめんどくさそうなオーラを感じる。