脳log[20230916]

2023年09月16日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)があった。コンテスト成績証。自分のすべての提出。ABCDE の５完遅解き水パフォは軽傷だけど先週(20230909)に続いてなのであまりへーきではない。すべては C 問題のせい。では E までのふりかえりを。■A 問題「Leyland Number」。計算するだけ。■B 問題「Longest Palindrome」。制約上限が小さいので候補となる文字列を実際にひっくり返して比較して大丈夫。文字列比較で楽をしつつちょっとだけケチなことを考えるなら、文字列は全体を１回だけひっくり返して、あとは比較範囲を適切に変換すればいい。■C 問題「Slot Strategy 2 (Easy)」。E までで最も難しかった問題。これに 50 分費やしたのが今日の負けを決めた。答えがあるなら３周期のうちに見つかる。制約が小さいので総当たりで大丈夫。だけど判定が書けなかった。まずどの数字を揃えるかを決めて、文字列を前から見ていって、どのタイミングで揃ったのか、判断する条件が書けなかった。泣きそうになりながらネストした if 式(全部で９分岐)を書いた>提出 #45624994 (AC / 868 Byte)。他の人の提出を見るとリールを止める順番(６通り)を総当たりしていた。あ、そう、なるほどね>提出 #45651218 (AC / 172 Byte)。■D 問題「Relative Position」。BFS。■E 問題「Somen Nagashi」。１番の人から食べられるそうめんを全部食べさせていった。N 番目の人は他の N-1 人の食べ漏らししか食べるチャンスがない。残っているそうめんの管理は SortedSet を使うのが素直だけど Ruby にはないのでおなじみ BIT で代用した。終了後に Ruby の他の AC 提出を７、８個見たけどどれもプライオリティキューを使っていた。どういう方針なんだろう。時間軸に沿ってシミュレーションしているのだろうか。キューには何を入れる？ あとで考える。■F 問題「Fuel Round Trip」。残り 20 分で考えていた。DP だろうなと。だけど、往路でどのガソリンスタンドで給油したかを状態に含めて区別してしまうと、それはただの総当たりになってしまう。制約を見る。ガソリンスタンドの数(N-1)とガソリンタンクの容量(H)がどちらも 300 以下に抑えられている。ガソリンの量が状態空間の軸の１つなのは間違いなさそう。ところで、ガソリンスタンドに注目したときの選択肢は、往路で給油する、復路で給油する、給油しないの３択。往路と復路の DP を同時に進めて３方向に遷移するとすると、状態がガソリンの量(H)の２乗になるけど、全体で NHH≦(300 の３乗)はありえる数字。ただし Ruby にとっては想定解が TLE になるボーダーラインがちょうどここらへんにある。■提出 #45651923 (TLE×15 / AC×22)。Cyberpunk 2077 で遊んだあと寝る前に 35 分かけて書いて、とりあえず WA は出なかった。■提出 #45653214 (TLE×5)。じっくり入念に書き直して TLE は 15 から５まで減った。なぜまだ寝ていない。５つのうち３つは超過時間が 200 ms 以下だとわかるような打ち切り時間になっている。だけどもう無理よ。■E 問題。PQ 解法。たぶん、(復帰タイミング, 復帰者) ペアのキューと、そうめん待機者のキューの２本を持つんだな。できそう。……。できた>提出 #45664340 (AC / 1273 Byte / 805 ms)。■F 問題。提出 #45663250 (AC / 1379 Byte / 94 ms)。かつて C++ は甘えと書いたものだけど、C++ なら素直に書くだけのものを Ruby であれやこれや複雑怪奇にこねくり回すのは不毛に思えてきた。そんな Ruby スクリプトは書きたくないし、シンプルでも読みやすくもないし。というわけでこれは C++ での AC。最初に TLE になった素直なバージョンを C++ に翻訳したもの。unsigned int 型が使える C++ だと、初期値としてのテキトーに大きな値と、答えがないことを表す特別な出力(-1)に共通の値が使えるんだよね。というわけで -1 を乱用してみた。■■■F 問題。提出 #45760450 (AC / 734 Byte / 1970 ms)。すでに Ruby で AC を出していた kuma_rb さんの提出 #45673011 (1885 ms) と見比べて１つ１つ修正して違いを確かめた。ローカルとジャッジサーバーとでは傾向も Fixnum のビット幅も違うのでコードテストを使って。まず DP 配列を１次元化したのが良くなかった。そのせいで添字の加工が必要になっている。高々 300 個の Array オブジェクトなど作ってしまえばいい。そして配列参照の中間結果を変数にキャッシュすればいい。２つ目はループメソッド。自分は配列参照だとか添字にオフセットを加えたりだとかの明示的な添字の操作が嫌いで Array#each_with_index や Enumerable#with_index を積極的に使うんだけど、これを Integer#upto メソッドを使った添字のループに書き換えたら 200 から 300 ms ほど早くなった。嫌だなあ。TLE を回避するためにちまちまちまちま添字の操作をしたくないなあ。だって ABC の B 問題であっても「4×4×2=32 マスの黒白を愚直に確かめるだけ。そんなんでも添字の範囲を間違えたりしてたいへん」なんだから。