日々drdrする人のメモ

今日もdrdr、明日もdrdr

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}とする。

  1.  {\min(L_S, R_S)}が最大となる {S}を選ぶ。
  2. 選べる {S}が複数ある場合、その中から {\max(L_S, R_S)}が最大となる {S}を選ぶ
  3. これでも選べる {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)