脳log[20251123]

2025年11月23日 (日) [AtCoder] 昨日は AtCoder Beginner Contest 433 があった。ABCD ４完だけど意外に耐えた。それで耐えられるレベルが情けない話。■A 問題 Happy Birthday! 4。最難関 A 問題来ました。なんもわからん。どっちが大きくてどっちが小さくてどっちがいくつずつ増えてどっちが早く大きくなるのか、なんもわからん。全探索でも許されるのはわかる。でも十分な範囲がなんも見積もれない。実行時間で区切れば 1000 万まではいける。でも 10000 で十分な雰囲気(！)も感じられる。ふわふわといつまでも雲を掴んでもいられないので６分時点でとりあえず投げて運を天に任せた。■B 問題 Nearest Taller。N が 20 万なら考えるけど N が 100 なので考えずに全探索。なんで A 問題がこうじゃないんだ。■C 問題 1122 Substring 2。1 と 2 の境界を全探索して、左右を調べる。高々全長の２倍しか調べないので愚直にやって大丈夫。■D 問題 183183。x と y の mod M が足してゼロか M なら f(x,y) が M の倍数。x の mod M がそのままの値ではない。y の桁数によって 1 から 10 桁まで持ち上げられる。10 から 100 億を x に掛けたものの mod を取る必要があるということ。数列 A の要素ごとに高々 10 通りの mod M なので予め集計しておく。■E 問題 Max Matrix 2。時間を使い過ぎないようにうまく情報を持って順番にマス目を埋めていくだけだと思った。最初の実装を完成させるのに１時間と６分かかった。時間を使い過ぎないようにうまくやれはしたけど、別の意味で時間を使い過ぎているし、WA が出てしまった。提出 #71168194 (WA×4/AC×26)。残り６分なのでランダムケースで考え漏らしやバグを見つけることもできず終了。F 問題は読んでいない。■■■精進。E 問題。WA だった最初の提出 #71168194 に対して必ず Yes となるランダム入力を与えてみたところ問題なく答えが出せていた。だから早期に No と答えている 33 行目が誤っているのかと疑って取り除いてみた。提出 #71212471 (WA×4)。結果に変化なし。では No と答えるべきところで No と答えられていないことが疑われる。ちょっとひらめいて、必ず Yes となるランダムケースの、X 数列の要素のひとつをインクリメントしてみた。つまりある行の本当の最大値よりも１つ大きい値が最大値として指定されているわけで、行列を埋めるに際しては寛容な制約となるが、もちろん制約を満たす最大値を埋めることはできないはずだ(必ずできないかはわからない)。提出 #71212530 (AC)。何をやって AC になったかというと、答えらしき行列を埋めた後で、事後的に各行各列の最大値が入力の X,Y 数列を満たしているかを確かめている。悔しいなあ。やるべきことはできていたし、実行時間にも余裕があったのに、検算をする慎重さが足りなかった。実装に時間をかけすぎていたことも敗因。大きい値から埋める派と小さい値から埋める派の２つを観測したけども、自分は大きい値から埋めました。小さい値から埋めるときに何を考えるのかはわかりません。「小さい値から行列の要素を埋めていけばよいです。行と列の片方にその値があればどちらかを適当に埋めていけばいいのですが、両方にある場合は交わった要素をその値にしなければなりません。 また、それ以外のその値以下で使われていない最大の値にすればよいです。それにはBTreeSetを使って要素を[first, last)の区間にすればよいです。結果的に区間が隣り合えば結合します」 わかりません。