GCJ Qual.2017 - A

Google Code Jam

Google Code Jam Qualification Round 2017 に参加しました。
結果は A.Large, B.Large, C.Small2 まで通って50点でした。
予選は27時間とかなり長く、しかも25点以上取れれば予選通過だから時間に追われることなくゆっくり考えることができてよかったです。

今回はAだけで異様に長くなってしまったのでAだけです。

Problem A. Oversized Pancake Flipper

問題概要

  • 一列に裏か表のパンケーキがN個並んでいる
  • 1回の操作でちょうどK個の連続した区間のパンケーキを一斉にひっくり返すことができる
  • 有限回の操作で全てを表にできる場合、その最小回数を求めよ
  • 不可能ならIMPOSSIBLEと出力せよ

感想

個人的にはBよりこちらのほうが若干難易度が高いような気がしました
Smallを解く時点で既に本質的な気づきが無いと解けないので

ひっくり返せるのはちょうどK個の連続した区間なので、ひっくり返せる区間はN - K + 1個あります
このN - K + 1個の区間を1つ選んでひっくり返して、また1つ選んで……、とか考えてるととても解ける気がしません
問題を少し整理する必要があります

まず「操作の順序を変えても最終的な状態は変わらない」ということですね
これは各パンケーキの最終状態が
「何回ひっくり返されたか？（もう少し言うとひっくり返された回数の偶奇と初期状態）」
のみで定まるからですね
順序が関係無いので「ある区間が何回ひっくり返されたか？」だけが問題になることが分かります
そして、これが分かると「ある区間を2回以上ひっくり返すのは無駄である」ことも分かります
2回ひっくり返すと元の状態に戻るからですね

ここまで整理できると
「ある区間をひっくり返すか、ひっくり返さないか」
だけが問題になるということが分かりました

ということでSmallを解くにはN - K + 1個の区間の「ひっくり返す or ひっくり返さない」を全て試して(2^{N - K + 1}通り)、全て表になるものがあるならその中で最小回数を出せばいいということになります
Smallは高々N <= 10, 2 <= K <= Nなので、最悪でも2^(10 - 2 + 1) = 2^9 = 512通りを試すだけなので、この総当たりの解法で十分間に合います

総当たりのやり方として

の2種類あるかと思いますが、例えば再帰を用いた深さ優先探索ならこんな感じでしょうか

import sys

def solve():
    def dfs(i, cnt, S):
        if i == N - K + 1:
            if all(S):
                nonlocal ans
                ans = min(ans, cnt)
            return

        dfs(i + 1, cnt + 1, S[:i] + [si ^ 1 for si in S[i:i + K]] + S[i + K:])
        dfs(i + 1, cnt, S[:])

    T = int(sys.stdin.readline())

    for tc in range(T):
        S, K = sys.stdin.readline().split()
        S = [1 if ch == '+' else 0 for ch in S]
        K = int(K)
        N = len(S)

        ans = 1<<30

        dfs(0, 0, S[:])

        if ans == 1<<30:
            ans = 'IMPOSSIBLE'

        print('Case #{}: {}'.format(tc + 1, ans))

if __name__ == '__main__':
    solve()

iに今見ている区間の左端位置、cntに今までひっくり返した回数、Sが状態という感じです
iがN - K + 1までたどり着いたら、そのときの状態を調べて全て表になってたら答えの更新をします

こういう深さ優先探索で総当たりする方法は今まであんまりちゃんとやったことなくて最近身に着けた感じです

これは完全に余談になりますが、ABC057-Dが半分全列挙で解けるという裏技（？）があって、そのときにビットフラグを用いた全列挙はO(N * 2^N)かかってしまい間に合わないけれど深さ優先探索を用いた全列挙ならO(2^N)で済むから間に合うみたいな話があって、そのときに知りました
Submission #1185545 - AtCoder Beginner Contest 057 | AtCoder

それはともかく、Smallならこの全探索でO(N^2 * 2^N)ぐらいで解けるということなんですが、LargeはN = 1,000まであるので全探索では無理でもっと改善する必要があるということです

でもここからのステップアップはそんなに難しくなくて、単純に左端から見ていくと、もしそこが裏だったらそこから始まる区間は絶対ひっくり返さなきゃいけないし、既に表だったらそこから始まる区間は絶対ひっくり返してはいけない、という風にある区間をひっくり返すかひっくり返さないかが確定していくということが分かります
そうやって左端から見ていくとN - K + 1個目までは表になっていることは明らかですが、それより右にあるパンケーキがどうなっているかは分からないです
なので右にあるパンケーキの状態を調べて、もし裏があればこれはどうしようもないですから不可能ということになります
全て表になっていれば、実際にひっくり返した回数が答えとなります

これを愚直に実装しても計算量はO(N^2)まで落ちて、これは十分速いアルゴリズムです

import sys

def solve():
    T = int(sys.stdin.readline())

    for tc in range(T):
        S, K = sys.stdin.readline().split()
        S = [1 if ch == '+' else 0 for ch in S]

        K = int(K)
        N = len(S)

        cnt = 0

        for i in range(N - K + 1):
            if S[i] == 0:
                S[i:i + K] = [i ^ 1 for i in S[i:i + K]]
                cnt += 1

        for i in range(N - K + 1, N):
            if S[i] == 0:
                ans = 'IMPOSSIBLE'
                break
        else:
            ans = cnt

        print('Case #{}: {}'.format(tc + 1, ans))

if __name__ == '__main__':
    solve()

さも分かったように書いてますが、これ別に左端からじゃなくてもいいんですよね。
例えば右端のパンケーキの状態を見てひっくり返すかどうか決めて……ってやっていってもよいわけですよね。
そうしたときに左端から、と右端から、の結果が本当に変わらないのか、例えば左端からやっていくと無理となったが、右端からやると可能になってしまったとか、左端からやるとx回だったけど、右端からやるとy(< x)回になってしまったとか、そういうことがありそうな気がしませんか？

実際はこれで通るし、想定解もこの方法なのでそんなことはあり得ないのですが、これに対する厳密な証明ができてなくて困っていました。

ですがこれを書いてる中で考えが整理されてきたのでそれを書きます。

まず、「全てを表にする操作全体の集合」を考えて、これをAとします
次に、「左端からN - K + 1個全てを表にする操作全体の集合」を考えて、これをBとします
「全てを表にする操作」は明らかに「左端からN - K + 1個を全て表にする操作」でもあるので、このことからA ⊂ B という包含関係が成り立っていることが分かります

ところで、左端からN - K + 1個全てを表にする操作は上の手法で一意に定まることが示されました。
つまりBの要素は1つしかないということです。

故に、この操作が全てを表にする操作であればA = Bとなり、全てを表にする操作も一意に定まることになり、この操作が全てを表にする操作でないならば、A = {}、つまり空集合となり、全てを表にする操作は存在しないことが分かります。

よって上記で書いたようなことは起こり得ないということになりますね、これでスッキリしました。

ちなみに愚直にひっくり返す操作をシミュレートしていっても間に合いますが、O(N)でやる方法もあるみたいです。
解説に乗ってるように「そこがひっくり返された回数の偶奇」が分かればそのパンケーキをひっくり返すべきか否かが分かるのでわざわざシミュレートしなくてもよいということになります。
ただし、区間の長さKを超えるとひっくり返された回数が1減るのでそれをメモしておく配列を別に作ってやる必要があるとのことです、配列を走査しながらimos法をするみたいな感じですかね。

偶奇だけ分かればよいので排他的論理和を使って書くと以下のような感じになります。

import sys

def solve():
    T = int(sys.stdin.readline())

    for tc in range(T):
        S, K = sys.stdin.readline().split()
        S = [1 if ch == '+' else 0 for ch in S]
        K = int(K)
        N = len(S)

        ans = 0
        v = 0

        memo = [0] * (N + 1)

        for i in range(N - K + 1):
            v ^= memo[i]

            if S[i] ^ v == 0:
                ans += 1
                v ^= 1
                memo[i + K] = 1

        for i in range(N - K + 1, N):
            v ^= memo[i]

            if S[i] ^ v == 0:
                ans = 'IMPOSSIBLE'
                break

        print('Case #{}: {}'.format(tc + 1, ans))

if __name__ == '__main__':
    solve()

今回の肝は

  • 最終状態が操作の順序に依らない
  • ある区間を2回ひっくり返す意味は無い

ということですね、どちらも分かってしまえばそんなに難しくないことですが、これに気づかないとなかなか解けない問題なのではないかと思います。そういう面でBの方が簡単だったんじゃないかなあと思いました。

私がこれに気づいたのも過去に似たような問題を解いたことがあるからでしょうか。
http://codeforces.com/contest/776/problem/D
この問題もボタンを押す順序を考えると凄くややこしいけど、単にボタンを押すか押さないかの問題であると分かるとすんなりとまではいかないものの、見通しよく解ける問題という感じでした。
どうやら蟻本にも似たような問題が載っているらしいので、汎用性の高い考え方なんでしょうね。
しっかり身に着けておきたい考え方だと思いました。