しじゅうく‐にち【四十九日】〘名〙 人の死後四九日目に当たる日。また、その日に行う法要。」とか書いてあって、これもうわかんねえな。いやホントはわかりますよ。「四十九日」「七七日」の２つと「四九日(目)」とでは使用時期にずれがある。辞典の言葉は収録される言葉よりも新しい。23 日を二三日と書くことの帰結として、10 月が一〇月になっていたのが先々週読んでいた小説。何を今更感しかないけども、そうなんだ、そりゃそうなるよな、だけど気持ち悪いな、その○はなんなんだ、漢字ではないよな、とひっかかってしまったのが今日の日記になっている。十月って書きたいよ。■ATOK で 10 を変換して出した一〇で使われているのは○ではなかった。U+3007 は「漢数字ゼロ IDEOGRAPHIC NUMBER ZERO」であり、U+25CB 「丸印，白丸 WHITE CIRCLE」とは異なる文字だった。〇が比較すると新しい字だけど数百年はさかのぼれるみたいなことが Wikipedia の漢数字のページに書いてある。お前漢数字なのか。漢数字とアラビア数字を区別して一方では位取り記数法を認めたくないっていうのは、単に好みや慣れや、旧弊に囚われているってだけなのか。自分はこれからも区別して用途を分けていきます。■用途を分ける(漢数字では位取り記数法を使わない)ことの別の一面は、「健康第１」とか「３位１体」とか「別の１面」とは書かないということ。算用数字を使うのは１、２、３と数を数える場面だけでいい。X と X+1 が可換な場合だけでいい。七七日 。
A-M$N-Z と並べたなら、(A,N),(B,O),(C,P),...,(M,Z) のペアを作る(のだと思う)。ローカリティに注目すればなんとなくそれでいいような気がするし、逆に両端からペアを作っていくのがダメなのもわかる気がするが、いつでも絶対それで OK とはわからない。■自分の解答の後半のステップはプライオリティキューを使わないで、単純に入れ子配列をフラットにして真ん中で切ってペアを作るので良さそう(C.flatten!; C[C.size/2..].zip(C))。どの解説もそういうペアの作り方をしてるので。どの頂点集合も過半数に届かないようにしているのだから、たしかにそれで同一集合からペアを作ることはないみたい。それと、DFS での頂点の並べ方は帰りがけ順でも OK と解説に書いてあった。Array#each_cons がおそらく線形時間を要するせいで TLE を１回出した。たしか以前も同じメソッドで TLE を出している。学習しないな。だけども、配列の dup や shift、pop では配列の要素レベルのコピーが抑制されると知っているから、配列から固定サイズの部分配列を切り出すのに単位時間しかかからないと期待するのは当然じゃない？ each_cons が Array#each に基づいて実装されてるとしても、一度の each_cons 呼び出し(と複数回のブロック実行)で線形時間しかかからないなら TLE にはならなかった。尺取りをするなら TLE にはならない。ブロック実行のたびに線形時間かかっていて、each_cons 全体では２乗の時間がかかっているからこそ TLE になる。これが予想外。■D 問題「Go Stone Puzzle」。制約がごく小さいのでメモして BFS をする。実装でいろいろミスをした。たとえば (1,2)、(3,4)、(5,6) みたいな (奇数番目,偶数番目) のペア単位でしか交換できないと思い込んでいたり。そこはちゃんとサンプルで落とされたけども、見るべき要素数が N ではなく N+2 だったりも。15 分かかった。■E 問題「Tree and Hamilton Path 2」。ARC179-D Portable Gate の簡単バージョン。精進記録はこちら>20240602。根を決めて DFS ですべての頂点を訪れてまた根に戻ることを考えると、すべての辺をきっちり２度ずつ通るのでコストの上限がまず決まる。本問題では根に戻る必要がないのでどれだけのコストが節約できるか。直径。自分の提出がすでに求まっている直径を再帰関数で改めて求めているのは、紆余曲折の結果なのです。引き算で求めるのではなく、２種類の再帰関数で積算して答えを求めようと迷走していたなごり。プライオリティキューを貼ったけど、いらなかったらしい。根からすべての頂点への距離を求めているのだし、各頂点へのパスは１つだけなのだから、それはそう。■F 問題「x = a^b」。苦手な苦手な数学問題。指数を３以上に決め打つなら N 以下の全ての立方数、４乗数、５乗数(って呼ぶのか知らないけども)……を列挙して重複を排除できる。じゃああとは最大で 10^9 個ある平方数をどうやって数えるかだけ。すでに数えた立方数、４乗数……が平方数でもあるかどうかを確かめて重複を除外することでクリアした。この問題の提出でも自分は変なことをしている。b を固定したときの a の最大値を Math.log で求めてからすべての a^b を列挙してるんだけど、それだったら a=1 から始めて N<a^b になるまで a+=1 を繰り返せばいい。コンテスト中はそこまで頭が回らないんだなあ。■G 問題「Go Territory」。解けてないよ。サンプルにあるように囲われている格子点を数えたい。縦横斜めに並んだ石のあいだで UnionFind をして、まずは輪っかを作っているかもしれないグループを特定した。次にグループを構成する石の周囲８マスから BFS を開始して孤立している格子点の島を数えようとした。どこで探索を打ち切るか。グループを構成する石の X 座標 Y 座標の最大最小を限度にして BFS を打ち切って孤立していないと判断をした。これでサンプルは合ったけど、WA があるかもそうだけど TLE は間違いないと思うんだよなあ。おおざっぱに２乗の範囲を塗りつぶそうとしてるわけだから。■コンテスト成績証。黄パフォに限りなく近いいいパフォが出たけども、前回(ABC が Unrated 判定だったので配点と Writer から必敗を覚悟して出た ARC)の緑パフォの傷が癒せただけなんだよなあ。F 問題まで４桁人数が解いてるので早解き回だったみたい。それは配点からも読み取れる。簡単な問題に滅法強いという自己評価を裏切らない結果。■G 問題。自分のやり方で WA になる例。ループが２つ左右にくっついていて、右のループの周辺ということで、右のループの外側、左のループから見れば内側から BFS を開始した場合、打ち切るタイミングを誤る。盤面を BFS のたびにクリアすれば解決するけど、ますますもって TLE が加速する。■■■精進。G 問題。提出 #55351016 (AC / 796 Byte / 571 ms)。kotatsugame さんの動画(【競技プログラミング】ABC361【実況】)で解法を聞いたんですよ。UnionFind をするのは石と石ではなく、縦もしくは横方向に連続した格子点列の隣り合ったもの同士だった。やってることは難しくなくて、付加情報として格子点数を持った UnionFind だけど、頂点番号が与えられているわけではないので、格子点列に自分で番号を割り振らないといけないひと手間がやっかい。Y 座標列をソートし忘れたり、ひと手間に色んなミスがからんでくる。グループの管理と格子点数の管理を同時にやろうとしてグループ０と数０を混同したりもした。また、格子点の総数が数えられなくて答えがなかなか合わなかった。X 座標の最大値が 200000 だとして、0 から 200000 のあいだには 200001 個の格子点があるんですよ(あたりまえ……ではなかったんだなあ)。3 2 という入力例がある。サンプル１のように解説がないし、出力例が実数ではなく 554580198 (mod 998244353) だということで、途方に暮れていたのが昨日。だけどね、自分で計算すればいいんですよ。昨日の方針だけど、場合の数を K 回数え上げていって、最後に N^{2K} で割ることで確率に変換するようにしていた。ということは、3 2 という入力に対しては９通りの出目が２つ続く 81 通りの場合がうまく数えられていれば良かった。81 に足りなければ遷移の式が誤っているということ。そのようにして今日はサンプルの２が合った。そして次のサンプル３の入力が 4 4。これの答えがまた合わなかったのだけど、同じようにして 4 2 に対する 256 通りの数え漏らしを見つけることでサンプルの３もまた合った。■提出 #55117837 (AC / 362 Byte / 126 ms)。N=1 で WA を出さなかったのはすでに他所で知っていたから。全く警戒していなかった。■この E 問題までささっと解けてまだ不満というのが自分の現状認識なんだけど、また脳みそにクモの巣が張ってきてるみたい。半年後からの挽回に期待！■続けて G 問題 Suitable Edit for LIS にも取り組んで提出したのだけど、#55121924 (WA×8/AC×45)、WA になるケースが全く作れなくてデバッグが進まない。C++ の AC 提出と答えを突き合わせたりしてるんだけど、最初にコピーしてきた提出は長さ６程度のシャッフルした順列に対する答えがおかしかったよ(それでも AC)。２つめにコピーしてきた C++ の AC 提出とは意見の一致を見たので、自分だけが盛大な勘違いをしているということはなさそう。こんなザルなジャッジだったら８個くらいの WA は見逃してくれてもええやろ。■G 問題について現在わかっていること(あるいは勘違いしていること)。操作によってできるのは LIS の長さを +1 することだけ。先頭か末尾の値を含まないで LIS が作れるなら、先頭か末尾の値を操作して +1 できる。では先頭と末尾の値が LIS に不可欠だったら？ 適切な位置に LIS に参加しない空き要素があるなら +1 できる。適切とは？ 空き要素があってもその前後にある LIS を構成する要素が連番だったら +1 できない。条件はこれだけだと思う。ところで LIS って候補がいくつもあるのが普通。最長の長さを知りたいだけならそれらを区別する必要がないけど、今回は空き要素を挟めるか挟めないかがポイントなので、LIS の個別の列に踏み込んでいかないといけない。添字列に対して LIS を求める操作をして作業配列を上書き更新せずに追記して履歴を残すようにしたらうまくできないかなーと思って書いたのがさっきの提出。なにがうまくないのかわかんない。思いつきでいけるやろって思う方がおかしいか。そうか。■■■通ったー！！！ G 問題。提出 #55154669 (AC / 672 Byte / 277 ms)。前の提出が 671 Byte だった。17 行目の < を <= にすると WA が AC になった。狭義単調増加だから、値の比較にイコールがないのは一見自然なんだ。でも 17 行目では LIS に含まれない要素をはじいていた。< の否定が >= であるように、そこではイコールが必要だった。なんだー、１文字かー。ランダムケースの生成ルールを A = 1,*([2,3,4]*3).shuffle,5; puts A.size,A*' ' に変えたらすぐに見つかった。同値の要素の重複がキーだった。ともあれ、やろうとしたことがちゃんと AC に繋がっていたのは良かった。■LIS の履歴の活用法について書く。作業配列には通常長さ i の増加列の末尾の値を記録する。最終的に i が取り得る最大値が LIS の長さ。今回は値の位置も知りたいので値の代わりに添字を記録し、さらに履歴も知りたいので各長さ i それぞれに添字列を記録していった。入れ子配列の総要素数は N+(LISの長さ) になる。作業配列には最長に届かなかった短いものも含む全ての長さの増加列の情報が記録されている。これを後ろから見ていくことで LIS の一部ではない要素をはじいていくことができる。値を見ることで添字列の先頭から、添字を見ることで添字列の末尾から取り除いていくことができる。たぶんね。あとは前後の添字列を見比べて LIS に中間値を挿入する添字の空きと値の空きがあるかを確かめる。■■■遅れていたレート更新があったのだけど、B 問題で範囲が間違っていた普通の WA コードを投げた人が Unrated に不満を表明していた。テストケースの制約違反とは関係なく WA だった人も Unrated なの？ 確かめたら自分も Unrated で草。４完低パフォだから不満はありませんけども。1≦c≦w という範囲を添字にするときに、c を 0 始まりにするのを忘れて各行１文字目を縦読みするケースが漏れていて WA を１回出したんだよね。最終更新: 2024-07-12T00:35+0900
いつもの前置き：提出先は AtCoder だけど問題は AtCoder の作成ではなく JOI で、だけど競プロカテゴリを意図して AtCoder タグを付けています。
しんどかった。BC 問題を読むのは気が向いたときにして、A 問題についてだけ書く。
４種類の論理演算(! & ^ |)と、かっこと、ある値を境にして真偽が切り替わる関数から成る式の値について、クエリに答える問題。式の長さが 1M 文字以下で、クエリとして与えられる値の数が 200K 個以下。つまりどちらもとてもでかい。
クエリを昇順に並び替えたら、入力値との比較で真偽が決まる関数というのは、一度だけ false から true に値が切り替わる関数になる。更新頻度が (関数の数)×(クエリの数) から (関数の数) に減る。
以上の２つのアイデアというか願望に基づいて最初に書いたのが次の提出
関数を class で置き換えて、そのクラスに演算子を定義して、式全体の評価を eval で行うお手軽な実装。
eval であるか *.rb ファイルを実行しているかに関係なく、大きな式を評価しようとすると Ruby は黙って異常終了する。式の形によっては終了する前に nesting too deep (SyntaxError) というエラーが出ることもある。p 1^1^1^1^1^...^1 という 1 か 0 を表示するスクリプトをコピペで膨らませて実行すると、Ruby のバージョンと Windows でのスタックサイズに左右されるんだろうけど、手元では 7 KiB を超える前に何も出力されなくなった。
両極端の例を挙げると、1+2+3+4+5+6+7 という式を [+ [+ [+ [+ [+ [+ 1 2] 3] 4] 5] 6] 7] と解釈するとき、(1+(2+(3+(4+(5+(6+7)))))) という式を [+ 1 [+ 2 [+ 3 [+ 4 [+ 5 [+ 6 7]]]]]] と解釈するとき、階層が直線的に増えていく。
中置記法とかっこの存在が式の扱いを難しくしている。
変換アルゴリズムがうまく書けなかったので、検索してトップに出てきた「逆ポーランド記法入門２｜中置記法から逆ポーランド記法への変換」というページを参考にした。
うまく書けなかった部分、求めていた答えがまさに「演算子を全てpopして」と与えられていて喜んだのだけど、あとになって答えが合わない原因が「全て」にあることがわかった。上のページで扱っている四則演算のように、演算子の優先順位が１位と２位の２つだけなら「全て」で正しい。それより多いなら、「これから入れようとする演算子よりも優先順位が高い演算子を pop できる限り全て」が正しい。日本語の説明と Python の実装例に齟齬はなかったので、日本語だけの問題ではないみたい。その一部分を除けば文章だけでアルゴリズムの全体像がイメージできるわかりやすい説明ではあった。
これで RE は解消するけど TLE はなくならない。むしろ eval を呼び出してインタープリタに丸投げすることができないぶん遅くなる。
例えば [1]^[2]^[3]^[4]^[5] という１つの式があって、クエリが 10 だったとする。最初は全ての関数が false で、クエリの昇順に true に切り替えていく。10 が最小のクエリなら、1 から 10 までの関数を順番に true に切り替えていくのだけど、その過程でこの式は false>true>false>true>false>true と値をチカチカ切り替えていく。もしこの式の全体が別の式の一部分であるなら、それら外側の式も同時に連鎖的に値を切り替えていくことになる。
更新の伝播を階層ごとに一旦ためておいて、深い階層から足並みを揃えて各項につき１度だけ値を更新しようとした。その過程で更新と更新が重なって更新が消えることも期待できる。ただまあ、これは根本的な解決策ではなく、効果がある入力もあるかもね、というレベルの対策にすぎなかった。TLE はなくならなかった。
演算子の優先順位を考慮して、| ^ & の順番で、もっとも真ん中にある演算子で分割する。
たとえば [1]&[2]&[3]&[4]&[5]&[6] という式なら [& ([1]&[2]&[3]) ([4]&[5]&[6])] と分割する。
たとえば [1]&[2]&[3]&[4]|[5]|[6] という式なら [| ([1]&[2]&[3]&[4]) ([5]|[6])] と分割する。
ところでこの分割は同一階層内でしかできないので、[1]&([2]&[3]&[4]&[5]&[6]) の分割結果は [& ([1]) ([2]&[3]&[4]&[5]&[6])] になる。かっこを無視して分割してしまうとあとでどうくっつけていいかわからないので。
かっこに制約されるということで、更新が影響する範囲を対数レベルに抑えて TLE を解消する助けにはならなかった。
なぜか抵抗があって考えないようにしていたのだけど、TLE 続きでなりふりかまっていられなくなったので、結合法則を使う。実は対策３でももう使っている。
「なぜか」っていうか、左結合だと問題に明記されていたから、それを無視するのはずるであると、理性ではなく感情が訴えるのだ。答えが合いさえすれば何をしてもいいという教育は受けていない。たぶんそういう理由。問題の解釈が曖昧にならないように出題者が左結合だと定義するのはわかる。交換して答えが変わらないのを見抜いて利用するのが解答者だというのもわかる。だけど無意識が抵抗している。まあいいや。
中置記法の式はかっこがあってややこしいので逆ポーランド記法の式を操作する。
たとえば 1+2+3+4+5+6 を逆ポーランド記法に書き換えると、1 2 + 3 + 4 + 5 + 6 + になるのだけど、演算順序をいじって 1 2 3 4 5 6 + + + + + に書き換えたい。
そうすると何が嬉しいか。演算子に由来する階層を取り去って [+ ([1]) ([2]) ([3]) ([4]) ([5]) ([6])] と解釈することが容易になる。次にこれを６項演算として扱うこともできるし、２項演算のまま引数列を半分半分にしていくこともできる、半分半分にするということは、セグメント木のようにきれいで効率的な階層が作れるということ。
正しい方向に向かっていることを予感させるけど、１パスでやろうとして十分にマージできなかった。
たとえば次の式の書き換えを考える。1 2 + 3 + 4 5 6 + + +。参照範囲が限定できるので予め連続する演算子を結合しておくと便利。1 2 + 3 + 4 5 6 +++ になった。左から読んでいって最初の + 演算子に出合うとき、右の要素が被演算子(3)でその次の要素が + 演算子なら、順番を入れ替えて 1 2 3 ++ 4 5 6 +++ にできる。しかしこれ以上の結合ができない。被演算子もまとめておくとひとつ飛ばすだけで +++ にアクセスできる？ だけど 4 という項は 2 2 * という演算子を含む３項として存在していることもありますね。
対策４とやりたいことは同じなんだけど、今度はうまくできた。演算子に行き当たったとき、スタックから取り出した２つの値(a, b)を即座に [op a b] としてスタックに戻すのではなく、a、b が単独の値か何らかの演算の結果なのかを調べて可能ならマージして、できるだけ階層を増やさないようにした。そしてそれが最後でもなく、スタックから取り出されてまたマージされることもある。
これの 92 行目から 107 行目のあたり。
2K オーバーの長大なスクリプトになってしまった。絶対もっと短く賢く書けるはずでしょ。
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 を喜ばせてはくれないのか。%P の位置だった。３項の掛け算のあとに %P をくっつけていたのを前にずらして２項の掛け算にするだけで２秒オーバーが１秒未満になった。Ruby にはオーバーフローがないからついテキトーに %P を付けたり省いたりしてしまうんだけど(%P が多すぎても少なすぎても TLE の原因になるのだ)、同じ１回の %P でも位置によって効果がだいぶ違うんだなあ。■F 問題「Easiest Maze」。出力形式難しすぎ。そして問題文が間違っていた。「壁があるときに辺で結ばれていて、長さ K の唯一のパスを構築する(大きさ K の連結成分では十分ではなく、塊やループや３つ以上の端点があってはいけない)」というのでは壁の既成概念が崩壊する。質問と訂正があるのを待つことにして A 問題からの実装を始めることにした。終了の 25 分前に戻ってきたら問題文の修正は終わっていたが、差分を調べるのが面倒で読まなかった。すること自体は難しくなさそうに見えてやりきるのはすごく難しいかも。自分の頭で考えて答えを構築するなら、縦と横の偶奇の扱いがやっかい。だったら機械に長さ K のパスを探索させれば何も考えなくていい。100×100 というのが素朴な DFS にとってどれだけの規模感なのかよくわからない。やばいとは思う。マスの埋まり具合と現在位置でメモ化してもどうか。２、３日前に読んでいた『競技プログラマー ハンドブック』(PDF) で紹介されていた枝刈り手法が使えそう。壁にぶつかって左右に進路が分かれるとき、ゴールがない方の進路に答えはない。なんにせよ時間がなかった。■精進。G 問題「AtCoder Tour」。F より低い青 diff なのを見たので問題を読んだ。現在のマスが終着点だと仮定したときの想定楽しさを元にした BFS でできそう。提出 #54618901 (AC / 413 Byte / 480 ms)。できた。こんな腑抜けた G 問題を置かれると、目の前の問題を解く以外のことを考えさせられてめんどうくさいんだよなあ。■■■精進。F 問題。やっぱりね、「すること自体は難しくなさそうに見えてやりきるのはすごく難しい」。何をするかって、ぐねぐね左右に線を引いて、ラスト２行の帰り道では縦にぐねぐね線を引いて、それをフォーマットして出力する。がんばってやる！ 提出 #54644107 (AC / 1676 Byte / 51 ms)。右へ線を引く、下に移動する、左へ線を引く、ぐねぐねしながら左へ線を引く、と関数を分けることで、同時に１つのことだけを考えればいいようにした。文字列化するのも、行を出力する関数と行間を出力する関数に分けて、同時に１つのことだけを考えるようにした。もーたいへん。縦横の偶奇と K の偶奇は調べなかった。予め達成可否を判定することはせずに(できませんから！)、やるべきことをやった結果ゴールにたどり着いているかどうかで判断をした。これは ABC347-D の反省から(「RE/WA を出した方では、不可能なケースを最初に判定するようにしていた。一方の AC 提出の方では、操作をしたあとで、結果が満足しているかどうかで出力を切り替えた。要するに、不可能なケースの判定に漏れがあったのだ」)。■■■F 問題のジャッジがザルだったらしい。まあ、あの大作の出力形式を整えて提出しただけで評価されてもいいよ。■G 問題。「現在のマスが終着点だと仮定したときの想定楽しさを元にした BFS でできそう」について書く。まず、待機するマスは必ずパスの末尾になる。最適を目指すとそうなる。パスがあって長さが決まっていて、残りのターンを費やすのは報酬が最大のマスに決まっている。それがパスの途中にあるとするなら、そのマス以降のパスが蛇足だったということになる。移動を省いてそのターンも待機に費やした方が良い。だから待機マスは必ずパスの末尾になる。▐あるマスに到着したときのことを考える。関心事はそのマスを最終地点とした場合のスコアだから、到着時点での残りターンを報酬に変換してスコアを比較する。スコアがすでに記録されているスコアと同じか下回っている場合は探索を打ち切って良い。なぜか。パスを伸ばす目的というのはより良い待機報酬を求めることにあるのだから、あとから訪れていて残りターン数が少ない探索の枝はそれだけでビハインドを背負っている。それなのにパスに依存したスコアが余分に費やしたターン数に見劣りしているというのだから、これ以上の探索で先達より良いスコアを得る可能性はない。▐もう全部書いた？ 提出したあとになって問題があると不安になって、でも実は問題がなかったことがある。BFS で t ターン目の処理をしているときに、隣接マスを t+1 ターン目のキューに入れると同時に t+1 ターン目の状態をその隣接マスに書き込んでいる。このあとさらに t ターン目の処理を進めているときに、さっき t+1 ターン目のキューに追加したマスが出てきてしまったら、t+1 ターン目の状態に基づいて t ターン目の処理をすることになるのではないかと考えた。でもチェス盤を考えるとわかるんだけど、t ターン目のキューと t+1 ターン目のキューに同時に入るマスは存在しないのだった。うまくできてるんだなあ。今までそれを知らずにグリッド BFS を書いてたんだぜ。■■■D 問題。B の降順だと A をスキャンするだけでは済まないみたいなことを書いたけど、具体的には二分探索と中間位置からの効率的な削除が必要だと、平衡二分探索木みたいなものが必要だと思っていたけど、そんなことはなかった。昇順でも降順でも