Google Code Jam 2018: Round 1C

Python

Google Code Jam の第1ラウンド。

・予選のときの記事はこちら memo.sugyan.com

Round 1は時間制限が2時間半、3回行われてどこか1つで上位1,500人に入れば次に進める、というもの。 多分毎回ここで脱落していた

1Aは土曜日の早朝で起きられなくて断念、1Bは挑戦してみたものの全然正解できずに撃沈、最後の望みをかけて1Cに挑戦。

A Whole New Word

文字の並び換えで新しい単語を作る、もしくはもうすべて網羅されているか、を出力する。

どうやって解けばいいんだろう…とすごく悩んでしまった。 例えば最後の文字が3種類あったら 最後から2番目の文字は各種類 × 3回あらわれるはずで、それが2種類×3あったらさらに前の文字は各種類6回… となるはず、それより少なければそれは入力に含まれていない語がある、ということでそれを出力すればいい！ という感じで、それを愚直に書いた。

def solve(w, l):
    n = 1
    p = []
    for i in range(l):
        d = {}
        for c in [s[l - i - 1] for s in w]:
            d[c] = d.get(c, 0) + 1
        if i > 0:
            for k in d.keys():
                if d[k] < n:
                    for e in p:
                        a = set(p) - set([s[l - i:] for s in w if s[l - i - 1] == k])
                        a = k + list(a)[0]
                        if len(a) < l:
                            a = w[0][0:l - len(a)] + a
                        return a
        if i == 0:
            p = [x for x in d.keys()]
        else:
            p = [x + e for x in d.keys() for e in p]
        n *= len(set(d.keys()))
    if len(w) == n:
        return '-'


t = int(input())
for i in range(1, t + 1):
    n, l = [int(e) for e in input().split(' ')]
    words = []
    for _ in range(n):
        words.append(input().strip())
    ans = solve(words, l)
    print('Case #{:d}: {}'.format(i, ans))

これで1時間くらい使ってしまった…。でも一応これで両方とも通っていたようだ

Lollipop Shop

飴を買いに来る人に最適なものをオススメしてたくさん販売できるようインタラクティブに。

この種のものにまず挑戦したことがなかったので とりあえずtesting_tool.py を使って動かしてみて、適当に出力を返すようにして通るのを確認、提出してみるとWrong answerに。 適当に販売してたらダメかそりゃそうか、で改めて問題を読み直して 買われる傾向が決まっているっぽい、ということが分かる。 じゃあ売れやすいものはまた注文が来るかもしれないし、売れにくいものを優先で売るようにすればいいのか？ 候補を全部記録して、出現回数が少ないものを優先的に返すように変更。

終了2分前にギリギリで通った。

t = int(input())
for i in range(1, t + 1):
    n = int(input())
    f = set(range(n))
    s = {}
    for _ in range(n):
        c = []
        d = [int(x) for x in input().strip().split(' ')]
        for j in d[1:]:
            s[j] = s.get(j, 0) + 1
            if j in f:
                c.append(j)
        if len(c) > 0:
            m = min([s[j] for j in c])
            j = 0
            for k, v in s.items():
                if v == m and k in c:
                    j = k
                    break
            print(j)
            f.remove(j)
        else:
            print('-1')

Ant Stack

耐久重量が決まっている各蟻が前の蟻を乗せていって、最大幾つ積めるかを求める。

どういう形で積むのが最大になるかがなかなかイメージできなくて 幾つかテストケースを追加して考えてみる。 結局 途中n匹目までのところで「m段詰むと最軽量のものはw_mになる」というのを順番に計算していって 求められるかな…？と思って書いてみた。

def solve(w):
    d = {1: w[0]}
    for i in range(1, len(w)):
        dd = {1: set([w[i]])}
        for k, v in d.items():
            dd[k] = dd.get(k, set())
            dd[k].add(v)
            if v <= w[i] * 6:
                dd[k + 1] = dd.get(k + 1, set())
                dd[k + 1].add(v + w[i])
        d = {}
        for k, v in dd.items():
            d[k] = min(v)
    return max(d.keys())


t = int(input())
for i in range(1, t + 1):
    n = int(input())
    w = [int(x) for x in input().strip().split(' ', n)]
    ans = solve(w)
    print('Case #{}: {}'.format(i, ans))

Test set 1で通って安心してそのまま提出したけど、Test set 2ではTIME LIMIT EXCEEDEDになってしまっていた。 考慮が足りていなかったようだ…

結果

奇跡的に73ptで871位で通過できた、っぽい。嬉しい