AtCoder Beginner Contest 206 反省

4連続で温まっていたが今回は冷えた。単独writer回なので仕方ない（？）

典型90を今週は30問近く解いてコンテスト練習をしなかったのだが、実装のミスは少なかったが直観が鈍っていたような感じだった

結果を鑑みて

1500(1) 64:47

405位となった。Dで手こずり、Eで手こずり、Fは解けなかった。

来週月曜まではやや忙しいことがあってまたスランプの入り口に立っているのではないかと危惧している

A - Maxi-Buying

100倍しておけばmath.floor()を使わないでも解ける。

解けるがこわいのでちゃんと境界値は試した。

B - Savings

パッと見て思いついたのが二分探索だったので二分探索した。

コードを書いている途中で全探索が可能なことに気付いた。大してかかる時間は変わらないのでOK

C - Swappable

同じ数をまとめておく余事象的数え上げで良い。

解いて出したあたりで順位表を見た。100位を切っており、良いスピードだった。ここまでは......

D - KAIBUNsyo

貪慾法かなと思っていた。dpするには制約がきつすぎる。

端から順に見ていって数字を入れ替えるなら常に２択だし、選び方によっては手数がかかりすぎたりする。寄与を考えるとか後から保証するやつは難しそう。

困りまくって端から貪欲書こうとして、数字の書き換えの管理をUnionFindでやるとうまくいくことに気付き、UnionFind使うんだったらひょっとしたら連結成分分解がキーで、貪欲は関係なくUnionFindだけで解けるのではないかと直感した。

結局、何も証明していないがUFを投げたら通った。メタ読みに救われた。

ここで時間をかけまくって700位くらいになった　たまげた......

E - Divide Both

題意を理解しようとしてみると、互いに素でないx, yのペア(x, y)であってどちらももう一方の約数ではないものを数え上げよという問題であることがわかる。ここまではすぐわかったが、そこから難航した。

余事象を用いて問題を切り分けると、計算量は以下のようになることが予想できた。

全体ペア集合のサイズ計算 O(1)

一方がもう一方の約数であるような(x, y)の個数 O*1

互いに素なペアの個数 O(?)

互いに素なペアの個数を求められればよくて、これはいかにも典型問題っぽいので number of coprime pairs みたいな文言でぐぐるとhttps://codeforces.com/blog/entry/65229…がみつかった。

メビウス関数で区間coprime pairsを計算するのは初めてだったのでバグらせたが、なんとか通すことができた。

この時点で350位くらいだった。

F - Interval Game 2

制約はヒントだったのだが、制約から連想したのは掃き出し法だった。そこから、区間というアイデアを捨ててグラフにする方向で進んだ結果、解くことはできなかった。grundy数を絡めれば Green Hackenbush に似た感じになることに気付いてどうにかならんかと考えていた（木ではないのでより難しいバージョンになる）

ワーシャルフロイド嘘解法を書いて出したが、当然WA

そのままコンテストは終わった。

総括

検索ムーブは結構よくなってきている。しかし今回は直観がうまく働かなかった。素因数・約数系の包除が苦手気味なのが今回のコンテストに響いた部分もあった。

典型90やるのもいいがコンディションの確認・向上のためにもコンテスト練習はしたほうがよさそう。

*1:R-L)log(R-L