Codeforces Round #564 (Div. 2)
あちゃ
A. Nauuo and Votes
やるだけです。丁寧に場合分けしましょう
B. Nauuo and Chess
問題：n個のコマをm*mのマスに置く。任意の2つの駒のマンハッタン距離が番号の差より大きくならなければならない。最小のｍを求めよ
考察：
かなり天才用問題だと思います。
1つ前の駒の1つ隣が良い。
2つ以上前の駒に近づく方向は良くない。
この2つから
oox
xoo
xxo
このようなxが駒oが空きになるような配置がよさそうです。
m=(n+2)/2で構築すればよいです。
C. Nauuo and Cards
問題：1からnまで書かれたカードがn枚、0がn枚ある。はじめ手札がn枚あり、以下の操作をして山札を上から順に1～nで並べたい。操作回数を最小化せよ
操作：手札の好きな1枚を下にいれる。上から1枚引く
考察：
1から順にしたから挿入していけば良さそうです。
この時あるカードiが山札にあるとき、それを引いてからn-i+1回挿入します。
つまり、全てのiでこの回数を調べて、ボトルネックになるところが最小回数です。
ここで山札の下のほうが既に1～kで並んでいることがあります。
このときk+1～nが1~n-k回目までに手に入れば、上のやり方より回数を減らせます。
丁寧に調べればよいです。
こういう場合分け頑張って知らべていく問題は苦手です…
バグ量産して最後のほうにようやく通せました。怖すぎる。
D. Nauuo and Circle
問題：n頂点の木がある。ある円状に頂点をある順列で置く。枝が交差しないような順列はいくつあるか求めよ。
考察：
ケースがマジで少なくてヒントが少ないです。
円のどこにおいてもみたいなところはあまり考えなくてよいです。見やすく等間隔とかで考えましょう。
まず高校数学を思い出すと1を固定することになります。
木の1を固定するといえば根付き木なので構築しておきます
ある頂点vの子になる部分木がk個あるとします。
このとき同じ部分木に含まれる頂点は、その中で順列を作ります。
Examples1では
1の部分木に(2，4)と(3)があります。
2，3，4という並びになると1-3と2-4が交差します。
24の並びと3の並びが考えられます。また24と3は入れ替わっても構いません。
まとめると1から出る枝は(1から出る枝)！通り
2から出る枝は2！通りになります。
これは根付き木を構築するdfsの中で求まるのでO(N)です。
これは1を固定しているので、円状に回してn通りをかければ答えになります。
E1. Nauuo and Pictures (easy version)
問題：1からnに重みがついていて、各操作で重み付き確率で1つ選ぶ
操作：選んだ数字が好きなら重みを+1、嫌いなら-1する
m回操作したあとの各数字の重みの期待値を求めよ
わからーーん解説読みます。
感想
1:31まで2完でまた事故かと思って焦ってました。
そこからCD通せたのアツかったですね。順位もいい感じでした
Cで沼ってなければシンプルにもうちょい高かったので、短期の目標はそういう感じになりそうです。
Eは*2500なんですけど、ほぼ考察が伸びず、まだまだ実力不足に感じました。
長期的な目標はコンテスト中にこの難易度を通すことになりそうです。
ばーい
