イップス的な。
result:ooooox--(65分(60分+1WA))
perf:1639(1921->1896)
■A - QQ solver
stringでもらう
■B - Caesar Cipher
全部の差分(mod26)が等しければok
■C - Graph Isomorphism
next_permutationをすべて試す。
■D - Weak Takahashi
とても単純なbfs
■E - Rook Path
元マス、元マスと同じ列、元マスと同じ行、その他で分ける
■F - Simple Operations on Sequence
誤読。。。
入れ替えは隣り合った要素しかできない。
典型的なO(n^3)のdpだと思うも誤読していました。
結局やることはただのbitdp
dp[i]:=前からのpopcount(i)まで決め、使った集合がi
として遷移は
dp[i + 2^j ]:=dp[i] + x * abs(a[j]-b[popcount(i)]) + y*(iの中でjより上位のビットが立っている数)
■G - Modulo Shortest Path
これ賢いね。
modの成約がなければ
数直線上に
i->-a[i],b[i]->iの辺を貼ったグラフを作って
0->n-1の最短距離をダイクストラなどで求めればいい。
modの成約をどう扱うか。これは数直線を丸めてしまえばよい。
一方通行の環状線上に、一方通行のコスト0のショートカットがn個あって
ショートカット0->ショートカットn-1への最短距離
■H - King's Tour
とりあえず小さい場合を考える。
2*nの形の構築はうまくやれば可能。
(n,m)->(2,l)にしたい
左上から左下か右上に向かって疾走することで
一行か一列減らせる
疾走する方向は、疾走したとこと、新しく左上になるところがゴールでないこと。
n.m>=3ならどっちかに疾走できる。
