脳log[20250907]

2025年09月07日 (日) [AtCoder] 精進。昼間にあった AtCoder Beginner Contest 422。■A 問題「Stage Clear」。ステージ数が倍のスーパーマリオブラザーズ。がっぴの処理と同じ。０始まりに文字列置換して８進数にして１足して文字列にして１始まりに置換するのは書いてて嫌になるほど無駄なのでやらない。じゃあなんで書いた？ 一瞬やろうとしたから。■B 問題「Looped Rope」。サンプル図を見た感じ、１本のひもが交差するのは許されるけど折り返して接するのは許されない、というのを表した問題名らしい。そんなのは関係なく全マス目について「黒マスではないか、隣接する黒マスが２個か４個であるか」を判定する。最初に書いた条件は「黒マスであって、隣接する黒マスが２個か４個であるか」だったけどサンプル実行前に修正したからセーフ。■C 問題「AtCoder AAC Contest」。A と C の少ない方に合わせて AXC を作ったあとで、余っている A_C を崩して AAC/ACC を何個作るかが問題。単に文字の数を数えて３で割るだけなんだけど、解説によると最初に AXC を作るパートを飛ばしてそういう計算をしていいらしい。飛躍が過ぎてわかりません。■D 問題「Least Unbalanced」。想像通りであるしサンプルの通りでもあるように平らに均します。再帰的に分配する過程が操作の逆再生になっている。■E 問題「Colinear」。時間内には解けなかった。過半数っていうんだからテキトーに選べば当たるのはわかります。でもそういう確率的な操作を書いたことがないし、決定的な方法を探して諦めてしまった。翌日に２か所で乱択の文字を見かけたので、そっち方面に突っ込んで考えてみた。半分が同じ直線に乗っているなら、テキトーに選んだ２点が乗っている確率は４分の１。点の数が最大で 50 万なので、線形時間の処理が 20 回で 1000 万。Ruby の限界は数千万のところにあるので試行回数は数十回が限度か。仮に 20 回試行するとして、外れのペア(が定義する直線)を引き続けるのは (3/4)^{20} で 0.3 % くらいらしい。不安だけどまあ。提出 #69170329 (AC / 455 Byte / 1034 ms)。やっぱり 20 回の試行でもけっこう時間がかかっている。lazy が遅い？ それはあると思う。以前から常々思ってるんだけど、find_map メソッド欲しいよね。find が目的だから map{}.find{} だと一度全要素を変換するのに抵抗があるし回りくどくも感じる。かといって find{} で返ってきた値に find の条件ブロックで判定に利用するために施したのと同じ変換をもういちどかけるのも冗長で嫌だし nil 判定はもっと嫌だ。そういうわけで今回は lazy.map{}.find{} になった。でも遅そう。■F 問題「Eat and Ride」。ゴールから BFS をすればゴールまでのステップ数(増加する一方)が揃うので、同一ターンではイコール条件になり前後のターンでは優劣がはっきり決まることになり、ウェイトにゴールまでのステップ数を掛けて消費燃料に換算した値が比較可能になる。毎ステップ各頂点においてゴールまでの消費燃料の最小を更新したもののみが次のステップに進める。ダイクストラ法と違って燃料消費の最小値が更新されることがあるので最悪で２乗のオーダーになるが N≦5000 なので２乗は通る。だからこの問題は各 i をゴールにしたときの最小燃料を問うている。２乗が３乗になった。やるだけの問題にはしないということだ (TLE)。じゃあ唯一のスタート地点である頂点１からたどりますか？ そうするとゴールまでのステップ数が不明なために、(ここまでに消費した燃料,消費燃料の増加量=ウェイト) という２つのパラメータが関わってきてダイクストラ法の基準になるコストが一意に定まらない。提出 #69169539 (AC / 1003 Byte / 117 ms)。パラメータを２つ持ってダイクストラ法をしたらけっこうな速さで通った。消費燃料を基準にしつつそれを絶対条件にはしないで消費燃料の増加量の最小を更新するものにも可能性を残している。それはプライオリティキューを使ったダイクストラ法ではない何かですね。通るとは思っていなかった。というのは、キューに入れるときに消費燃料最小か燃料増加量最小のどちらかを更新する可能性があるかを調べてから入れてるんだけど、そのときに基準値を更新していない。基準値を更新するのはキューから取り出したときに限っている。そうしないと答えを間違えると思ったからそうしているのだけど、結果としてキューが取り出してすぐに捨てられるダメな要素で膨れ上がって出し入れに時間がかかり過ぎるおそれがある。これはダイクストラ法を実装するときの罠であり勘所だから、それをしないのでは TLE になると思ったがならなかった。想定解法はなんだろう。Ruby での F 問題へのすべての提出 を見たら想定解法は通らないっぽい？ 最近の制約はまじでクソだと思う。３乗が通らない N=500 と２乗が通らない N=5000 と NlogN が通らない 5×10^5 のことだよ。俺は Ruby を書くために AtCoder をやっているので、Ruby お断りの AtCoder につまらない思いをさせられたらできることがない。■オンタイムで参加していないので E, F が解けなくても平穏だ。Rated だったら入緑していたね。■■■F 問題。想定解法がようやく理解できた気がしたので書いてみた。提出 #69198045 (TLE×26/AC×25)。かなり気を使って普通でない書き方をしたけど TLE が 26 個。他の人のを見ると、提出 #69146527 (TLE×29 / tinsep19 さん)、提出 #69145173 (TLE×23 / fumta さん)。Ruby では全然見込みがなさそう。一番 TLE が少ない fumta さんの提出はちょっとおもしろくて、辺を頂点ごとにまとめずにそのまま DP の遷移に利用している。そうするとループの回数がちょうど半分になる。ループ１回の処理は往路、復路で２倍になっているので全体の処理量は変わらないけど、ループを回す負担は半分になる。Python で一番速い提出を見てみたらたこつぼのページでたびたびお世話になっている ikatakos さんの提出 #69123541 がコンテスト中に提出されていて、解法が自分のなんちゃってダイクストラ法と同じに見える。Python の層の厚さはすさまじい。Ruby でからくも TLE を免れた遅延セグメント木の問題でも、２人か３人の人がそれぞれの手法を突き詰めてどんどんとタイムの「桁を」縮めていく様子が提出一覧からうかがえたりもした。何をやって縮めてるのか全然わからないんですよ。見た目が違うからたぶん採用している手法は異なってるんですよ。