競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
今回の敗因
あっ、日曜もやってたんだ？
コンテストの存在を知らなかった。日程を見てなかった。
というわけで、コンテスト終了後に問題を解いてます。
A - A?C
atcoder社は毎週土曜日にコンテストを開催しているそうです。次回はABCとARCのどちらが開催されるか答える問題です。
入力が'ABC'なら'ARC'を出力。違ったら'ABC'を出力しましょう。
S = input()
if S == 'ABC':
print('ARC')
else:
print('ABC')
B - Trick or Treat
K種類のお菓子がそれぞれ番号$\boldsymbol{A_k}$の子供に配られます。お菓子を受け取っていない子供は何人いるか答える問題です。
それぞれの配列の要素を合わせて重複を取り除き、「お菓子が配られた人数」を調べて全体の人数から引けばいいと思います。
N, K = map(int, input().split())
A = []
for _ in range(K):
d = input()
A += list(map(int, input().split()))
print(N - len(set(A)))
↓は毎回set型に突っ込んでみたパターン。こっちの方が早かった。
N, K = map(int, input().split())
A = set()
for _ in range(K):
d = input()
A = A.union(set(map(int, input().split())))
print(N - len(A))
C - Peaks
「自身と隣接している全ての展望台より高い」という条件を満たしている展望台が何個あるか答える問題です。
グラフ問題...のように見えますが、そんなに難しいことを考える必要はないでしょう。隣接した展望台が自分以上の高さを持つならFalse。持たないならTrue。最後にTrueの数を調べて出力しました。
「同じ高さ」を持つ展望台は共にFalseなことに注意。
N, M = map(int, input().split())
H = list(map(int, input().split()))
good = [True] * N
for _ in range(M):
A, B = map(int, input().split())
A -= 1
B -= 1
if H[A] >= H[B]:
good[B] = False
if H[A] <= H[B]:
good[A] = False
print(sum(good))
D - I hate Factorization
$$ A^5 - B^5 = X $$
を満たす整数の組(A, B)を一つ出力する問題です。
$X \leq 10^9$という制限を満たすための$A, B$はどのくらい範囲を取ればいいのでしょうか。5乗して$10^9$を超える数は？
n = 1
while n**5 < 10**9:
n += 1
print(n)
# 64
適当にこの倍ほど範囲を取って全探索してみます。
import itertools
X = int(input())
for a, b in itertools.product(range(128), range(-128, 128)):
if(a ** 5 - b ** 5 == X):
print(a, b)
break
通っちゃいました。
解説を見たところ、
$$ n^5 - (n-1)^5 \geq 10^9 $$
を満たす$n$,つまり$n=120$までを探索する...と考えるのが正しいようです。結果オーライですがちゃんと考えるようにしましょう。あとはこの計算が通る限り、できるだけ広い範囲を探索しちゃうのも手ですね。
E - This Message Will Self-Destruct in 5s
「このメッセージは5秒後に自動的に消滅する」。
$A_i + A_j = j-i$を満たす数を答える問題です。
itertools.combinations_with_replacement()で全網羅しました。TLEになりました。
import itertools
N = int(input())
A = list(map(int, input().split()))
count = sum([j-i == A[i-1]+A[j-1] for i, j in itertools.combinations_with_replacement(range(1, N+1), 2)])
print(count)
わからなくてギブアップ。解説を見ます。$O(n^2)$から逃れることはできるんでしょうか？
$$ A_i + A_j = j-i $$
$$ ↓ $$
$$A_i + i = j-A_j $$
できました。それぞれの値について独立なステータスを計算すればいいと。
値$A_i$に対して、$L_i = i + A_i$, $R_i = i - A_i$という値を計算します。$R$と$L$にそれぞれどの値が何個入っているのか数えれば$L_i = R_j$となる組み合わせの数を計算できます。
というわけで以下のコードで実装しました。
import collections
N = int(input())
A = list(map(int, input().split()))
L = [i + A[i] for i in range(N)]
R = [i - A[i] for i in range(N)]
countL = collections.Counter(L)
countR = collections.Counter(R)
print(sum([countL[n] * countR[n] for n in countL.keys()]))
この記事はここまでとします。