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()]))

この記事はここまでとします。