ABC 356 E — Max/Min

考察

値域が10^6以下なので頻度とprefix和を作る。各pairを小値dと大値xへ向けると寄与はfloor(x/d)。同値はC(freq[d],2)として別計算し、異値は商qごとの正確なbucket [qd,(q+1)d−1]をx>dで切って数える。例えばd=2ではx=3の商1とx=4の商2は別bucketであり、d+1から幅dで区切る方法は誤る。q=1..floor(V/d)を列挙し、bucketの頻度をfreq[d]q倍して合計する。全dのbucket数は調和級数でO(V log V)。

典型の発動条件

整数商が一定の区間[qd,(q+1)d−1]を頻度prefix和で数える。最小値を固定してunordered pairの向きを一意にし、同値pairを組合せで分離する。

問題固有の要素

自己pairと同値要素の重複を避けるためx>dだけをbucket側で数え、x=dはC(freq[d],2)へ分ける。

正当性

各unordered pairは小値dと大値xで一意に向きを決められる。同値はC(freq[d],2)で別に数える。異値では商qの正確な区間[qd,(q+1)d−1]をx>dで切り、freq[d]·区間個数·qを足す。頻度prefix和は各bucketの個数を正確に返すので全pairのfloor(max/min)を一度数える。

実装上の注意

bucket lower=max(d+1,qd)、upper=min(V,(q+1)d−1)とする。lower>upperならskip。q=1の区間をd+1から始める場合でも上端は2d−1であり2dを含めない。答えは64bit。

復習の核

d=2,x=3,4の寄与が1,2へ分かれることを確認する。A=(2,4,4)の正答5と同値pairを一度だけ数える境界を復習する。

計算量と制約

時間

O(V log V+N)、V=max A≤10^6。調和級数個の商bucketを走査する。

空間

O(V)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1 \leq A_i \leq 10^6; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Max/Min の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 整数境界と同値区間を正確に分ける

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 整数境界・同値区間分割

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: 整数境界と同値区間を正確に分ける

      • floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。

      この解説で扱わないこと:

      • 素因数指数による整数条件の分解。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題