GCJ Round1C 通過しました (1165位) - 天色グラフィティ

f:id:ejinote:20180506173658j:plain

Round1Aで敢えなく撃沈し、Round1Bは深夜1時からの開催に耐えきれず不参加。今回迎えたRound1Cで無事突破することができました。

内訳としては1問目をvisible、hiddenともに解き、2問目を通し、3問目はDPだなーと思いながら撃沈しました。DP力が低すぎる。

amalog.hateblo.jp

この日は朝早起きしてかるたの練習に行き、帰ってきて昼寝して自転車のメンテナンスをするという充実の土曜日でした。これはもう通過間違い無しと思いながらGCJに臨みました。ちなみに自転車はチェーンが錆びついてしまったので今度ちゃんと整備に出します。

振り返り

A Whole New Word

新しい単語が作れない=全パターンが網羅されている、なので、i文字目に関して文字の種類をカウントしておいて、総乗とNが等しいときは新しい単語は作れないと判断できる。

作れる場合はitertoolsで全パターン試したら通りました。GCJは比較的時間制限もメモリ制限もゆるい？のでいいですね。予選だけなのかな。

import operator
from functools import reduce
import itertools

def solve():
    N, L = map(int, input().split())
    chars = [set() for _ in range(L)]
    words = []
    for _ in range(N):
        word = input()
        words.append(word)
        for i, c in enumerate(word):
            chars[i] |= {c}
    if N==reduce(operator.mul, map(len, chars), 1):
        return '-'
    for word in itertools.product(*chars):
        w = ''.join(word)
        if w not in words:
            return w
            
if __name__=='__main__':
    T = int(input())
    for i in range(1, T+1):
        print('Case #{}: {}'.format(i, solve()))

Lolipop Shop

できるだけたくさんの人にロリポップを買って欲しい→ニッチなのを好む人にメジャーなやつを売るとダメそう、という思考で解きました。

それぞれのロリポップについて出現回数をカウントしておき、来店者の好みの中で最も出現回数の低いロリポップを売りつけつづける戦略です。

continueのつもりでbreakするいつものミスをやらかして2回REが生えました。

import sys

def solve():
    N = int(input())
    counter = {}
    remain = set(range(N))
    for i in range(N):
        pref = list(map(int, input().split()))
        D = pref[0]
        if D==-1:
            sys.exit(1)
        resp = None
        resp_cnt = float('inf')
        for j in range(D):
            p = pref[j+1]
            cnt = counter.get(p, 0) + 1
            counter[p] = cnt
            if cnt < resp_cnt and p in remain:
                resp = p
                resp_cnt = cnt
        if resp is None:
            print(-1, flush=True)
        else:
            print(resp, flush=True)
            remain.remove(resp)

if __name__=='__main__':
    T = int(input())
    for i in range(1, T+1):
        solve()