roiti46's blog

主に競プロ問題の解説を載せてます

Google Code Jam 2015 Qualification Round: C. Dijkstra

Dijkstraにijkが含まれるのに気付かされた問題。

問題はこちら

問題

iとjとkからなる式を与えられる(長さLの文字列をX回繰り返したもの)。これらは四元数(wikipedia)であり、四元数の計算規則が適用される。与えられた式を3つの部分に分ける。それぞれの部分を計算規則に従って簡約していくことで最終的に ijk にすることができるかどうかを答えよ。

解法

!!!以前の解法では簡約の仕方が問題文とは違い、正しい答えを出力しない可能性がありました。ご注意ください!!!

!!!以前の解法ではX > 4のときX = 4+X%4にしても結果は変わらないとしていましたが反例が見つかりました!!!

四元数からなる計算式なので Ln+4m = Ln となる。この性質を利用して調べると X > 8 ならば、 X = 8+X%4 としても結果は変わらないことが伺える。あとは式を前から計算していき、i ができたら次は j ができるまで計算し、j ができたら残りの式を計算し、残った値がkならば"YES"を、そうでなければ"NO"を出力すればいい。分配の法則より、この方法で答えを得ることができる。

sign_ref = { "1": 1,  "i": 1,  "j": 1,  "k": 1,
            "11": 1, "1i": 1, "1j": 1, "1k": 1,
            "i1": 1, "ii":-1, "ij": 1, "ik":-1,
            "j1": 1, "ji":-1, "jj":-1, "jk": 1,
            "k1": 1, "ki": 1, "kj":-1, "kk":-1}

mul = { "1":"1",  "i":"i",  "j":"j",  "k":"k",
       "11":"1", "1i":"i", "1j":"j", "1k":"k",
       "i1":"i", "ii":"1", "ij":"k", "ik":"j",
       "j1":"j", "ji":"k", "jj":"1", "jk":"i",
       "k1":"k", "ki":"j", "kj":"i", "kk":"1"}

T = int(raw_input())
for loop in xrange(T):
    L, X = map(int, raw_input().split())
    if X > 8: X = 8+X%4
    S = raw_input()*X

    sign = 1
    e = ""
    char = "i"
    for i in xrange(L*X):
        sign *= sign_ref[e+S[i]]
        e = mul[e+S[i]]
        if char != "k" and e == char and sign == 1:
            char = {"i":"j", "j":"k"}[char]
            e = ""

    judge = (e == char == "k" and sign == 1)
    print "Case #%d: %s"%(loop+1, "YES" if judge else "NO")

以下は以前の間違っていた解法です。頭からijkを作っていってますが、3つの部分に分けて簡約していないので S = jjijkjj のような"NO"と出力すべき時に"YES"と出力してしまいます。(climpetさん、ご指摘ありがとうございます)

また X = 4+X%4では、L = 4, X = 10, S = jikjのようなケースで本来"YES"と出力すべき時に"NO"と出力してしまいます。(これもclimpetさん、ご指摘ありがとうございます)

sign_ref = { "1": 1,  "i": 1,  "j": 1,  "k": 1,
            "11": 1, "1i": 1, "1j": 1, "1k": 1,
            "i1": 1, "ii":-1, "ij": 1, "ik":-1,
            "j1": 1, "ji":-1, "jj":-1, "jk": 1,
            "k1": 1, "ki": 1, "kj":-1, "kk":-1}

mul = { "1":"1",  "i":"i",  "j":"j",  "k":"k",
       "11":"1", "1i":"i", "1j":"j", "1k":"k",
       "i1":"i", "ii":"1", "ij":"k", "ik":"j",
       "j1":"j", "ji":"k", "jj":"1", "jk":"i",
       "k1":"k", "ki":"j", "kj":"i", "kk":"1"}

T = int(raw_input())
for loop in xrange(T):
    L, X = map(int, raw_input().split())
    if X > 4: X = 4+X%4
    S = raw_input()
    S = S*X
    sign = 1

    make = {"i":False, "j":False, "k":False}
    sp = 0
    for char in "ijk":
        e = ""
        for i in xrange(sp, L*X):
            sign *= sign_ref[e+S[i]]
            e = mul[e+S[i]]
            if e == char:
                make[char] = True
                sp = i+1
                break
        else:
            break

    e = S[sp] if sp < L*X else "1"
    for i in xrange(sp+1, L*X):
        sign *= sign_ref[e+S[i]]
        e = mul[e+S[i]]

    judge = all(make[char] for char in "ijk") and sign == 1 and e == "1"
    print "Case #%d: %s"%(loop+1, "YES" if judge else "NO")

まとめ

本番はsmall、largeともに通ったがただ運が良かっただけのようだ。 提出する前に問題を軽く見直す習慣が必要かもしれない。 この問題のおかげでDijkstraのスペルミスをしなくなりそうな気がする