Codeforces Rounds #361 (Div. 2)
http://codeforces.com/contest/689
- A. Mike and Cellphone
- B. Mile and Shortcuts
- C. Mike and Chocolate Thieves
- D. Friend and Subsequences
- E. Mike and Geometry Problem
A. Mike and Cellphone
問題
与えられた電話番号に対して、入力するときの指の動きが同じ電話番号は存在するか。
解法
(dy, dx) ずらして正しく入力できるかを判定すればいい。
B. Mile and Shortcuts
問題
N個の交差点が一直線上に並んでいる。交差点 i からは交差点 i-1, i+1, a[i] にコスト 1 で移動できる。交差点 0 から交差点 i への最短コストをすべての i に対して求めよ。
- 1≦n≦200,000
解法
i→i-1 の移動がなければ単純な DP で解けるが、i→i-1 があるので幅優先探索をする必要がある。
C. Mike and Chocolate Thieves
問題
A≧1, B≧2, AB3≦n を満たすような (A,B) がちょうど m 通りになるような最小の n を求めよ。存在しないなら -1 を出力すること。
- 1≦m≦1015
解法
f(k) を n=k としたときのパターン数とする。このとき f(k) は単調増加するので f(k)≧mとなる最小の k を二分探索で求められる。では f(k) はどう求めればいいだろうか。
(A,AB,ABB,ABBB) というパターンを (A,B) に対応させる。このとき AB3≦n≦1017 (なぜn≦1017なのかは後述) より B≦106 であるから B を 1..106 まで for で回す。B を固定したときに A が取りうるパターン数は m/B3 であるから 106*O(1) で計算できる。
二分探索の初期値ミスに注意。$n/8 \le f(n) \approx \sum_{i=2}^{\infty} n/i^3 \le n$ より $f(10^{17}) \ge 10^{15}$ なので 1017 を初期値にしておけば問題ない。
D. Friend and Subsequences
問題
同じ長さの 2 つの数列 A, B が与えられる。max(A[l],...,A[r])=min(B[l],...,B[r]) となるような (l,r) は何通りあるか。
- 1≦n≦200,000
- -109≦A[i],B[i]≦109
解法
左端を L に固定して右端が何通りあるかを O(log n) 程度で数えられれば解ける。
新しく関数を次のように定義する。
- F(R):=max(A[L],...,A[R])
- G(R):=min(B[L],...,B[R])
F(R) は単調増加で G(R) は単調減少になる。
そのため F(R)≧G(R) となる最小の R と F(R)>G(R) となる最小の R が二分探索で求められて、この 2 つを使えば F(R)=G(R) となる R の個数が求められる。
F(R) と G(R) の計算はセグメント木を使えば O(log n) で計算できる。とは言うものの微妙に TLE しかねないので sparse table で書いた方が無難だと思う。
区間 [l,r] を幅 2k の区間に分解するというのが sparse table のアイディア。
各 i を左端とする幅 1,2,4,8,... の区間の min を O(n log n) で前計算しておくことでクエリ一回あたり O(1) で処理できるようになる。
k も前計算して配列に入れておく。__buildin_clz を使っても計算できるが、速度差がどの程度あるのかは調べてない。
E. Mike and Geometry Problem
問題
N 個の区間 [l[i], r[i]] が与えられる。n個の区間から k 個選ぶすべてのパターンに対して区間の共通部分の長さを計算し、その総和を求めよ。
- 1≦N≦200,000
解法
点 i が何回カウントされるかを数えて、その総和を取ればいい。点 i が何回カウントされるかは点 i を覆う区間の数さえ分かれば計算できる。点 i を覆う区間の数は座標圧縮 + いもす法で効率的に計算できる。