/(A+)/ で split するのか /([^A])/ で split するのかということを。あとは入力によらず処理を統一するために入力の頭に必ず A を付加し、末尾に必ず AZ を付加するなどした(答えは変わらない)。そうすると split(/([^A])/) した結果が必ず偶数になって都合が良い。S と T をそれぞれ split して、偶数番目の比較で判定ができ、奇数番目の比較で答えが求まる。abs を付け忘れてサンプルが合わない。11 分かかったので D 問題より難しい。■D 問題 Take ABC 2。D は DP の D……ではありませんでした。ただの貪欲。最も左にある i を使用しない理由がないし、そのときに、i より右にあって最も左にある j を使用しない理由がない。最初に入力をスキャンして A、B、C に対応した i,j,k の列を用意しておいて、前から順に使えるものを使っていく(#73691658)。事前準備なしのバージョンはもっとシンプル(#73746369)。A の数と AB の数と ABC の数を管理しておき、A への遷移、A から AB への遷移、AB から ABC への遷移を文字列に沿って実行する。■E 問題 Divide Graph。辺のコストが倍々になっていくというのが特徴。この特徴をどう読めばいいのかは chokudai さんの典型に関するブログで読んだ(「競技プログラミングの強みと「典型力」について - chokudaiのブログ」)。つまり、大きい方から見てある辺を選ばないで済むのなら、それより小さい辺をすべて選んでもコスト的に見合うということだ。こういうことを書くのが今回初めてというわけでもない。初めてのときは二進数になぞらえて理解してなるほどねと膝を打つ様子を書いたと記憶している。さておき、じゃあソートして UnionFind だねというのが考えずにわかるんだけど、結局実装して提出するまでには 20 分かかるんですね。サンプルで気づいた見落としは、あるボーダーラインがわかったとして、それ以降のすべての辺を必ずしも選ばなくてもいい、ということ。その判定をするためにはボーダーラインを見つけるための UnionFind を寸止めの状態に保つ必要があって、そのへんでごちゃごちゃと場合分けが増えて時間を食った。■F 問題 Centipede Graph。以前にも似た問題があったかな。アルカンの問題。今日は両端の水素が１つずつ少ない。末端から積み上げていく DP を最初は検討したけど、積み上げていく段階では答えが出せない。全方位木 DP ってこと？ 結局はトップダウンで実装をしてそれがやりやすかった。まずコアとなる頂点を１つ決める。隣接頂点ごとにどれだけムカデの体節を伸ばしていけるかがわかれば、あとは最長の２つを選んで組み合わせたり１を足したりなんだりごちゃごちゃやって答えが求まる。「どれだけムカデの体節を伸ばしていけるか」を効率良く求めるのはメモ化再帰で実装した。一度の呼び出しで答えをすべて用意することはできない。呼び出し元を呼び出し返すことができないからだ。少なくとも２つの隣接頂点から呼び出されて初めてメモが完成する。かといって隣接頂点リストを呼び出しのたびに何度も走査すると星形グラフで死ぬので、リストは破壊的に消費することとした。一方向にどれだけ体節を伸ばせるかと、体節と体節を組み合わせて全長がいくつになるか、どちらも答えが１通りや２通りではなく計算が間違いやすくなっている。25 分で１ペナを出して、５分で修正して AC。実装がトップダウンで素直だったから凡ミスしかないと確信できたし読解もスムーズで頭から一読してバグが見つかった。時間が 20 分余ってしまった。625 点の G 問題にできることはありません。真ん中２つの使い回しが総当たりできるならなんとかなるかもしれないけど(トップ４)、それができないのではね。■自分のすべての提出。コンテスト成績証。瓦増えず。■F 問題。自分の実装(#73718005 の 18 行目)にバグがあると思ったけどバグはなかった。トップ２をメモして答えに利用しているのだけど、要素数が２のときの順序が追加された順で不定。でも要素数が２しかないときは答えが定数なのでセーフ。こんなのが原因で WA になったらリカバリーできないぜ。あと、他の人の提出が UnionFind とか直径とかいろいろ謎。次数が３以上の頂点だけのグラフを考えるのだろうか。いや４以上。端っこの処理が難しくない？ あとたぶんボトムアップで積み上げる木 DP でもやっぱりできるような気がしたな(全方位木 DP でなく)。２通りを数える必要があって、自身が中間の体節になる場合と、一方の端になる場合の両方を考えていくことで、行って戻る全方位でなく行きっぱなしの道中ですべての答えが列挙できる(たぶん)。■■■F 問題。ボトムアップで積み上げる木 DP バージョン。たいへん厳しい。じっくり丁寧にコメント付きで書いたけど WA×34、WA×25 のち AC。大枠はさっき書いた通り、自身が末端になるケースと自身が中間ノードになるケースを数える。それが WA×34。忘れてはいけないのが、自身が末端かつ唯一のノードになる場合で、必要な子の数が１つ減るので答えがゼロかイチかが変わってくる。それで WA×25。さらに、親に伝える数字には親を勘定に入れてはいけないけど、自身が答えを作るときには親を子の１つとしてカウントすることで他の子の要求数を減らすことができる。値としては同じものが含まれるとしても親に伝えるものと自身で使うもの、７つも８つもの数字を頂点ごとに取り扱って考え漏らさないのはとても難しい。一度 AC を出した後でよくよくわかっていても間違えるのだから、実装方針で当たりを引くという幸運があったのだとよくわかった。