HUPC 2019 Day2 F: MOD Rush
0 likes182 views
2019/7/15 北海道大学プログラミング合宿 Day2 (有志セット: drken, idsigma, tempura0224, tsutaj, tubuann) F 問題 ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
HUPC 2019 Day2 F: MOD Rush
- 1. 北大合宿 2019 Day2 F: MOD Rush 原案: tempura 問題文: tsutaj 解答: idsigma?tempura?tsutaj?tubuann 解説: tsutaj 2019 年 7 月 15 日 tsutaj HUPC 2019 Day2 F 2019/7/15 1 / 7
- 2. 問題 MOD Rush 長さ N の正の整数列 A と、長さ M の正の整数列 B が与えられる 全ての (i, j) (1 ≤ i ≤ N, 1 ≤ j ≤ M) に対して、Ai を Bj で割った あまりを計算し、その和を求めよ 制約 1 ≤ N, M ≤ 2 × 105 1 ≤ Ai, Bj ≤ 2 × 105 tsutaj HUPC 2019 Day2 F 2019/7/15 2 / 7
- 3. 想定誤解法 O(NM) → Time Limit Exceeded tsutaj HUPC 2019 Day2 F 2019/7/15 3 / 7
- 4. アプローチ 剰余のまま考察するのは扱いにくいので、問題を言い換えよう そもそも剰余とは？ tsutaj HUPC 2019 Day2 F 2019/7/15 4 / 7
- 5. アプローチ 剰余のまま考察するのは扱いにくいので、問題を言い換えよう そもそも剰余とは？ X を Y で割ったあまりを求めたいとする X = pY + q の形で表すことができ、この時の q が剰余 p, q ∈ N ∪ {0} 0 ≤ q < Y 商が求められれば、X から商を Y 倍したものを引いて剰余が出せる tsutaj HUPC 2019 Day2 F 2019/7/15 4 / 7
- 6. アプローチ 剰余のまま考察するのは扱いにくいので、問題を言い換えよう そもそも剰余とは？ X を Y で割ったあまりを求めたいとする X = pY + q の形で表すことができ、この時の q が剰余 p, q ∈ N ∪ {0} 0 ≤ q < Y 商が求められれば、X から商を Y 倍したものを引いて剰余が出せる よって元の問題は次のように言い換えることができる tsutaj HUPC 2019 Day2 F 2019/7/15 4 / 7
- 7. アプローチ 剰余のまま考察するのは扱いにくいので、問題を言い換えよう そもそも剰余とは？ X を Y で割ったあまりを求めたいとする X = pY + q の形で表すことができ、この時の q が剰余 p, q ∈ N ∪ {0} 0 ≤ q < Y 商が求められれば、X から商を Y 倍したものを引いて剰余が出せる よって元の問題は次のように言い換えることができる MOD Rush の言い換え 正の整数列 A, B に対し、以下の操作を高速に実行せよ S ← M ∑ i Ai とおく 各 (i, j) に対して、p = ?Ai Bj ? を求め、S から p × Bj を引く 最終的に得られた S を出力 tsutaj HUPC 2019 Day2 F 2019/7/15 4 / 7
- 8. アプローチ どうすれば商を高速に求められるか？ tsutaj HUPC 2019 Day2 F 2019/7/15 5 / 7
- 9. アプローチ どうすれば商を高速に求められるか？ Bj をひとつ選びとったとき、Bj で割った商が p になるような Ai の 範囲は連続した区間になり、商の値によらず区間の長さは Bj 商が p であるような Ai は、p × Bj ≤ Ai < (p + 1) × Bj を満たすもの Pi :=「A 内に登場した数の中で値が i 以下であるものがいくつあるか」 という配列を用意しておけば、範囲内にあるものは O(1) で数えること ができる (いわゆる累積和) tsutaj HUPC 2019 Day2 F 2019/7/15 5 / 7
- 10. アプローチ どうすれば商を高速に求められるか？ Bj をひとつ選びとったとき、Bj で割った商が p になるような Ai の 範囲は連続した区間になり、商の値によらず区間の長さは Bj 商が p であるような Ai は、p × Bj ≤ Ai < (p + 1) × Bj を満たすもの Pi :=「A 内に登場した数の中で値が i 以下であるものがいくつあるか」 という配列を用意しておけば、範囲内にあるものは O(1) で数えること ができる (いわゆる累積和) X = max Ai とおくと、試す区間の数は ? X Bj ? 個 Bj が同じ値であればまとめて計算すれば良いことを考えると、B は 相異なるとみなしてよい 試すべき区間の数の合計は最大 ?X 1 ? + ?X 2 ? + · · · + ? X max Bi ? 個 tsutaj HUPC 2019 Day2 F 2019/7/15 5 / 7
- 11. アプローチ 区間の数の合計は最大 ?X 1 ? + ?X 2 ? + · · · + ? X max Bi ? ≈ X log X 個 調和級数と呼ばれるもの よって全ての (i, j) に対して商を求め、和にすることは高速に可能 これを利用すると剰余の部分だけ残すことができ、元の問題も高速に 処理可能 → Accepted tsutaj HUPC 2019 Day2 F 2019/7/15 6 / 7
- 12. Writer 解?統計 Writer 解 idsigma (C++?35 行?838 bytes) tempura (C++?37 行?652 bytes) tsutaj (C++?28 行?819 bytes) tubuann (C++?63 行?1638 bytes) 統計 AC / tried: 27 / 67 (40.3 %) First AC On-site: Tampaku (93 min 54 sec) On-line: ushitapunichiakun (8 min 16 sec) tsutaj HUPC 2019 Day2 F 2019/7/15 7 / 7