Google Code Jam 2008 QR Problem A

先日予選が行われたGoogle Code Jam 2008 予選ですが、無事ラウンド1 へ進出できたようです。

ラウンド1 は3つのサブラウンドに別れ、参加者は3つのサブラウンドのうち2つまでに参加し、それぞれのラウンドで上位840人、合計で2520人が次のステージに進むことができます。このラウンドからコンテストの時間が2時間になるのでなんとか勝ち抜けるように頑張りたいと思います。

さて、そんなこんなで突破した予選や練習問題・ベータ問題について、復習も兼ねて解説を試みたいと思います。今日は予選のA問題 "Saving the Universe" です。

予選で提出したコードは下の通りです。

#! /opt/local/bin/python
# -*- coding: utf8 -*-

def do_calc(num_engine, query):
    change = 0
    flags = [0] * num_engine

    for q in query:
        flags[q] = 1
        if flags.count(0) == 0:
            flags = [0] * num_engine
            flags[q] = 1
            change += 1

    return change


def main():
    for c in range(input()):
        dic_engine = {}
        query = []
        num_engine = input()

        for i in range(num_engine):
            tmp_str= raw_input()
            dic_engine[tmp_str] = i

        num_query = input()

        for i in range(num_query):
            str_query = raw_input()
            query.append(dic_engine[str_query])

        change = do_calc(num_engine,query)
 
        print 'Case #%d: %d' % ( c+1, change )

if __name__ == '__main__':
    main()

予選が終わって IRC #gcj や google-codejam ではDPだDPなんて話になっていましたが、検索エンジンごとにフラグを作り、全てのフラグが立った瞬間が検索エンジンの切り替え時とみなして数えあげるというアルゴリズムです。フラグ立ては美少女ゲーマーの人が得意ですね(謎)

予選では、検索エンジンを切り替えた時の flags[q] = 1 の部分を忘れてSmall Input を処理して、1 wrong try を出してしまいました。また、パースするときについでに検索エンジンやクエリーを数字に置き換えていったのですが、この程度のものではそこまでしなくても問題が出なかったかもしれません。数字に置き換えたことで見通しのよいコードになったので、それなりの意義はあったと思います。

人数的には正解者が一番多いのがこの問題だったわけですが、このようなコードを24時間内に提出し、Small / Large の両データセットを処理すればいいわけですから、予選を通過することそのものはそんなに難しくはなかったのかもしれません。