第二回日本最強プログラマー学生選手権参加記録

4完1ペナ 32分でした

A - Competition

数式で解いて $O(1)$ で求めることが可能ですが、コンテスト中は混乱していて、販売価格の二分探索をしました。

販売価格を $W$ としたとき、 $\frac{W}{Z} \lt \frac{Y}{X}$ より、 $W \lt \frac{YZ}{X}$ が成り立つ最大の非負整数を求めれば良いです。

B - Xor of Sequences

集合で言うと、 $(A \cup B) - (A \cap B)$ を求めれば良いです。

以下の要領で求められます。

N, M = map(int, input().split())
A = set(list(map(int, input().split())))
B = set(list(map(int, input().split())))
C = A.intersection(B) # 共通部分
D = A.union(B)  # 和集合
D.difference_update(C)
ans = list(D)
ans.sort()
print(*ans)

C - Max GCD 2

上手いやり方が思い浮かばなかったので約数を列挙する方針で解きました。

$A$ から $B$ までの各値の約数を求め、出現回数をカウントし、2回以上現れたもののうち最大を答えとすれば良いです。約数は $O(\sqrt{N})$ で求められるので、最悪計算量は $O(N\sqrt{N})$ です。

python で提出して TLE になり、pypy では間に合いました。

D - Nowhere P

$P$ の倍数かどうかを判定する際に、 $P$ で割ったあまりを見ると考えやすいです。

最初は $1$ 以上 $P-1$ 以下の数全てが候補になるので、 $P-1$ 通りあります。
次は、加算したあとに $P$ で割ったときのあまりが $0$ にならないように考えます。例えば $P = 6$ のとき、直前で $4$ を選んでいたとしたら、次に $2$ を選ぶことはできません。 $A_1 + A_2$ のあまりが $0$ にならないためには、最初に選んだ数字に対して、あまりが $0$ になるもの以外の $P-2$ 通りが候補になります。
その次は、 $A_1 + A_2 + A_3$ のあまりが $0$ にならないようにします。 $A_1 + A_2\ (\mathrm{mod}\ P)$ の値は $0$ でないので、状況的には一つ前と同じで、 $P-2$ 通りが候補になります。