脳log[20240210]

2024年02月10日 (土) [AtCoder] 今日は鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）があった。では ABCDE のふりかえりと G の精進を。■A 問題「Arithmetic Progression」。やるだけなんだけど、step メソッドでうまくやりたかったね。ループを回してしまった。■B 問題「Append」。配列が扱えますかという問題。■C 問題「Divide and Divide」。C 問題らしからぬ制約にびびるけども、対数時間で底にたどりつく。１ステップ当たり２分岐あるのが不安だけど、メモ化再帰でダメなら泣いちゃう。Ruby で最短の提出 #50173926 はループなしの計算で解いている。式の中にビット長が２回出てきているのが目を引くが、意味はわかりません。■D 問題「Super Takahashi Bros.」。最初はステージ１から N-1 まで順番に処理する DP だと思った。しかしワープ土管は先へ進むだけでなく前に戻るパターンもある。D 問題でひっぱり出したくはなかったけど頭を使いたくもなかったのでプライオリティキューを貼り付けた。■E 問題「Mancala 2」。最初は前々回の D 問題 Island Tour のように、変化量をため込んでおいて最後に累積和を答えにするのかと思った。そうではない。操作のたびに箱にあるボールを数えて空っぽにしなければいけない。では愚直に操作しよう。BIT で効率良く処理しよう。自分にはめずらしくコメントが書いてある>#50168931。そうしないとややこしくて間違えると思った。１ループ当たり BIT の操作が最大８回あり、入力と出力のそれぞれで N 回の操作がある。N と M の最大が 20 万のときに、(2N+8M)logN のステップは Ruby では非常に不安。わかりやすさのために処理を刻んだけど、TLE になったらいくつかの BIT 操作をまとめるせこくて間違いやすい節約術が求められていた。幸いにも出してみたら 572 ms で余裕のセーフ。■G 問題「Leaf Color」。まず頂点数１の誘導部分グラフは必ず OK。頂点数２のパスグラフも同色の２頂点を組み合わせて問題なく作れる。３頂点から様子が異なる。２頂点を結ぶパスに３頂点目が含まれている場合、この誘導部分グラフは２頂点の組み合わせとしてもう数えてしまっている。余りの数で答えなさいという出題形式から予想できることだけど、頂点同士の個別の組み合わせ、個別のパスをひとつひとつ考慮して数を数えることは許されない。どういう特徴量によれば計算で数が数えられるのか。ある部分木について、色ごとに端点の選び方の通り数を記録した。あとは DP。ある頂点を根とする部分木について、子と子の組み合わせを数え、根と子の組み合わせを数える。提出 #50189012 (AC / 591 Byte / 1023 ms)。木 DP はコードが長くなりがちだけど、９割方は定型の処理であって、この問題に固有の部分は 20 行目と 25 行目ぐらいのもの。その式が見えるまでは何度も何度も合わないサンプルに苦しむんだけど。やっと見えても最初は TLE (#50187841) だったりした。マージテクが使えるように数える数を工夫して、別口で行っていた集計もすでにある数を流用するようにしたら AC だった。こういう解ける G 問題を得点にしたいなあ。正直、木の問題はボーナス問題だと思っている。自分のレート帯を基準にしてだけど、知っているべきことは全て知っているし、解けない問題はないと思っている。こういう強気の姿勢大事。気持ちが負けていると解けない理由を探してしまって解けるものも解けなくなる。そしてあえて水をさすことを書くと、気持ちだけでは解けない問題は解けないのもまた事実。■F 問題「S = 1」はさっぱりです。これが水 diff ってまじなのですか。青じゃないということは、目の付けどころ次第であっさり解けるタイプの問題なのかな。あっさりとさっぱりは似ているけど通じていないよね。私はさっぱりの方でした。三角形の面積の公式を検索して |XB-AY| = 2 の式までは出ていた。しかし探索ができる制約ではなく、そこから何も手が出なかった。高校数学の演習課題でよくあったパターン。手段は授業で教わっているので、ヒントをもらえば最後まで書ける。だけど最初のとっかかりが何もなくて途方に暮れる。それはつまり、知識はあれども理解するには至っていないということなんだろう。そういうようなことが『技術の創造と設計』(畑村 洋太郎) などに書いてある。