GCJ 2017 (Qualification Round) - 日々ｄｒｄｒする人のメモ

Google Code Jam 2017のQualification Roundに参加した。
Dashboard - Qualification Round 2017 - Google Code Jam

25pts取れば通過できる。A,B,Cのlargeまで解いて65pts取った。

以下、自分の雑な解法。

A. Oversized Pancake Flipper

${S}$ 個の連続したパンケーキが与えられる。パンケーキの一方はhappy-side('+')でもう一方がblank-side('-')である。K個の連続したパンケーキをひっくり返せるフリッパーを使って、 ${S}$ 個のパンケーキ全てをhappy-sideにする。その最小回数を求める問題。
Smallは ${2 \le |S| \le 10}$ , Largeは ${2 \le |S| \le 1000}$ 。

貪欲に、前からblank-sideのパンケーキをひっくり返していくことにした。計算量 ${O(N^2)}$ でLargeまで対応できる。

for _ in xrange(input()):
    print "Case #%d:" % (_+1),
    s, k = raw_input().split()
    s = [c is '+' for c in s]
    k = int(k)
    l = len(s)
    ans = 0
    for i in xrange(l-k+1):
        if s[i] == 0:
            for j in xrange(k):
                s[i+j] ^= 1
            ans += 1
    print ans if sum(s)==l else "IMPOSSIBLE"

B. Tidy Numbers

1から ${N}$ の中で、桁が昇順に並んでいる数字(224488など)の内で最大になるものを求める問題。
Smallは ${1 \le N \le 1000}$ , Largeは ${1 \le N \le 10^{18}}$ 。

数字のある桁について、Nより小さくなる桁が存在した場合、それ以降の桁は全て9で埋めれる。
このことを利用し、DFSで(桁数, Nより小さいか)を持ちながら条件を満たす数字を求め、この中から最大の数字を求めた。
計算量は ${O(N^{\log_{10} 2})}$ で、Largeまで対応できる。

for _ in xrange(input()):
    print "Case #%d:" % (_+1),
    n = raw_input()
    l = len(n)
    nn = map(int, n)

    def dfs(c, less, st):
        if c == l:
            return int(st)
        if less:
            v = dfs(c+1, 1, st + '9')
        else:
            v = 0
            if c == l-1 or nn[c] <= nn[c+1]:
                v = max(v, dfs(c+1, 0, st + n[c]))
            if c == 0 or nn[c-1] <= nn[c]-1:
                v = max(v, dfs(c+1, 1, st + str(nn[c]-1)))
        return v
    print dfs(0, 0, "")

C. Bathroom Stalls

N個の連続したbathroomがあって、K人がbathroomに入ろうとしている。
bathroomに以下のルールで選択し、入浴する。ここでbathroom Sの左側から連続して空いているbathroomの数を ${L_S}$ とする。同様に右側について ${R_S}$ とする。

${\min(L_S, R_S)}$ が最大となる ${S}$ を選ぶ。
選べる ${S}$ が複数ある場合、その中から ${\max(L_S, R_S)}$ が最大となる ${S}$ を選ぶ
これでも選べる ${S}$ が複数ある場合、最も左の ${S}$ を選ぶ

このルールを適用した結果、K人目が選ぶ ${S}$ について ${\max(L_S, R_S)}$ , ${\min(L_S, R_S)}$ を求める問題

Small1は ${1 \le N \le 1000}$ 、Small2は ${1 \le N \le 10^6}$ 、Largeは ${1 \le N \le 10^{18}}$

ここでは、連続して空いているbathroomの左端から右端までを一つの区間として考えていく。

このルールでは、最も長い区間の中の、その中央のbathroomを選んでいくことになる。例えば、長さ4の区間と長さ5の区間が存在した場合、長さ5の区間の中央のbathroomを選ぶことになる (そして、長さ2の区間が2つ生成されることになる)。

そのため、長い区間から順番にその中央のbathroomを選び、区間を分割していくことをシミュレーションすればよいことになる。

Small1,2ならば、PriorityQueue使えば ${O(K \log K)}$ でできそうだと思ってPythonで実装したら、Small2で3分で計算が終わらなかった。そこでバケットを利用し、大きい区間から順番に、同じ区間をまとめて処理することによって ${O(N)}$ で計算したらSmall2も間に合った。

def small(n, k):
    bucket = [0]*(n+1)
    bucket[n] = 1
    for i in xrange(n, -1, -1):
        if bucket[i] > 0:
            if k <= bucket[i]:
                n = i
                break
            else:
                k -= bucket[i]
                if i % 2 == 1:
                    bucket[i/2] += bucket[i]*2
                else:
                    bucket[i/2] += bucket[i]
                    bucket[i/2-1] += bucket[i]
    if n % 2 == 1:
        return n/2, n/2
    else:
        return n/2, n/2-1

for _ in xrange(input()):
    print "Case #%d:" % (_+1),
    n, k = map(int, raw_input().split())
    print "%d %d" % small(n, k)

ここで区間の長さについてよく考えてみると、区間の長さは ${N, N/2, N/2-1, N/4, N/4-1, \ldots}$ しか出現せず、高々 ${2 \log N}$ 個しかなさそうなことに気付く。(これは帰納的に証明できそう)
それを考慮すると ${O(\log N)}$ で解けて、Largeも解けた。

def large(n, k):
    bucket = {}
    bucket[n] = 1
    i = n
    st = n
    while 1:
        if bucket[i] > 0:
            if k <= bucket[i]:
                n = i
                break
            else:
                k -= bucket[i]
                if i % 2 == 1:
                    bucket[i/2] = bucket.get(i/2, 0) + bucket[i]*2
                else:
                    bucket[i/2] = bucket.get(i/2, 0) + bucket[i]
                    bucket[i/2-1] = bucket.get(i/2-1, 0) + bucket[i]
            if i-1 in bucket:
                i -= 1
            else:
                i = st / 2
                st = i
    if n % 2 == 1:
        return n/2, n/2
    else:
        return n/2, n/2-1

for _ in xrange(input()):
    print "Case #%d:" % (_+1),
    n, k = map(int, raw_input().split())
    print "%d %d" % large(n, k)