naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉700点問題(ARC 060 E, 068 E)

700点問題埋めるぞ〜
なんか急に難しくなってきたw

8月13日

ARC 060 E - 高橋くんとホテル (700)

N(=1e5)軒のホテルがそれぞれ座標 x_1,...,x_N に一直線に並んでいて、一日に距離Lだけ進むことができる高橋くんがあるホテル a からあるホテル b に行き着くのに何日かかるかというクエリをQ=1e5本こなす問題。
1回のクエリの計算量をO(logN)とかO(√N)とかのレベルにまで落とすことができるか。

  • 各ホテルから1日で行き着ける最遠ホテルを求めるのはO(logN)で出来る。これは簡単。
    • こうして求めた配列を使って、2日で行き着ける最遠ホテルを求めるのはO(1)で出来る。(2ステップするだけ)
      • 1日目で既に最後のホテルに到達してしまうならなにか門番的な値(0ベースならN、1ベースならN+1とか)を入れておく
    • 同様に4日で、8日で、…、2^(R-1)日で行き着ける最遠ホテルを求めておくとすると、全部でO(log^2 N) だ
    • 高々R=17段なのでメモリ的には問題ない
  • こうして準備したテーブルで、aからbへの旅路をどう高速に求めるか
    • aから1日,2日,4日,8日,...の項を見ていって、bそのものかbに一番近い所(a')まで移動する。bそのものに到達したらそこでおしまい。
    • a'から同様に1日,2日,4日,8日,...と見ていく。
      • 最後に、どうしてもbそのものにたどり着けない(bを越えてしまう)なら工程数に+1を足しておしまい。
    • この計算量は整数を2進表記するコストみたいな感じ。O(logN)?O(log^2 N)?
  • いずれにせよ間に合う

→RE 1:07
https://beta.atcoder.jp/contests/arc060/submissions/3001359
あ?
ああ、前計算の段数をけちってるせいだ(Nが2の累乗ジャストの時に死ぬ)
一箇所、ループの<N<=Nに直して
→AC 1:11
https://beta.atcoder.jp/contests/arc060/submissions/3001372
時間かかっちゃったけど自力で解けて嬉しい

解説より

大体解説解も同じなんだけど、前計算のテーブルを1日,2日,4日,8日,...と見ていかなくても二分探索でやるといいよね(O(log log N)だ)

…ダブリングにより…

そうかこういう前計算テーブルの作り方は「ダブリング」というのか
(いや、蟻本にも載ってるってよ…そろそろ蟻本を読み返したら学びが多いかも)

8月14日

ARC 068 E - Snuke Line (700)

区間がN=最大3e5個与えられて、d(1〜M=1e5)の倍数が含まれている区間の個数を1〜Mについてそれぞれ返すクエリ問題。
40分以上かかったけど自力で方針思いついた。

  • 区間[li, ri]をx=1〜√Mで割っていって、得られた区間 [ceil(li/x),floor(ri/x)] を追加していく。この区間が有効なら、割った数xについても(未登録なら)[x, x] を追加。
    • 区間が [lo, hi] なら, a[lo]++, a[hi+1]--
    • √Mがジャストの数かそうでないかで境界条件に注意。
  • imos
  • 計算量は O(N√M)
    • 3e5×√1e5 = 9.48e7だし間に合うでしょ
  • あれー最悪ケースで4.7sかかる
    • どこで時間食ってるんだろう(ループを何度も見返す)
    • もしかして入力?(30万行とか読むし)
    • cin を scanf に変えたら2s切った
    • よし出すぞ

→AC 1'35'34''
https://beta.atcoder.jp/contests/arc068/submissions/3006776
一発AC嬉しい。(そしてサーバ上では1197ms)
ぎりぎり時間内(=Eだけに取り組んでたら取れた)

解説よむ

O((MlogM + N)logM) らしいんだけど...
Fenwick Tree(フェニック木/Binary Indexed Tree (BIT))を使えとな。

  • 区間の幅(inclusive)がwなら、d≦wなdは必ず1回以上訪れるというのは自明
    • d=wのときは1回
    • d>wのとき、1回も訪れることができない可能性がある
      • そこまでは分かる
  • 区間を幅ごとに分類しておいて
    • dを1〜Mまで回しながら
    • 初めてd≧wになった区間を何か(Fenwick Tree等)に追加(1加算)
      • Fenwick Treeへの区間追加でO(logM)なら、全部でN区間あるからO(NlogM)か
    • dの倍数を全て調べる
      • 各dについてdの倍数を全て調べる計算量って...M/1+M/2+...+M/M = M(1+1/2+1/3+...) = O(MlogM) か。それにFenwick Treeのクエリの計算量(O(logM)か)を掛けてO(M log^2M)
    • 合計O((MlogM + N)logM)。なるほど

後で解説の解き方でもやってみるか

Fenwick Tree (Binary Indexed Tree, BIT)

区間への加算も Fenwick Tree 等を用いることで 1 回あたり O(log M) で行うことが可能です.

簡単に言えば

  • Segment Treeのメモリ効率を良くしたやつ
  • 長さNの配列 v[] があるとして
    • v_i=v_i+w\displaystyle\sum_{i=a}^{b}v_i をO(logN)で出来る
    • しかも必要なのは長さNの配列のみで、実装もシンプル
      • 1ベースの方が実装がしやすいけど0ベースもまあ書ける

区間 [a,b) に+wするにはFenwick Treeを2本用意して(p,qとする)

  • p.add(a,+w); p.add(b,-w);
  • q.add(a, -wa); q.add(b, +wb);

これで区間 [0,c) の合計が p.sum(0,c) * c + q.sum(0, c) で求まる。
(例えば、aが0とcの間にあるとしたら、求めたい [0,c)の合計は(c-a)w = cw-awである。p.sum()=w, q.sum()=-wa なので、w * c - wa = (c-a)w といい感じに補正されている。)
→AC
https://beta.atcoder.jp/contests/arc068/submissions/3008242
(サーバ上で370ms。速い)