【ABC296】AtCoder Beginner Contest 296 A-D 振り返り【Python】

https://atcoder.jp/contests/abc296

A - Alternately

文字列Sを1文字ずつ順番に取り出し、前の文字を一致していれば No を出力する。すべて取り出すことに成功したら Yes と出力する。注意点として前の文字を空文字などで初期化する必要がある。

Python

n = int(input())
s = list(input())

pre = ""
for i, s_str in enumerate(s):
    if pre == s_str:
        print("No")
        exit()
    pre = s_str
print("Yes")

B - Chessboard

グリッドに相当する2次元配列を作成し、値が * になるまで要素を取り出し続ける。値が * の場合、行数をi, 列数をjとおく。アルファベットは chr() のメソッドで出力し、数字は 8-jを出力する。

Python

s_board = [list(input()) for i in range(8)]

# print(s_board)
for i in range(8):
    for j in range(8):
        if s_board[i][j] == "*":
            moji = chr(97 + j)  # chr(97) = a, chr(98) = b
            print(f"{str(moji)}{8-i}")

C - Gap Existence

$A_j$ を固定した場合、引き算の組み合わせは $N-1$ 個ある。また、条件を満たす値は $A_j + X$ なので、探索する組からこの値が存在しているかどうかを確認する。Pythonのリストの場合、存在確認は $O(N)$ なので $A_j$ を固定して繰り返す計算量を含めると$O(N^2)$ となり実行時間の制限に間に合わない。探索対象の組をsetにし、存在確認をすることで探索の計算量が $O(1)$ となるため計算量が全体で $O(N)$ となり実行時間に間に合う。

Python

n, x = map(int, input().split())
a_list = set(map(int, input().split()))

for pt in a_list:
    if pt + x in a_list:
        print("Yes")
        exit()
print("No")

D - M<=ab

コンテスト中は積の形で表される2つの整数を同時に考えず、1つを固定してもう1つを探索から外すことが重要だと感じた。片方を固定する考えがあれば実装は容易。

Python

N, M = map(int, input().split())

ans = 10**18

# a <= bを仮定する
for a in range(1, N + 1):
    b = M // a
    if not M % a == 0:  # 余りが発生した (掛け算してMに達しない) 場合は+1
        b += 1
    if b <= N:  # bはNを超えない
        ans = min(ans, a * b)
    if b < a:  # a<=b<=N に反する
        break

if ans == 10**18:
    print(-1)
else:
    print(ans)