脳log[20231202]

2023年12月02日 (土) [AtCoder] 今日は大和証券プログラミングコンテスト2023（AtCoder Beginner Contest 331）があった。結果は知らねーよ。自分のすべての提出。では F の精進までを。■A 問題「Tomorrow」。繰り上がり処理を２回まで書けばいい。■B 問題「Buy One Carton of Milk」。おおざっぱな総当たりができる。テキトーに組み合わせて N 個を超えていればコストを比較して最低のものを選ぶ。■C 問題「Sum of Numbers Greater Than Me」。昇順もしくは降順に総和を更新しながら答えを得る。■D 問題「Tile Pattern」。はい、G 問題を除けば本日のボス問題です。いや、まあ、ただの２次元累積和なんだけど。図を書いて整理すればもっと早く解けたのかな。クエリを２段階に変換した。クエリは左上隅の点と右下隅の点として与えられる。用意した累積和は原点からの和なので、いつもの包除で A-B-C+D の形にする。A,B,C,D は原点を左上隅とする矩形(に含まれる黒マスの数)なので (高さ, 幅) として解釈してもいい。これを N×N の正方形の繰り返しと、(N の倍数)×(半端) と (半端)×(N の倍数) と (半端)×(半端) の長方形３つに切り分けて N×N の累積和から数字を拾う。これに１時間 12 分かけたんですって。それってコンテスト時間(100 分)の 72 %。E、F 問題を解く時間はどこだ。■E 問題「Set Meal」。N×M の組み合わせを全列挙はできないから、うまいことコスト順に列挙して駄目ペアではない最初の組み合わせを見つけたい。最初はうまく列挙できなかったけど、開き直ってあまりうまくない列挙にすることで列挙しやすくなった。プライオリティキューに最初に N+M 個のアイテムを突っ込んだ。各主菜に対してもっとも価格の高い副菜を、各副菜に対して最も価格の高い主菜を、まずはキューに入れた。あとは取り出しては次の候補をキューに入れる。そして駄目ペアでなければ答えにする。駄目ペアの持ち方について。添え字で与えられるが数列をソートすると情報に齟齬が出る。だがソートはしたい。添え字配列をソートすることで主菜副菜のソート列と駄目ペアの添え字を仲介したけども、駄目ペアを値のペアとして持って数を数えても良かった(その場合自分がやったように重複した組み合わせをキューに入れてしまうと間違えるんだけど)。そんなとこに気を回してる余裕はなかったけども。結局 35 分かけてコンテストは終わっていた。■F 問題「Palindrome Query」。ローリングハッシュかな。１点更新のセグメント木かな。ちょうど何日か前に第16回 アルゴリズム実技検定(過去問)-N「ソートと関数」に提出した #48039671 が使えそうだな。TLE (#48152176, #48153685) が出た原因は累乗をメモしなかったことと、選んだ素数が 51 ビット幅だったことではないかと思う。51 ビットと 51 ビットを掛けたら AtCoder のジャッジサーバーで動いている Ruby の整数型が 64 ビット幅だとしても Bignum が出てきて遅くなるんだよ。提出 #48153886 (AC / 1130 Byte / 1164 ms)。■最近の ABC は F 問題まで解ける問題が並んでるんだけど、成績がまったく奮わないのなんでだろね。■■■D 問題。最初の提出 #48139371 (AC / 520 Byte / 1188 ms) は紆余曲折を反映して使っていない変数や意味のない処理が残っていたので整理した。提出 #48191813 (AC / 404 Byte / 725 ms)。最初にすっきり見通しが立っていれば 10 分で書けるようなスクリプトだ。かけた時間(72分)の言い訳はできない。■■■最近の結果をふりかえると取り組み方について考えてしまう。A 問題から順番に解くことについてだとか、考えを詰める前に実装を始めて迷走して結果的に初期のコーディング時間が無駄になっていることについて。コーディングをすることで細部が煮詰まっていったり誤りに気付いたりする側面があるので、一概にすぐに手を動かし始めることが無駄というわけではないんだけど、でも、コーディングという思考補助なしで考えを詰められるようになれば、将来的に時間が節約できるということがあるかも。30 分は手を動かさないとか、F 問題まで解法の最後まではっきりさせてからコーディングを始めるとか、落ちようがないくらい低成績の今だからこそやりやすい。