AtCoder Beginner Contest 096に事後参加してみた
今日も今日とてAtCoder ABCを解く。
第１問
1月1日、2月2日、10月10日といったようにX月X日のようになっている日が年始からa月b日までに何日あったかを数える問題。
a, b = map(int, input().split()) print(a-(a>b))
ブール値が1と0に評価されることを利用している。各月に一回月と日が一致する日があり、その日を過ぎているかどうかをa > bで判定している。
第２問
a, b, cの整数のいずれかを二倍に変えるという操作をk回行い、和を最大化する問題。
a, b, c = sorted(map(int, input().split())) k = int(input()) print(a+b+(c*(2**k)))
当然一番でかい数字をk回二倍にして足し合わせるのが最大。
第３問
隣接した二つのマスを黒く塗りつぶすという操作のみで、特定の白黒のパターンを再現できるか判定する問題。
h, w = map(int, input().split()) s = [input() for _ in range(h)] d = {(i, j):c for i, row in enumerate(s) for j, c in enumerate(row)} def next_to_black(i, j): directions = ((-1, 0), (1, 0), (0, -1), (0, 1)) surroundings = ((i + a, j + b) for a, b in directions) colors = (d.get(cell, '.') for cell in surroundings) return any(color == '#' for color in colors) black_coords = (coord for coord, c in d.items() if c == '#') paintable = all(next_to_black(*coord) for coord in black_coords) print('Yes' if paintable else 'No')
塗るべきパターンの黒いマスを列挙して、その周りの四つのマスのいずれかが黒いか判定する、というロジックをそのまま記述するだけ。
dictionary comprehensionとenumerateを使って座標と値のdictionaryを一行で作れるのが地味にうれしい。
第４問
どの５つをとって足しても合成数になるユニークなn個の素数のリストを作成する問題。
全部１で終わる数字なら５つとって足し合わせると確実に5の倍数になる。エラトステネスの篩を作って小さい順に１で終わる素数をn個取り出すだけ。
from itertools import count, islice def eratosthenes(): d = {} for q in count(2): p = d.pop(q, None) if p: x = next(x for x in count(q + p, p) if x not in d) d[x] = p else: yield q d[q*q] = q n = int(input()) ones = (prime for prime in eratosthenes() if prime % 10 == 1) n_ones = islice(ones, n) print(' '.join(map(str, n_ones)))
素数をつくる関数が定義されていればロジックは最後の三行でまとめられてしまう。
そういえば素数のリストを作成する関数が標準ライブラリに入っていないのはちょっと不思議だろうか？あまり汎用性がないという判断なのかな。他の言語でも標準ライブラリに入っているという話はあまり聞かないかも。
