AtCoder Beginner Contest 139 に参加した。今回は ABCD 4 完答 の 1699 位でパフォーマンスは 1091 だった。
以下のコードは PyPy3 (2.4.0) で AC を確認している。
問題 A
入力の \(S, T\) の各要素が一致する個数を数え上げる。
# PyPy3 (2.4.0)
S = input()
T = input()
ans = 0
for i in range(3):
if S[i] == T[i]:
ans += 1
print(ans)
問題 B
電源タップを一つ追加すると、差し引きして \(A - 1\) だけ差込口が増えるので、その和が \(B\) 以上になるまで調べる。ただし \(B = 1\) の場合は何も追加する必要がないので注意する。
# PyPy3 (2.4.0)
A, B = map(int, input().split())
if B == 1:
print(0)
exit()
count = 1
remain = B - A
while remain > 0:
count += 1
remain -= (A - 1)
print(count)
問題 C
一つ前の高さを憶えておいて、
ansを \(0\) から始める- 今の高さが一つ前の高さ以下ならカウントアップ
- 今の高さが一つ前の高さより高いならカウンタをリセット
- カウンタのリセット前に必要に応じて
ansを更新する
- カウンタのリセット前に必要に応じて
のように前から処理していけば \(O(N)\) で処理できる。
# PyPy3 (2.4.0)
N = int(input())
H = list(map(int, input().split()))
ans = 0
last = H[0]
count = 0
for i in range(1, N):
if last >= H[i]:
count += 1
else:
ans = max(ans, count)
count = 0
last = H[i]
if i == N - 1:
ans = max(ans, count)
print(ans)
問題 D
\(\bmod\) を取ると法の値より小さくなるので、一番大きくなる候補は各法 \(1, \ldots, N\) から \(1\) を引いた場合の総和になる。つまり
$$\sum_{i=0}^{N-1} i$$
従って解の候補は \((N - 1) \times N / 2\) となる。
次に、実際にそのような組み合わせが構成可能であるかを考える。
- \(P_1 = N\)
- \(P_i = i - 1, 2 \leq i \leq N\)
とすればよい。
# PyPy3 (2.4.0)
N = int(input())
print((N - 1) * N // 2)
問題 E
まずは対戦表を埋めていけばいいと考えて愚直に実装していたがバグが取り切れず。