脳log[20240615]

2024年06月15日 (土) [AtCoder] 今日は CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358) があった。良くないできではあるがしかたがないというあきらめもある。F 問題はどうにもならない。ではふりかえりを。■A 問題「Welcome to AtCoder Land」。比較します。「空白」を 0x20、改行を 0x0A だと決め打ってもいいよね。しなくていい split はしない。■B 問題「Ticket Counter」。前の人から順番にシミュレートすれば答えになる。■C 問題「Popcorn」。制約が小さいので組み合わせる数を決め打ってから全組み合わせを試した。考えなくていいので隙あらば全探索。またの名を総当たり、ブルートフォース。■D 問題「Souvenirs」。スーヴェニール？ ou をウと読ませるのはおフランスっぽい。ジュルナリステン、カムフラージュ、ウイノン…………以上！ つい最近までこれがお土産だとは知らなかったので、なのにお土産っぽい雰囲気がしたので、こういう名前の問題があったのだとわかる。思わず問題名に２って付いてないか確かめた。日記を書いている今調べたら、該当する過去問は ABC286-E Souvenir であり、あちらは単数形、こちらは複数形という違いがあったのだった。まあいいや。値段と個数を１つのパラメータで決めてしまうってなかなかおかしいね。二度見した。要求を下回らない限り最も安いものを選べばよい。B の昇順に処理を進めるなら A も昇順にスキャンするだけで済む。B の降順だとそうはいかないし、正当性にも不安が生じる(実際には問題ない気がする)。■E 問題「Alphabet Tiles」。問題を勘違いしていて解法が間違った枝に入り込んでしまって余計な時間を使った。どこに分岐路があったか。作る文字列は長さ K に限らず、１以上 K 以下であれば良いのだった。最初の間違った解法は、K 文字のうち k 文字が確定している場合の数を文字種ごとに数え上げていく DP だった。長さ K の答えは合っていたけどその他の長さは合わない。長さ K の答えは合っていたので、同じ方法を K 回繰り返すだけで答えが出るのはわかる。しかしこれはまともな時間で完了しなかった。１から K までの一連のプロセスを通じてそれぞれの答えを見つけなければいけない。インクリメンタルに答えを出していかなければ間に合わない。そうすると必然的に DP で持つべき状態が決まる。あとは状態と状態をつなぐ遷移がどうなるか。しばらく悩んで見つけた次の解法は、k 文字が確定しているときにある文字を１から c 文字まで挿入して k+1 から k+c の文字列を作る DP。答えは合ったけどローカルで 30 秒以上かかる。自分の PC で 16 秒だったら２秒制限でも AC になるのは ARC179-B の精進でわかっている(20240602)。システムを HDD から SSD に移し替えたときにジャッジサーバーとの速度差が２倍程度に追いついたのだけど、最後の言語アップデート以来、えっと、８倍に広がったの？ 30 分以上高速化に費やして結局 AC までに１時間ちかくかけた。厳しい。何をやったか。コンビネーションの前計算をして、それだけでなく共通項をループの外に括りだして掛け算の回数を減らしたり、DP 配列の複製を抑制して in-place で値の更新ができるように処理順を入れ替えたりした。それでもコードテストで 3.5 秒だったり 2.5 秒はかかる。AC 提出は #54600449 なのだけど、最後の決め手は 20 行目の %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 をスキャンするだけでは済まないみたいなことを書いたけど、具体的には二分探索と中間位置からの効率的な削除が必要だと、平衡二分探索木みたいなものが必要だと思っていたけど、そんなことはなかった。昇順でも降順でも線形時間でソート部分の O(NlogN) で解ける。B の降順に処理を進める場合にはスタックを新しく１本用意する必要があるが、それだけでよかった。提出 #54693460 (AC / 降順)。だけどあえて降順ソートをするより素直に昇順に処理をする方が簡単。提出 #54576260 (AC / 昇順)。■G 問題。ダイクストラ法とのツイート(？)を読んだのでプライオリティキューを使う方法を考えた。グリッドが小さいから BFS でも大丈夫だと思ったし実際大丈夫だったけど、BFS だと後追い更新が続くとターンが進んでもキューが短くならないんだよね。提出 #54698671 (AC / 1132 Byte / 124 ms / 58 ms)。プライオリティキュー由来の log が付いても 480 ms より速くなった。ちょっと意外。しかも 124 ms というのはテストケース１つ目に特異的なタイムに見えるので、実質的には２番目に遅い 58 ms が最悪タイムだと見ていいと思う。爆速。キューにはグリッドのマスと同じ数だけ K ターン待機した場合のスコアを入れた。ゴールからスタート地点を目指す。移動するごとに決まったスコア(ゴール地点の待機報酬)を引き現在位置の報酬を足していく。最初にスタート地点に到達したときのスコアが答え。負の辺とかは知らない。ダイクストラ法を１回だけやっている。