第一回日本最強プログラマー学生選手権-予選- D - Classified
2部グラフとか知らね〜って人のための記事が書けたらいいなという記事。
一番大事なところぼかしてない？みたいな感じだけどまぁ雰囲気だけでも。
出来れば実際に紙用意して同じように実験を書いてほしい。色を何色か用意しておくのと、図形はある程度大きく書くといいと思う。
解法（というか考察の仕方？）
まず紙で手実験をします。多分ほとんどの人はしてると思いますが、解法が思い浮かばないうちはN=3~6くらいは手で色々やってみるべきです。実験コードを書くのもいいと思いますが、今回のは実験コードを書くのが比較的大変な部類ですし手でやることで発見出来ることも多いです。ただ実験コードは書いてしまえば手では大変な大きめのNに対してもある程度対応出来るので一長一短です。
以下、N頂点のグラフは時計回りに1,2,...,Nと頂点に番号がついてるとします。頂点N+kは頂点kのことを表します。
実験をするとおそらく"奇数長の閉路が出来ないようにしたい"と感じると思います。あと各Nに対する好感度が"4>>6>>3>5"くらいの感じになると思います。N自体が奇数だとそもそもムカつくのはまぁ当然として、N=6の時は気持ちよく(i,i+1)の辺、(i,i+3)の辺をレベル1にした後気づくと残りの辺が憎きN=3の形2つになっているのでムカつきます。僕はムカつきました。三角形はNが奇数なので。逆にN=4は好きになりました。ばってんをレベル2認定するときの心地よさね。
N=6までやってもむかつきしか生まれなかったのでもう少しだけ実験をします。N=7は奇数なのでむかつきます。N=8をやると嬉しくなります。ただ僕は正八角形を紙に綺麗に書けないのでちょっとむかつきました。N=8の何が嬉しいかと言うと、(i,i+1)、(i,i+3)の辺をレベル1にした後残りの辺が大好きN=4の形2つをしてるんですよね。結局答えはN=6の時と同じ最大レベル3なんですが断然N=8の方が好感度高いです。
ここでN=6とN=8の何が好感度を分けたかを考えます。偶数長閉路をいい感じに作った後の残り辺とは何か見て見ます。これは実験用紙をグッと睨むと(i,i+2)、(i,i+4)といった偶数刻みの辺だということが（簡単なイメージ的証明も込みで）すぐにわかります。
そうすると残る辺たちがN/2バージョンになることがわかり、N=8の時4の形が、N=6の時3の形が残った理由がわかります。（なんとなくわかってた人もいると思いますが）残るN/2バージョンは偶数に角を持つものと奇数に角を持つものが1つずつです。
そうすると次はN=16の時が嬉しいだろうというのはすぐに想像が付きます。少なくともN=16の時は最大レベル4で出来ることはすぐにわかりますし、これがとても無駄のない感じに出来てる気分にもなれます。
というわけでN=2^kの時が最大レベルkで抑えられることに加えて、これが最大レベルkによって押さえられるNの上限値であることを仮定してしまいます（は？）。競技プログラミングは時にはフィーリングに身をまかせることも大事です。ACが証明なのです。
あとは簡単で、Nに対してN<=2^kを満たす最小のkを取ってきたら、2^kに対してグラフを作ってあげればいいのです（最大レベルk-1ではN=2^(k-1)までしか作れないと仮定した以上最大レベルはk以上で、最大レベルkでの作り方はN=2^kのを知っているので)
コード
解説と違い0-indexedで解いてます。
7行目のline(u,v,level)が辺u-vをlevelレベルにします。同じ辺を2回塗らない方法としてループの添字に気を使う代わりに一回塗ってる場合はすぐにループを終わらせる形式にしています。（10,16行目）（ちなみに何も考えず雑に2回以上塗るようにするとTLEします）
13行目のf(s,M,d,cnt)は頂点sを通り(i,i+d)を1辺とするN=Mのパターンをレベルcntにする関数です。
18,19行目が、N=8の場合からN=4の場合を2つ見つけるアレです。
あとは注意点として、ansのサイズは500ではなく512を超えるようにしましょう（2^kの最大値が512なので）
