ABCDEGの6完。久々の2桁順位。直前までぷよぷよを観ていたし、体感あまり調子がよくなかったけど、知ってる典型と実装で解けてしまったので助かった。考察はけっこういい加減だったと思う。
B - Maritozzo
ん、何この問題名。まあ愚直にやるだけ。Nが小さいので2乗かかってもOK。
C - Neo-lexicographic Ordering
これ好き。変換テーブルを作り変換してソートしてXで戻して出力。簡単そうなのはすぐわかるのに、この流れがすぐには見えないから面白い。
D - Strange Lunchbox
いかにもDPだけど、頭が全く動かなくなった（ここで不調を自覚）のでとにかくコードを書いていく。i個目まで入力を受け取ったときのdp[j][k]を「最初のi個のうち最小で何個選んでたこ焼きj個たい焼きk個にできるか」とする。全然わからないのでとにかく手癖で書き進める。(j, k)の辞書順で大きいほうからやればin-placeでできそう。「以上」なのが難しく、DPの初期値を変えて対応する方法が全く思い浮かばない。ただ、解くだけならできそうではあるので方針を変える。配るDPにする。X以上のケースをdp[X][k]にまとめる（Y以上も同様にする）。0以上X以下の全域から配る必要がある。自分自身へ配ることもあるコードになったが、1足して最小値をとるので影響はない。あまり自信はなかったがAC。in-placeだと値そのままのやつをコピーしなくていいから定数倍だけでなく実装も楽になるんだよね。
（追記）貰うDPでもできると知った。これは慣れない。
E - Moat
図を見ると、お堀ではなく、多角形に囲まれた図形が連結か見ればいいのねとなる（まだ厳密な理解ではない）。とすると高々2^16通りしかない。全列挙して条件を満たすものだけ数えればいい。とりあえず書いてみる。最初DFSを意識して番兵を入れていたが、連結かの判定はUnionFindでできると気づき番兵なしに直す（ハーフマラソン増刊号で番兵を使わなかったのの振り戻しか）。サンプルが全然合わないが、入力をintで受け取っているのにcharだと思って'0'を引いていた。それを直してとりあえず1720が出る。何を余計に数えているのか。自己交差を考えてない。交差してるパターンを検出するか？いや、そもそも穴とかもあるし。囲まれた図形でずっと考えてきたが、そもそもの問題設定はお堀だった。お堀が交差はないし、内部に別のお堀を作ることもない。問題文からもそう読み取れる（あとから考えると、お堀は多角形だと言っているので交差に関しては若干怪しいが）。お堀の内部が連結であることは確認したが、外部が連結であることも確認すればよさそうだと思った。マスに0から15の番号を付けていたが、外部を16として（マスの左上隅の）座標に0や3が含まれていたら外部と連結にする。サンプルはわりと強そうだしこれでサンプルは合ったので提出してAC。これも自信はなかった。
F - Cleaning Robot
Sを1周して元の位置に戻ってくるなら簡単。そうでないとき、1周で描かれる図形を一定ずつずらしながら配置してどれだけ重なるかという話になる。2回や3回で落ちつくならいいけど、でかい輪みたいな図形のときはSの長さに近い回数がかかりシミュレーションできない。かなり難しい。知ってる典型で解けそうなGをやるよりこちらをやりたかったが、順位表を見ていい順位が欲しくてGに行った。
（追記）解説を見て、ABCで想定されているレベルの高さを感じた（上を目指す人が基本を身に付ける場所でしかない）。1回の実行でできる図形を考えて、それをずらしながらK個置く。1回目のゴールと2回目のスタートは重なっているが問題ない。このズレで（十分な回数やって）重なるかどうかは同値関係になるのでmapとかを使って分けておく（ズレと同じ向きの同一直線上にあっても内積のあまりで分ける必要があってWA）。分けたらそれぞれの中で答えを求めて足すだけ。横に1だけずれるのとか簡単なケースを考えるべきだったなあ。1回目と5回目が重なったらそれ以降もずっと重なる（例えば6回目は2回目と重なる）（5回目で初めて重なるとしてもK=2とかだったらK回しか寄与しないことに気づかずWA）。端だけは毎回自分で土地を広げるのでK回。ズレベクトルとの内積の差を、ソートが符号逆かもしれないので絶対値とってから、ズレベクトルの長さの2乗で割って、寄与する回数がわかる。
G - Propagation
平方分割。典型90で見たような問題だ（コンテスト中は調べなかったが083だった）。
昨日の典型について、全ての辺を次数が大きい方に向き付けるという方法もある
— 熨斗袋 (@noshi91) July 4, 2021
このツイートを思い出して（誰のツイートかすら思い出せなかったが）、当時この方針で実装したことも思い出した。普通の平方分割でやるかけっこう迷ったが、こちらで。結果的にシンプルな実装になって時間も節約できたと思う。ある頂点から自分より次数が大きい頂点への辺の個数は、O(sqrt(M))になる（次数が大きければそれより大きいのは少ししかないし、次数が小さければそもそも隣が少ない）。次数が同じものは頂点番号とかで適当に順序付けする。てきとうに書いても全然サンプルが合わない。実装では、次数が小さい頂点への辺も持ってしまったが、よく考えると必要なかった。解説でいう「看板」が必要だった。chminでシンプルに書けると思ったがそうでもないかと思ったが結局シンプルに書けた。次数が大きいのだけ見て最新の看板に自身を書き換えて、その後自身の世代を最新にして隣の次数が大きいのを書き換え、最後に看板を立てる。これも全く自信はなかったけどACだった。
