/ 最近 .rdf 追記 編集 設定 本棚

脳log[20251004]



2025年10月04日 (土) [AtCoder] 精進。今日あった ABC426-F「Clearance」。どうやったら効率的に処理できるかいろいろ考えた。主に BIT とセグメント木をどう使うかを。遅延セグメント木で範囲減算をしながら値が負になる要素をトラップして都合良く扱えるだろうか。できそうになかった。商品ごとに要求量を BIT に積み上げていったらどのクエリまでなら在庫が足りるかがわかるだろうか。わかる。しかしここで商品ごとに足りないクエリを個別処理することは Q×N になっていけない。エンコードした在庫を BIT に乗せたら範囲和を取得したあとでクエリに固有の値を divmod 演算で取り出せないだろうか。足してから余りを取るのでなく余りを取ってから足さないといけないのでできない。それに値が大きくなりすぎる。じゃあ商品在庫が何クエリ分あるかを BIT に乗せたら……それでうまくやれるなら最初から素直に個数単位の在庫を BIT に乗せてやれるはずなのでできない。(単位はともかく)在庫を BIT に乗せるのでなく在庫が足りるか足りないかの二値を BIT に乗せるようにしたら……うまくいった。クエリに沿って在庫の有無を更新していく。要求量が k で十分な在庫がある商品が範囲内に c 種類あるなら、k*c 個の商品が買える。要求量に満たない端数は予め処理しておける。■提出 #69886664 (AC / 1693 Byte / 1813 ms)。長さが N だったり Q だったりする BIT が2本(※3本目はいつのまにかいらなくなっていたものの消し忘れ)と、同じような長さで入出力用とは別に配列を3本使っていることからわかるように、とてもたいへんだった。問題を縦に見て横に見て最後にまた縦に見てやっと答えが出る。■■■ABCD4完で水色に戻っていてびっくりした。前回までの ABC なら間違いなく 1100 台の緑パフォでしたよ。だって自分は何も変わっておらず(最近すっかり定着してしまった冴えないパフォーマンスしか発揮できておらず)、直近の8回中7回が 1000 から 1100 台の緑パフォだったんだから、今回も同等のパフォーマンスが出るのが当然だった。■解説を読んだら遅延セグメント木だった。負になる要素はトラップできるし、トラップした後はテキトーに大きい値を設定することで以降は無視できる。在庫切れ商品がどこにあるかは別途 BIT でもセグメント木ででも管理する。できそうにないと思ったことが実はできるらしかった。■提出 #69913286 (TLE×24/AC×14)。F 問題想定解法。予想はしてた。BIT で間に合うところはセグメント木より軽い BIT を使ったのだけど、5秒あってもあかんねんて。これが通るならかなり素直に貼るだけやるだけの問題になるんだけどな。セグメント木には最小値と最小値の位置とセグメントの幅を持たせた。幅1のセグメントにおける最小値というのはある商品の在庫そのものなので別に値を持つ必要がない。そして最小値の位置を記録しているので在庫が負になった商品がすぐにわかる。■■■G 問題「Range Knapsack Query」。kotatsugame さんの動画を見ました (「【競技プログラミング】ABC426【実況】 - YouTube」)。区間を区切って予め済ませておいた DP 結果をマージするというのは自分でも考えていた。テーブルのマージが C の2乗でも2つの結果をマージするときに (重み)=C となる結果を得るだけなら正順と逆順の結果を1対1対応させる線形時間で済ませられることもわかっていた。しかし区間の区切り方としてセグメント木を想定するとしても Sparse Table を想定するとしてもテーブルのマージは対数回発生するので2乗のマージを繰り返すしかない。動画を見て Disjoint Sparse Table について初めて名前を聞きました(「Disjoint Sparse Table [いかたこのたこつぼ]」)。そんなうまい話があるんですなあ。ちなみにアイテムの重みを低く抑えたランダムな最大ケースでローカルでは十数秒かかりました。事前に CNlogN (<150メガ) かかり、クエリに QC (≦100メガ) かかるので、Ruby には桁が1つ以上大きすぎる。それでいて5秒制限でもなんでもない2秒制限なのだ。解説 によると「全体の計算量は O(K(Q+NlogN)) です」「K=maxC_i」とのことなので、想定通りの計算量でこの時間らしい。1桁か2桁限定された制約に対して8割くらいの部分点が与えられたら受け入れやすいのにな。