終了後「これはよくない」と叫んでいたが...
経過
A
偶奇をカウントしておわり。なんか異様に時間がかかった(358ms)、なんでかよくわからん...
B
0-indexedで19桁目から順に、1ならスルー、0なら2^(i+1)-1とXORを取る。取った後、2^20-1になっていれば終わり、そうでなければ+1して続行。
意外と解くのに時間がかかった...
C
lcm(a+k,b+k)を最小にするkを求める(同じ値なら最小のk). lcm(a+k,b+k)=(a+k)*(b+k)/gcd(b-a,a+k)なので、分母のgcdをfixしたときkが最小なものを考えたい。なので、b-aの約数dを列挙し、各dに対しd|a+kとなる最小のkが候補となる。候補はdの約数の個数くらいしかないので、素直にlcm同士を比較して間に合う。
頭を使わないことを意識するとよさそう。a=bは最初に除外しておくこと。
D
トリエ木とか知りません先生。Wikiを見たらなんか解けた。最大マッチングとか仰々しいけど、実際は「前から奇数個見た時何種類あるか」の合計が答えとなる。これは前からdpしていくとすぐ求まる。ただし、括弧の個数に制約があるのに注意すること。
E
オイラー路問題に帰着したのだが、そこから書き切れなかった雑魚。座標圧縮しないといけないのがまず面倒で、そのあとオイラー路が復元できなかった (悲しいね)。判定問題なら解けたのになぁ。
座圧はライブラリ持ってたが、オイラー路復元は持ってなかった () ちなみにDFSでいいっぽい。ググってそれを見たのが5分前、そこからは書けんなぁ。悲しい。
F
見てません。
結果・感想
4完。それなりに満足だけど、やっぱEできなかったのが残念過ぎる。本当に勿体ない。
Codeforcesは考察パートが少な目で、素直な問題が多い印象。たくさん解けると楽しいので、Atcoderより楽しいです。数オリ勢とは思えない感想だな!
終了直後はEができず萎えていたが、その後に順位表を見ると、なんかしらんが順位が高い。実はCがネックだった説があり、数オリやってて良かったね感が出た。ちなみに2017年のJMO本選に、似たネタの問題があります (似てるというだけ)。Dも「トリエとか知らんし」ってみんな思った説。Wikiをみて「こんなん簡単に計算できんと問題としてあかんやろ」と思ったらできた。問題はナメてかかるに尽きるな!
今回も無事system testを通過し、結果53位(unofficial 89位)、レートは1829+143=1972で、なんと紫色になりました!こどふぉさん過大評価すぎちゃう?まあええわ、素直にうれしい。さらに上を目指すには、簡単な問題をもっと早く書くのと、Eみたいな取りこぼしを無いようにすればよさそう。まだセグメント木が必要な場所にすら行ってないし。
ひとまず、いろいろライブラリと知識を整理せなあかんね。もう少し強くなれば橙、加えてAtcoder黄色も見えてくると思う。