Takahashi を探したけど、制約を読めば T を数えるだけでも良かったらしい。他の人の提出で知った。そうか、手の抜き方を見習わないといけないな。無駄にコンピューティングパワーを使ってしまった。■B 問題「Couples」。正規表現の先読みでやったけど、結構複雑で罠もあるパターンになったので(/\b(\d+)(?= \d+ \1\b)/)、普通に Array.each_cons(3).count{...} でやるのが良かった。■C 問題「Tile Distance 2」。数え方が ABC353-F Tile Distance と同じ。斜めを数えてから縦と横を数える。横移動のコスト計算が難しかった。目的地がタイルの右側か左側か判別してから、右と左のどちらから移動してくるのか場合分けをした。■D 問題「Avoid K Palindrome」。ABCDEF で一番難しかった。えっとね、まず否定で良い文字列を定義するのをやめてほしい(わがまま)。かなり長いあいだ勘違いしていた。何を数えたらいいのかまだわかっていない。長さ K の枠の中について回文があるとかないとかを数えるとするじゃない、でも枠の外を数えることができない。重複を省いてどうやって数えられるのか。■E 問題「Water Tank」。特別なデータ構造はいらない。スタックが１つと数を１つ覚えておくだけで答えが出せる。こういう単純な道具をこねこねする問題は好きだけど、前回の D 問題が灰 diff だったことを考えると、緑 diff どころか茶 diff があるかどうかもわからないと思う。高めに出てもそれは D 問題の壁があったからだよ。■F 問題「Tree Degree Optimization」。Ruby での他の人の提出を見ると、自分のよりずいぶんとシンプルで、自分には見えていない何かがあるのかなと思わされる。自分が考えたこと。各頂点が単独でばらばらに存在していて、(相手のいない)辺を１本伸ばしている。コストはその頂点の値(A)と現在の次数による。木を作るのだから、N-1 回、２本の辺を選んで繋ぐことを繰り返す。繋いだときにコストが発生して、それぞれの頂点からはまた新しい辺を生やす。辺を選ぶのにプライオリティキューを使ったけど、同じ連結成分から生える２本の辺を繋ぐことはできないので、単純にキューから２つ取り出して繋ぐというわけにはいかない。自分はキューを２本使った。１本目のキューにすべての辺を入れて、２本目のキューには最小コストの辺と、それと同じ連結成分の辺を入れた。そうすると２本のキューの最小同士を連結することでうまく処理が進む。だけど他の人の提出を見ると、キューは１本で足りるみたいなんだよね。どう考えるとそうできるのかわからない。■F 問題。次数の和が 2(N-1) になることを利用するのかな。キューには常に N 個の数を入れておいて、２つ取り出してコストを計算して、２つ戻す。自分の提出が無駄に複雑になったのは、個々の頂点の繋ぎ方を区別していたからだ。次数だけをカウントして繋ぎ方は考えないでおくと、シンプルになる。たぶんね。ほらね。提出 #54856675 (AC / 753 Byte / 562 ms)。ほらねじゃない。２つ取り出すのは嘘だった。１つずつ N-2 回取り出す。次数の和が 2(N-1) になるというだけでは条件が足りない気がした。各頂点の次数が最低でも１あるというのも条件なのかな。だから次数 N は予約済みとして、残りの N-2 をキューから引いた。■F 問題。tinsep19 さんのこの提出 #54855773 は個々の辺の繋ぎ方を考えつつもシンプル。木の問題の制約で自分が好きな形式があって、こういう形で親を定めるもの p2,p3,p4,...,pN (1≦pi<i)。これでどんな形の木も作れるんだよ。これと同じ考え方で処理を進めていてシンプルになっている。自分の考えが１つも２つも足りないのが明らかになっていくなあ。■F 問題。自分の最初の AC 提出には嘘があると思う。辺を繋いで、新しい辺をキューに追加するときに、２つ目のキューが空かどうかを確かめて適切なキューに追加するようにしないと、取り出し済みのコスト最小の辺と、２本目のキューに入っている同じ連結成分の２番目以降の辺の、コストの大小が入れ替わってしまうおそれがある。これは自分がキューのトップを参照するのではなく、とりあえず取り出してみた最小値を変数に保存して利用しているせいで生じているバグ。あぶないところだったなあ。■■■G 問題「Sum of Tree Distance」。全方位木 DP だと思ったら普通の木 DP だった。木 DP は DP の中でもやりやすい印象を持っている。積み上げの基礎となる葉の部分が最も単純でとっかかりとして好都合だからだと思う。その代わり子のマージに神経と時間を使う。提出 #54881518 (TLE×2 / AC×50)。２ケースダメでした。何が弱点だろう。メモリ消費と時間がだいたい比例している。メモリ消費は Hash かなと思うけど、どういう形の木だと無駄が増えるんだろう。単純に頂点数じゃあないんだよな。■精進。D 問題。X で ABC305-G Banned Substrings の簡易版だと読んだので、自分の提出 #42262239 をなんとか解読してそれっぽいものを書いた。提出 #54884526 (AC / 496 Byte / 147 ms)。おもしろいのは、っていうかやられたなって思うのは、入力文字列中の ? の出番がごく控えめなこと。力技で長さ N の良い文字列を構築していくにあたって、入力文字列中の A と B はふるいとしての役割を果たしているのだけど、? というのは A でも B でもいいという意味だから、ふるいとして働かないことが機能なのだ。注目する部分が間違っていたし、プログラムの構成も全く予想していないものだった。■■■G 問題。朝のトイレでひらめいてしまった。マージテクのためにサイズでソートしてるんだけど、そのサイズって５とか３の固定だったりしませんか。帰ってからデバッグする。提出 #54896069 (AC / 839 Byte / 3169 ms)。通りました。まさかのマージテク失敗が TLE の原因だった。あれこれ考えることが多いと手癖にまかせて .sort_by(&:size) とか書いちゃうんだな。ところで、今確認したところ tinsep19 さんが G 問題を 528 ms で通している。同じ Ruby なのに桁が違うんだけど、何をどうやっているのか、知りたいが読んで知りたくはないんだな。■F 問題。「自分の最初の AC 提出 #54840376 には嘘があると思う」と書いた。実際に確認したところ、新しい辺を無条件に２番目のキューに入れていたので、懸念していたコストの逆転は起こらないはずだけど、代わりに「２つ目のキューが空かどうかを確かめて適切なキューに追加する」ことができていなかったことが明らかになった。これの何がまずいか。新しい辺を空っぽの２番目のキューに追加すると、そのキューから選ばれた辺が次に繋ぐ辺の一方として必ず使われるんだけど、これがコスト最小であるとは保証されない。１番目のキューから取り出されたものを２番目のキューに入れるからコスト最小が保証される。一方でこれが WA の原因にならない理由もわかってきた。どれか１つ任意の連結成分を選んで、これに属する辺を２番目のキューに入れると決めることでも N-1 回の操作で木を構成することができる。自分は UnionFind を使っていながら、ミスによって UnionFind による連結成分の管理を必要としない木の構成法を実行していた。なんだかなあ。考えが２つ足りず(次数への着目、インクリメンタルな木の構成法)、実装ミスをし(追加するキューの選定)、ミスしたと勘違いをしていた(IMKK)。素直に F 問題の AC を喜ばせてはくれないのか。