🍣

AtCoder ABC230 個人的メモ

2021/12/04に公開

Python

競技プログラミング

AtCoder

tech

A - AtCoder Quiz 3

ゼロ埋めはf-string使うのが好き

N = int(input())

if N >= 42:
    N += 1

print("AGC" + f"{N:03}")

B - Triple Metre

以下のように3パターンだけ調べればおｋ

例1の場合
oxxoxxoxxoxx : T
xoxxoxxo     : S
 xoxxoxxo    : Sを1文字右にずらした文字列
  xoxxoxxo   : Sを2文字右にずらした文字列(Tの部分文字列になってる)

公式解説のが簡潔で良さそう

S = input()

T = "oxx" * 10 ** 5
for i in range(3):
    if T[i:i + len(S)] == S:
        print("Yes")
        exit()

print("No")

C - X drawing

$N\times N$ のマス目をシミュレーションすれば良さそうだが、 $N\leq 10^{18}$ なので難しい。
$(Q-P+1)\times (S-T+1)\leq 3\times 10^5$ という制約から、出力するマス目の色をそれぞれ計算量 $O(1)$ で求めることができれば良さそう。
マス $(i,j)$ が黒く塗れるかはそれぞれの操作について以下のように判定できる。

$(i,j)=(A+k,B+k)$ となる $k$ が $max(1-A,1-B)\leq k\leq min(N-A,N-B)$ の範囲に存在する
$(i,j)=(A+k,B-k)$ となる $k$ が $max(1-A,B-N)\leq k\leq min(N-A,B-1)$ の範囲に存在する

よって、各 $(i,j)$ が上記2条件を満たすか満たさないかを判定すればおｋ

N, A, B = map(int, input().split())
P, Q, R, S = map(int, input().split())

for i in range(P, Q + 1):
    ans = []
    for j in range(R, S + 1):
        # 1つ目の操作で(i, j)が黒く塗られる場合
        if i - A == j - B and max(1 - A, 1 - B) <= i - A <= min(N - A, N - B):
            ans.append("#")
        # 2つ目の操作で(i, j)が黒く塗られる場合
        elif i - A == B - j and max(1 - A, B - N) <= i - A <= min(N - A, B - 1):
            ans.append("#")
        # いずれの操作でも(i, j)が黒く塗られない場合
        else:
            ans.append(".")

    print("".join(ans))

D - Destroyer Takahashi

1回のパンチで多くの壁を壊したい。
なので「破壊されていない壁で最小のRをパンチの範囲の左端としてパンチをする」という操作を全ての壁を破壊するまで繰り返せばおｋ。

from operator import itemgetter

N, D = map(int, input().split())
walls = [list(map(int, input().split())) for _ in range(N)]

walls.sort(key=itemgetter(1), reverse=True)
ans = 0
while walls:
    _, R = walls.pop()
    punch_range_right_i = R + D
    while walls:
        tmp_L, _ = walls[-1]
        if tmp_L < punch_range_right_i:
            walls.pop()
        else:
            break
    ans += 1

print(ans)

E - Fraction Floor Sum

N = int(input())

num_set = {0}
for i in range(1, int(N ** 0.5) + 1):
    num_set.add(i)
    num_set.add(N // i)

num_lst = sorted(num_set)
ans = 0
for i in range(1, len(num_lst)):
    ans += N // num_lst[i] * (num_lst[i] - num_lst[i - 1])

print(ans)