More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
立命合宿2016顿补测3：贬问题
- 1. RUPC2016 2016/03/08 RUPC2016 Day3 H: われわれの努力について 1 原案：井上 解説：井上? 問題文：井上 解答：井上
- 2. RUPC2016 2016/03/08 問題概要 ? 長さNの順列pが与えられる ? Q個のクエリ li, ri が与えられるので、それ ぞれについて inv(li,ri) を答えよ ? inv(l,r) := | { (i,j) | pi>pj かつ l≤i<j≤r} | ? 制約: 1≤N≤100,000, 1≤Q≤200,000 2
- 3. RUPC2016 2016/03/08 問題背景 ? D問題原案提出時の僕? 「こんなんセグ木とかでちょちょいと? やればO(logN) でクエリ答えられるやろ」 ? RUPC1週間前の僕? 「えっ、これむずない？」 3
- 4. RUPC2016 2016/03/08 解法のアイデア ? 「転倒数 クエリ」検索? ↓ ? 今日の典型データ構造(解答編) - よすぽの日記 ? http://yosupo.hatenablog.com/entry/ 2015/03/31/000740 ? これはbit列の話 4
- 5. RUPC2016 2016/03/08 解法のアイデア ? IJPC 2012 #1: 魔法の訓練 ? http://japl.pl/contest/ijpc/1/reviews/ training.html ? 転倒数クエリに答える問題 ? この問題では値の変更もある ? O( (N+Q) √N logN ) 解法が書かれている ? 平方分割 + BIT + 転倒数を数えるルーチン ? JAPLJ is GOD 5
- 6. RUPC2016 2016/03/08 われわれのつらみ ? O( (N+Q) √N logN ) 解法を実装する ? ゆうてね、O(√N logN) はね、遅いよね ? D問題のジャッジに組み込むが、クエリが律速 になってNを大きくできない? → O(N2) がTLEしない…… 6
- 7. RUPC2016 2016/03/08 われわれの努力 ? 「inversion range query」検索 ? stack overflow がヒット ? http://stackoverflow.com/questions/ 21763392/counting-inversions-in-ranges ? 神によりO( N+Q √N ) 解法が提案されている ? 平方分割内の計算を頑張ってlogを落とす ? radix sort + merge sort でlogを落とす 7
- 8. RUPC2016 2016/03/08 われわれの本当の努力 ? 平方分割サイズの調整 ? 配列を使い回してメモリ削減 ? 事前計算できるとこを計算する (N<Qなので) ? できるだけ long long を使わない ? 小さいケース (長さは<=600くらい) だと僕が 下手な radix sort 書くより std::sort の方 が速いのでそれを使う 8