2完。難しいね。やることやれたと思うけど。
いやブログ書くのきっつ（考えたことが多い、疲れている）。2時間ちゃんと使えたことの現れだと思うのでいいことではある。
A - No Attacking
チェスって行き所のない駒の反則あったっけ？ああ、プロモーションがあるのか。必ず他の駒になる必要がある？というところまで考えた。斜め前の駒しか取れないことは忘れていた。
ポーンの前にルークがあるようなケースも最初は考えてしまっている（ルークの利きでそういう配置はできない）。まずルークを置く。N個までは置ける。次にポーン。ルークがA個あるから、ポーンが置ける列はN-A個だけ。そのN-A列について、ルークの横利きは列によらないのでどの列でも状況は同じ。ポーンは1個おきに置けるのでルークはそれを邪魔しないように配置しておく。ポーンを1列に置けるのはfloor((N+1)/2)個が最大で、ルークのない行が少なければその分減る。ルークは都合のいい行に置けるのでそれでOK。13分かかっているとはいえ、いつものA問題と比べてあっけなく解けてちょっと不安だった。
B - Chmax
操作の順番は関係ない。1からNまでの各数について、数が大きくなる操作が何回か続いて最終的にどこで止まるかということ。合流したらそこからは同じ道を辿る。サンプル2のように、iより小さいA_iがあったら0通り（操作で小さくなることはない）。サンプル3を考えてみると、最終的に8になるグループと6になるグループがある。6について考えると、6は6から動かないから、Pのその位置は6以下の数である必要がある。そのすぐ左の6を見ると、これは行き先が6である必要がある（寄り道して6にいくならそいつもAの値が6であるはずだがすぐ左を選んだのでそういうのはない）。6がいくつかあったら、それらは順番に一本道でつながっている。6について見ると、一番右の6以外はPの値が1通りに決まる。じゃあ1個だけある4や5はどうかというと、5なら5以下である必要がある。こうなるともう全部決まりそう。Pの自由度について、いくつかの位置は1通りに決まっていて、他は5以下などの条件が付いている。その、5とかの数値をソートして小さい順に決めていけば答えが求まりそう。もう少し考えると、仮に6の位置より左に6があって6の位置には7があるとすると、これは6に行ったあと止まらないので6になれず矛盾。これも0通り。これで、けっこう早く解けたなと思ったけど、それをコードに落とすのが驚くほど難しく、かなりの時間を使った。
6以下と言いつつ6に来るために6を使うから5以下でないといけないとか考えていたが、6は6に来るために使うので使用済みチェックすれば6以下と考えてよかった。設定が難しく0-indexedに直していいか不安になるが、直す。Aを後ろから見て、A_iの値でvviに振り分ける。iとA_iが同じならグループの始まりとしてチェック。そうでないときA_iがチェックされてなければ0通り。vviを使わずできると思ったけど結局使った。そしたらグループ毎に見て確定したやつをチェックしてこれは累積和にしておく。グループの親は何通りかをvectorに突っ込んでおきこれはソートする。最後、自由度があるところを小さい順に選んで掛け算して答え。たぶんいらないけど同じ数を2回使ったら0通りとか使える数の個数がマイナスになったら0通りとか入れた（考える余裕がない）。
C - Swap on Tree
最初に使う辺を固定したら？被りがある。駒1が最終的にどこに行くか固定したら？道中起こることの種類が多すぎる。パスグラフで考えるとDPできそう。しかし一般の木となるとできない。二乗の木DPっぽいなあとは最初から思ってて、腹決めて部分木の各駒が一瞬でも根の位置に行く場合の数を持ってみるが、更新しようとしたら不可能。そもそも自分の子への辺のうちK個を使うとしてK!通りの順番とどの駒が部分木の根に来た時交換するか交換したあと何通りあるかといった不可能要素が多すぎる。そもそも大きな方針が間違っていそう。
（追記）めちゃくちゃ難しい。使う辺の集合を固定すれば、（その辺だけを残したグラフの）連結成分毎に答えを求めてその積が答え。連結成分内は全ての辺を使っているので、全ての辺を使う場合を考えると、各頂点について直接つながった辺たちをどの順番で使うかと最終的な駒の状態が一対一対応する（らしい）（ある頂点について辺を使う順番が違えば他の辺の順番によらず最終的な駒の状態も違うというのは言われればまあ、順序をどう決めても優先度が一番高い同士両想いの辺が常に存在して使っていけるらしい、順番決めたときに1通りになるのがわからん）。そうなると、全ての辺を使う場合は、各頂点の次数の階乗の積が答えになる。ここからもすぐにはわからなかったが、木DPして各部分木について根に直接つながる辺をいくつ使うかで分けて答えを持っておく。例えば3つ使っていてそこに1頂点を1つの辺でつなげたら答えは4倍になる。使う辺の連結成分が変わっても各頂点独立に計算できるのが感覚になくて混乱した。二乗の木DPではないが、二乗の木DPの計算量でいいので根につながる辺をいくつ使うか全探索して計算すれば楽。ここまで来れば、ある程度解かれているのもなんとなくわかる気はするが、自分が解くのは不可能だった。めちゃくちゃ難しい。
D - Rolling Hash
どんなA（長さNの非負整数列）が与えられても指定区間のどれかでハッシュ値が0になる。そういうのがNoで他はYes。最後の10分だけ考えたけど全くわからない。
（追記）彩色数と聞いたときは「この問題ヤバすぎ！」と思ったけど、解説を読んでいくと非常に素直。mod Pで考えて、Bには逆元があるし、累積和は当然復元できるので、累積和で考えていい。0にBを何回か掛けても0だし、0でないものにBを掛けて0になることもない。LRで辺を張って同じ数をつながないようにして、累積和のN+1個の要素をP色以下で塗れればYes（端は0である必要があるがそうじゃなかったら全体からその数を引けばいい）。P+1色以上必要なら無理（そういうAは存在しない）。これを実装するにあたって、ABC187Fをがっつり復習してからやった。
