AtCoder Beginner Contest 099に事後参加してみた
ツイッターでいろいろ流れてきて面白そうだったので競技プログラミングサイトのAtCoderで問題を解き始めている。
手始めに直近のこれをやってみた：
コンテスト開催中に参加したわけではないのだが、とりあえずPythonで解いてみた。
第1問
横着してワンライナー。
print('AB' + ('D' if len(input())==4 else 'C'))
第2問
高さの法則性からB塔は（B-A）本目。塔の高さの差は雪の影響を受けない。
X本目の塔の高さは1..Xの和なので：
a, b = map(int, input().split()) d = b - a print(sum(range(1, d+1))-b)
第3問
コードを書くよりも、そもそものロジックが正しいかどうか納得するのが難しかった。つまり、6と9の乗数のうち、最大のもの二つだけを使って二分木的なDFSをするのが本当に正しいのか、という点。よく考えてみたが厳密に理解しているかは怪しかった・・・ 正解でよかったね、といったところ。
コード自体は単純明快。メモ化された二分木的な深さ優先探索。
from itertools import count, takewhile from functools import lru_cache @lru_cache(maxsize=None) def dfs(n): if n == 0: return 0 max9 = max(takewhile(lambda x: x<=n, (9**i for i in count()))) max6 = max(takewhile(lambda x: x<=n, (6**i for i in count()))) return min(dfs(n-max9), dfs(n-max6))+1 print(dfs(int(input())))
第4問
collections標準ライブラリのCounterを使っている以外は非常に愚直なコード。長いのがちょっと不満。計算量は入力に必要なO(N2)が最大。Counterを使っている部分はそのおかげでO(N2 * C)にならずにO(C2)で済んでいる。
from itertools import product from collections import Counter n, c = map(int, input().split()) color_costs = [list(map(int, input().split())) for _ in range(c)] matrix = [list(map(int, input().split())) for _ in range(n)] colord = {(i, j):cost for i, row in enumerate(color_costs) for j, cost in enumerate(row)} res = [] for n in range(3): color_count = Counter(c-1 for i, row in enumerate(matrix) for j, c in enumerate(row) if (i + j) % 3 == n) def color_cost(color): return sum(colord[ccolor, color] * ccount for ccolor, ccount in color_count.items()) cx = [(color, color_cost(color)) for color in range(c)] sorted_by_cost = sorted(cx, key=lambda x:x[1]) cheapest3 = sorted_by_cost[:3] res.append(cheapest3) color_pickss = product(*res) filtered_unique = (picks for picks in color_pickss if len(set(x[0] for x in picks)) == 3) costs = (sum(x[1] for x in picks) for picks in filtered_unique) print(min(costs))
感想
今まであまり乗り気ではなかったのだけど、やってみるとなかなか面白い。
少なくとも今回やった問題は、競技プログラミング用に無理やり最適化を施さなくても、Pythonでアルゴリズムをできるだけ明快に記述するつもりで書いても時間に抵触する恐れもなく解けた。（最大2000msのリミットに対して、最後のD問題だけ200ms、他は20ms付近）
動的計画法やグラフアルゴリズムなど、昔勉強したけど使わずに忘れているものを棚卸しするのにけっこういい運動だと思う。
次回のABCが二週間後のようなので、それに参加することを目的に過去問をどんどん解いていきたい。
