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 個の格子点があるんですよ(あたりまえ……ではなかったんだなあ)。