脳log[20230701]

2023年07月01日 (土) [AtCoder] 今日は CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)があった。コンテスト成績証。今日は F 問題までこれというところのない、つまりは典型的な問題ばかりだった。G 問題は TLE 解しか書けなかった。コンテストの途中から終了後しばらくの現在まで AtCoder にアクセスすると必ず 403 Forbidden が返ってきて、即座にリロードすると正常に表示されるという状態が続いている。とても面倒。以下 A-F のふりかえり。■A 問題「New Scheme」。PAST のはじめの方にでも出てきそうな問題。書かれていることを愚直に実装する。■B 問題「Default Price」。これも愚直に実装する。まだ効率を考えなければいけないような制約ではない。これに５分の時間をかけてしまった理由は入力の受け取りに失敗していたことに気がつくまでの時間。だって AtCoder で色っていったら数字で与えられるのが常なんだもん。■C 問題「Standings」。たぶん分数を浮動小数点数で扱っても AC になるのかなあ、C 問題だし(追記：ツイッターを眺めてるとダメっぽい)。一応 sort メソッドに比較関数を渡して通分してから分子を比較するようにした。浮動小数点数って特殊で使用場所を選ぶものっていう認識で、整数で間に合うところで使うものではないと思ってる。なお JavaScript……。■D 問題「Snuke Maze」。素直にグリッドを探索する。同じマスを二度処理しないようにするなら BFS でも DFS でもいいだろう。再帰関数を使わないで書くなら違いはキューから shift で出すか pop で出すかの違いしかない。■E 問題「MEX」。いいかげん MEX という概念を認知するくらいには MEX を問題で見る機会が増えてきたけど、やっぱり「いずれとも一致しない最小の非負整数」みたいに否定で定義されるのは脳に負荷がかかる。この解法を DP と呼ぶのかな。M の字が出現した状態はその値が 0,1,2 である場合の３通りがある。ME の２字が出現した状態は(0,1,2)×(0,1,2)の９通りが考えられるけど、MEX への影響という観点では M(0)E(1) と M(1)E(0) を区別する意味がない。３桁のビットフラグで８通り持てば十分(ただし、0b000 と 0b111 は０通りに決まってるので意味があるのは６要素)。ところでこの問題の典型要素に「３つのうち真ん中に注目する」があったらしいが気がつかなかった。そういえば ARC160-B「Triple Pair」もそうだったけど真ん中を固定できなかったな>20230514。次からは典型として注目できるといい。■F 問題「Voucher」。ソートすれば貪欲に無駄なくクーポンが利用できそう。何をソートしようか。必ずこうでなければいけないという必然の選択はなんだろう。高額商品は使えるクーポンの幅が広いので低額商品から優先的にクーポンを割り当てたい。あるいは最低価格の設定が高いクーポンは利用機会が限られるのでできるだけ優先的に使用したい。でもクーポンが余るような時に最低価格設定が高いからといって値引きの渋いクーポンを使いたくはない。どうしましょ。低額商品から順番にクーポンを割り当てる。プライオリティキューで使えるクーポンを管理しておいて値引き額が最高のクーポンから順に使用していく。一度使用可能になったクーポンはその後ずっと使用可能だからできる。kotatsugame さんの動画を見ていて言及されていたので思い出したけど、クーポンの値引き額が商品価格を超えないことを制約で確認している。もし値引き額が商品価格によってキャップされてしまうなら常に最大の値引きクーポンを利用するのが最適ではなくなってくるので。もしそんなことがあれば DP でもしてすべての可能性を考えないと答えが出せないと思う。■G 問題「Minimum Xor Pair Query」。解けてないよ。黒板に書かれている数字をプリフィックスで分類しておきたいなと思った。数字は 30 ビット幅の範囲なんだけど、たとえば 29 ビット分のプリフィックスが共通する数字が２つ以上あったら、30 ビット分のプリフィックスが共通するものがないとしたら、答えは１に決まっている。できるだけ長い共通プリフィックスを見つけることが答えを出す最初の一歩だと思った。たぶん TLE なのは次の一歩が愚直組み合わせだからなのだろう。見つかった共通プリフィックスが短いほど組み合わせがやばい。プリフィックスを取り除いて MSB を無視して再帰的にプリフィックスで分類していくのだろうか。難しい、っていうかややこしいよ。プログラムの概形が見えない。今の TLE 提出の段階でもややこしくて配列に逃げたんだけど、配列の非効率的な操作が TLE の(唯一の)原因だったら嬉しいなあ。３要素以上の組み合わせを考えることってなくない？ ３要素あるならより長い共通プリフィックスが見つかると思う。じゃあ最長の共通プリフィックスを効率良く見つけるのに失敗してるな。最長の共通プリフィックスを見つける算段は立ったと思うけど、それが b ビットの長さだとすると最大で 2^b 組の XOR から最小値を見つけるのはどうすれば？ SortedMultiSet があれば考えることもないけど(ないんだな)。■■■G 問題。間接的に解説を読みました。「整数集合から2つ選んだXORの最小は整列させた隣り合う数のXORのどれか」 うん、そうだね。できるだけ長い共通プリフィックスを持つ２数は隣り合う数字だね。バイナリ表現と数としての評価が繋がらなかったんだよ。あと条件を緩和する発想もなかなか出て来にくいと思う。隣接する２数の中には最長の共通プリフィックスを持つものもあるけど、そうでないものも当然ある。だけど区別する必要がないし、区別しない方が処理しやすい。■■■G 問題結果報告。■１.平衡二分探索木がない言語の頼れる味方 BIT を使ったもの>提出 #43153261 (TLE×23)。XOR した値が 30 ビット整数の範囲でどういう値をとるかわからないから BIT の実装に Hash を使っている。これはお時間やばめ。■２.XOR した値に対しては Hash 実装の BIT のままだけどクエリ先読みができる x については Array 実装の BIT を使った。あと必ず効果があるものではないけどクエリ１と２の処理をクエリ３が来るまで遅延させて同一の x に対する処理がまとまるようにした。提出 #43229129 (TLE×14)。■３.XOR した値に関して Hash BIT の代わりに削除可能なプライオリティキューを使うようにした。提出 #43229096 (AC / 2342 ms)。削除可能なヒープの実装が『アルゴリズムとデータ構造』(メールホルン, サンダース)の課題にあったと思うんだけどどう実装するのか知らなかった。だけどこの前比較可能なキーだけを突っ込めるプライオリティキューにひと皮かぶせてキーに値を関連付ける方法を hmmnrst さんの提出 #42277952 で知ったので、キーに個数を関連付けて削除とするのは簡単だった。ヒープへの出し入れは定数倍が重いので節約術(２個目以降の同一キーはヒープに入れない)としても個数の管理を役立てていきたいと思う。もうひとつ。初めて見る prepend メソッドの使用例でもあった。これは継承を操作するメソッドで、自分が持つ言葉のイメージとは裏腹に prepend されたモジュールは継承階層の末端側に配置される。反対のメソッドは append ではなくて include らしい。そちらはよく知っているが目から鱗の発見でもあった。include↔prepend なのか。prepend は Ruby が 1.9 の頃にはなくて 2.3 の時にはもうあったメソッドらしい。ところで自分の提出では prepend も継承も使っていない。オーバーライドされた親クラスのメソッドを呼び出す方法が見つからなかったからだ。具体的には PQ2#head メソッドの中で、オーバーライドしている PQ2#deq メソッドではなく PQ#deq メソッドを呼び出したかった。同名のメソッドなら super で呼び出せるけど。C++ には明示する文法があるんだけど。図らずも「(可能ならいつでも)継承よりコンポジション」を別の理由から確認する結果になった。たぶん Ruby での方法は alias だけど、あまりにも姑息なやり方だと思う。■４.これは解説を読む前に作っていた「最長の共通プリフィックスを見つける算段は立ったと思うけど、それが b ビットの長さだとすると最大で 2^b 組の XOR から最小値を見つけるのはどうすれば？ SortedMultiSet があれば考えることもないけど(ないんだな)。」と書いていた頃のもの。2^b 組について愚直に全件調べているが意外に健闘した>提出 #43229224 (TLE×14)。