ABC024復習 - 俵言

昨日のABC024に参加しました。

<a href="http://abc024.contest.atcoder.jp/">Welcome to AtCoder Beginner Contest 024 - AtCoder Beginner Contest 024 | AtCoder</a>abc024.contest.atcoder.jp

前回(ABC023)に比べるとオーダーの制約は優しかったんですけど、Dが解けなくて残念。でも逆元の話とか勉強になりました。

A - 動物園

動物園の一人当たりの料金(こどもA円、大人B円)が与えられるので、こどもがS人、大人がT人だったときの料金を求める問題。

団体割引さえちゃんと考慮すれば特に問題ないです。

A, B, C, K = map(int,raw_input().split(" "))
S, T = map(int,raw_input().split(" "))
print S * A + T * B - (0 if S + T < K else C * (S+T))

B - 自動ドア

N人のお客さんそれぞれが店を訪れる時刻と自動ドアが開いてから閉まるまでの時間が与えられるので、自動ドアが空いていた合計時間を求める問題。

こういう問題は時間をインデックスにとる配列を埋めていく解法がわかりやすいんですが、制約が $1 \leq A_i \leq 10^6$ , $1 \leq T \leq 10^5$ なのでつらいです。 $10^6 + 10^5 = 1.1 \times 10^6$ の大きさの配列とかなめるだけでTLEの気配が漂ってきますわ。解説の満点解法も $10^6+T$ だけfor文回すので、python的にはギリギリな感じ。

そもそも最初から配列を使う必要は無くて、

f:id:Tawara:20150524032206p:plain

i人目のお客さんが来たときに

まだドアが開いていれば、被っている時間(赤い部分)をTから引いた分だけ加算する
ドアが閉じていればTだけ時間を加算する

という方針で行きました。(図がでかい(^_^;;)) これなら計算量O(N)なのでpythonでも問題なく通ります。

N, T = map(int,raw_input().split(" "))
total = 0
time = 0
for i in range(N):
    A = int(raw_input())
    if A > time:
        total += T
    else:
        total += A + T - time
    time = A + T
print total

あとからよくよく考えると, 自動ドアが開き続ける時間Tが一定だからこんなにシンプルに書けてるんだなあと。ドアの開き続ける時間がバラバラだと、もう少しだけ工夫が必要ですね。

(追記) 解説放送でimos法でやったってコメントがあったのでやってみました。

N, T = map(int,raw_input().split(" "))
MAX = 10**6+T
time = [0 for i in range(MAX+1)]
for i in range(N):
    A = int(raw_input())
    time[A-1] += 1
    time[A+T-1] -= 1
for i in range(MAX):
    time[i+1] += time[i]
print sum(map(bool, time))

計算量はO(10**6+T)、時間は1206msでした。上の配列を使わない方法は376ms。オーダーが一桁違うだけで大分違いますね。

C - 民族大移動

それぞれの民族が目的の街に移動できる一番早い日を答える問題。

幸いにして大移動が行われる日数Dと民族の数Kの制約が $1 \le D \le 10^4, 1 \le K \le 100$ だったため、難しいこと考えずに民族ごとに何日でたどり着けるか求めれば大丈夫でした。さっさと愚直に解いたら良かったorz

解説では貪欲に解けるって話をされていて、言われてみればそうだなって感じです。まあやってたときはそこまで考えが至らなかったので、民族iが現在移動できる範囲 $B_i$ とその日の移動できる範囲 $B_{day}$ について

$B_i \cap B_{day} \neq \emptyset$ であれば、移動できる範囲を $B_i =B_i \cup B_{day}$ に更新
$B_i \cap B_{day} = \emptyset$ なら $B_i$ を更新しない

という操作を繰り返し、 $B_i$ を更新したときに $T(目的地) \in B_i$ であればOKという方針でやっています。

N, D, K = map(int,raw_input().split(" "))
LR = [map(int,raw_input().split(" ")) for i in range(D)]
for i in range(K):
    S, T = map(int,raw_input().split(" "))
    move_L = S
    move_R = S
    for day in range(D):
        L, R = LR[day]
        if L <= move_L <= R or L <= move_R <= R:
            move_L = min(L, move_L)
            move_R = max(R, move_R)
            if move_L <= T <= move_R:
                break
    print day + 1

貪欲な方法もあとからやってみました。

def move_right(S,T):
    H = S
    for day in range(D):
        if LR[day][0] <= H <= LR[day][1]:
            H = LR[day][1]
            if S < T <= H:
                break
    return day + 1
    
def move_left(S,T):
    H = S
    for day in range(D):
        if LR[day][0] <= H <= LR[day][1]:
            H = LR[day][0]
            if H <= T < S:
                break
    return day + 1

N, D, K = map(int,raw_input().split(" "))
LR = [map(int,raw_input().split(" ")) for i in range(D)]
for i in range(K):
    S, T = map(int,raw_input().split(" "))
    print move_right(S, T) if S < T else move_left(S, T)

わざわざmove_leftとmove_right作ってるんですが、pythonはif文が遅いのでこれが大分効いてます。ちなみに範囲でやる方が680ms, 貪欲の方が360msでした。

D - 動的計画法

高橋君が破いてしまった紙が、動的計画法で埋めたマス目の何処に当たるかを探す問題。

最初二分探索で頑張ろうとしてたりしたんですけど、10⁸以上の階乗が必要になってきてどうしようってずっと悩んでました。あとから方程式で求めれるって気付いたときにはもう手遅れ。けど逆元の事分かってなかったのでどっちにしろ無理だったと思います。

(0,0)から(r,c)への右と上にだけ進める場合の行き方が $_{r+c}C_r$ であるので, 入力A, B, Cより

$_{r+c}C_r = A \Leftrightarrow \displaystyle \frac{(r+c)!}{r!c!} = A \ \ \ \ \ \ \ \ \cdots (1) \\ _{r+c}C_r = B \Leftrightarrow \displaystyle \frac{(r+c+1)!}{r!(c+1)!} = B \ \ \cdots (2) \\ _{r+c}C_r = C \Leftrightarrow \displaystyle \frac{(r+c+1)!}{(r+1)!c!} = C \ \cdots (3)$

(1)と(2), (2)と(3)を組み合わせて、

$\displaystyle \frac{r+c+1}{c+1} = \frac{B}{A} \\ \displaystyle \frac{r+1}{c+1} = \frac{B}{C}$

この連立方程式を解いたものがこちら。

$\displaystyle r = \frac{BC - AC}{AC - BC + AB} \\ \displaystyle c = \frac{BC - AB}{AC - BC + AB}$

右辺を $10^9+7$ でmodをとったものが答えになるの実は少し納得いってないんですが、時間がないので割愛。

で、今回一番勉強になったのは逆元の話でした。 $A \equiv a, B \equiv b, C \equiv c$ であったとき,

$A \div B = C \Rightarrow a \times (bの逆元) \equiv c$

が成り立つというもの。加減乗算に関してはmodとっても大丈夫だと知ってましたが、除算だとこんなことするんですね。そしてこの逆元ですが、法が素数pであった場合はフェルマーの小定理により

$X^{p-1} \equiv 1 \\ \therefore X^{-1} \equiv X^{p-2}$

が成り立つそうです。 $10^9+7$ は素数なので使うことが出来ます。

そしてもう一つ勉強になったのは冪乗を高速に求めるアルゴリズム。解説聞いたときにピンと来てなかったんですが、あとから納得しました。

$X^N$ を求めるときに、Nの二進数表示を考えると、

$X^N = \prod_i X^{2^i}$

の形に分解できることを利用してます。例えばN = 11 なら二進表記は1011なので

$X^N = X^{2^0} \times X^{2^1} \times X^{2^3}$

に分解できるわけですね、なるほどなるほど。これを利用すれば $X^{p-2}$ を高速で求められるのでXの逆元を求めれます。

def mod_inv(X, N):
    result = 1
    prod = X
    inc = 0
    while (1<<inc) <= N:
        if (N>>inc) % 2 == 1:
            result = (result * prod) % p
        prod = (prod**2) % p
        inc += 1
    return result % p

A = int(raw_input())
B = int(raw_input())
C = int(raw_input())
p = 10**9+7
r_nume = (B*C - A*C) % p 
c_nume = (B*C - A*B) % p
deno = mod_inv((A*C - B*C + A*B) % p, p-2)
print (r_nume * deno) % p, (c_nume * deno) % p

因みにpythonのpow関数は $X^a \ \% \ b$ を求めてくれる超便利機能があって、

A = int(raw_input())
B = int(raw_input())
C = int(raw_input())
p = 10**9+7
r_nume = (B*C - A*C) % p 
c_nume = (B*C - A*B) % p
deno = pow((A*C - B*C + A*B) % p, p-2, p)
print (r_nume * deno) % p, (c_nume * deno) % p

と書けちゃいます。ただ冪乗の高速計算は他でも使えそうな知識なので覚えていて損はなさそうです。

次のABCこそは全完目指したいなあ。