5完。なんか問題を自分の都合のいいように考えてしまうな。最近競技者になってきたという話を少し前にした気がするが、すっかり普通の人になってしまった。全然悪いことではない。
A - QQ solver
簡単でいいね。気持ちよく実装速度を競うことができる。
B - Caesar Cipher
先頭を見ればどれだけずらすか決まる。
C - Graph Isomorphism
グラフの同一性!?まあ、next_permutationすればいい。どっち向きに変換しても一対一対応はしてるはずなので何も考えなくていい。とはいえ考えてないと不安ではあるが。
D - Weak Takahashi
簡単そう。とはいえ具体的に実装する必要はあり、まあ左上から配るDPが楽そう。DPしながら、'.'のマスについて最大値を更新していく。素早く書いて、WA。壁にも配ってるけど、DPテーブルは0で初期化すれば到達できない場所は壁で阻まれるからいいかと思ってたらその0が成長して大きくなり得るじゃん。壁を通さないように壁に配らないようにしてまたWA。そりゃそうで、そこは関係ない。DPテーブルを-INFで初期化してAC。2個目のWAが意味不明すぎるけど、まあWAの出し方としては悪くない(自分の能力のギリギリを攻めているので)。
E - Rook Path
Kが小さい場合を考えてみるとかなり嫌らしい。ただ、場合分けは書かずにおく。Kが小さいのでDPするだけだ(大きくても行列累乗できそう)。ゴールに注目し、横位置が合っているか、縦位置が合っているかで4通りに分ける。16通りの遷移を考えるのは嫌だなあと思う。まあ、やる。考えやすいところから。4個中最後の1個は全体(それぞれH+W-2通りある)から引けばいい。サンプルが合わない。xが等しい場所が縦に並んでるように勘違いしてたのと、横位置だけ合ってるやつから縦位置だけ合ってるやつへ行けないことに最初気づいてなかったのを直してAC。
F - Simple Operations on Sequence
最初「転倒数を求める能力のあるコードを書く必要があるのか」と思っていたのに、どこかで隣同士でなくても自由にスワップできると思い込んで実装してサンプルが合って提出して半分WAだった。Gと交互に考えていたが、かなり痛い勘違いで、最後まで解ける兆しは見えなかった。
G - Modulo Shortest Path
面白そうだけどさすがに難しいかなあという見た目。頂点1からの最短距離を頂点番号順に求めていくことを考えるが、まあ2乗にはなってしまう。ワーシャルフロイドがはまりそうな見た目でもあり、最後のころはそれで考えていたが、3乗からNを1つならともかく2つ落とすのは厳しいという感じ。