各問題

A - Connection and Disconnection

想定解とは違う変な解き方をしてしまったようです。以下、自分の考察です。

まず、S単体で変更箇所がいくつあるかを探します。言うまでもなく、変更が必要な箇所は同じ文字が連続している箇所です。

次に、Sを二つ連結して同じことをします。接合部分が違う文字（Sの最初と最後が違う文字）なら最初に出した回数かけるKで終わりですが、同じ文字（Sの最初と最後が同じ文字）だった場合に連続箇所が「ずれる」ことがあるためです。例えばaaaの場合、K=1なら1回ですが、K=2のaaaaaaなら3回になります。直感的に（おい）、以下繰り返しになるだろう、つまり上記の例だと1+2+1+2+...になるだろうと踏んで、コードを書いて提出したところ、最後の一つがWAになってしまいました。

必死でコーナーケースを探したところ、abaみたいなのはK-1が正解であり、上記のロジックでは拾えないことがわかったのですが、それをうまく吸収することができず、仕方無しにメチャクチャな場合分け（SSSSの場合の回数を求めて、SSの倍になっているかいないかで判断する）を書いて無理やり通しました・・・。

B - Graph Partition

結論からいうと、すべての頂点を起点にBFSで各頂点に集合番号を振っていって、矛盾が発生すれば-1を出力し、矛盾が発生しなければ求めた集合の個数のうち最大のものを出力すればいいです。

自分は最初BFSではなく脳死で再帰関数を書いて時間を溶かしてしまい、その後、勝手読みで入次数が最小の頂点を起点にすれば最大が求まると思い込み、提出したところでWAをもらい、全探索でいいじゃないかと気づき修正したところ修正漏れがあってもう一つWAをもらってしまいました。

また、最初、最大値という条件を見落として、例3がなんで4になるん？？？ってずっと悩んでいたのはここだけの秘密です。on_

あと、二部グラフうんぬんというのは問題をみた瞬間わかりましたが、二部グラフに関する実装はまだ勉強していないため気づかなかったことにしました（おい

C - Division by Two with Something

1を引いて2で割るという操作は、右に一つシフトすることと同値、2で割って2N−1を足すという操作は右に一つシフトして最上位に1を立てるのと同値です。それを元にシミュレートすると、通常は操作に2N回かかることがわかりました。また、1010101のように1と0が交互に出現するものは2回で終わることもわかりました。

とりあえずその方針で実装していたのですが、ぎりぎり間に合わず・・・。コンテストが終わってから実装ができましたが、うまくいく例といかない例があったので、結局ダメでした。

結局のところ、考察が中途半端だったようで、editorialやYouTube解説によると、2N回かからないものが単純に一つずつ交互だけじゃなくて、周期性がある場合にも発生する、ということのようです。