GCJ Round1C 通過しました (1165位)
Round1Aで敢えなく撃沈し、Round1Bは深夜1時からの開催に耐えきれず不参加。今回迎えたRound1Cで無事突破することができました。
内訳としては1問目をvisible、hiddenともに解き、2問目を通し、3問目はDPだなーと思いながら撃沈しました。DP力が低すぎる。
この日は朝早起きしてかるたの練習に行き、帰ってきて昼寝して自転車のメンテナンスをするという充実の土曜日でした。 これはもう通過間違い無しと思いながら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()
Ant Stack
ナップザック問題だなぁと思いながら解いてたら解けませんでした。解説読みながら復習します。
DP力がまだまだ低いのでAtCoder typical DP contestも一緒に解いとくと良さそうですかね。