精進バチャ1600-2200 #1 メモ

https://kenkoooo.com/atcoder/#/contest/show/01389bb5-a825-4c1a-8958-eb237c1c1d70
生活リズムを壊さないで恒常的に競プロの時間を取りつづけましょう

A - だれじゃ

それぞれの文字の数が一致しているかどうかで $2$ つの文字のアナグラムが同じかどうか判断できる。長さ $K$ と決まっているので、尺取りで見ていくと高速。 set> みたいなのを使ってその時の文字の数の情報を入れていく。共通部分を持ってはいけないので $K$ 文字分 setに入れるのを遅くして、判断すると処理が出来る。

B - All Your Paths are Different Lengths

例えば $L$ が偶数のときのことを考える。
このときにノード $1$ からノード $2$ へ $2$ つエッジを張る。
具体的には、コストがそれぞれ、 $0, L/2$ のエッジを張る。
こうすることで、次のノードについて、 $L/2$ についての問題を考えることで、重複なくパスを作る事が出来る。( $0$ を通った場合、 $0,1, \cdots, L/2-1$ , を通ることになり、 $L/2$ を通った場合 $L/2, L/2+1, \cdots, L-1$ を通ることになり、キレイに分断する)

ただ、 $L$ が奇数の場合は余りが $1$ つどうしてもでてしまう。
そこで、このように辺を張る。

ノード $1$ からノード $2$ へコスト $0$ の辺を張る
ノード $1$ からノード $2$ へコスト $\lfloor L/2 \rfloor$ の辺を張る
ノード $1$ からノード $N$ へコスト $L-1$ の辺を張る。

最後の一つは直接最後に貼ってしまえば良いということである。

そうしたら次はノード $2$ からノード $3$ へ $\lfloor L/2 \rfloor$ についての問題を解く。
これも偶数か奇数かで貼り方を分けてやる。

これを繰り返していくと、エッジの数は $60$ 以内に収まり、 $N \leq 20$ にもなる。

解説解の下位bit押さえてやっていく方法で必要なところだけ分裂させるのも面白い。

C - オレンジグラフ

これは一つの事実に気づくと問題がかなり簡単になる。
「奇数長の閉路を含まないグラフは二部グラフ化できる」ということである。
すると、どっちを左側にするか右側にするかを決めたら( 左右は区別できないので $2^{N-1}$ 通り) 、一意に塗り方が定まる。というのも、側が異なる辺を無造作につなげるだけでいいからである。
そのため、 $2^{N-1}$ 通り全て試す。
このときに決めた割り振りが矛盾する場合は、全部辺を繋ぎ終えた時に連結グラフになっていない。そのような偶奇で全ノードをつなげる手立てがなかったことになるからだ。
矛盾のないものを数えると答えになって正答する。