AtCoder 第二回日本最強プログラマー学生選手権 JSC2021 個人的メモ

所感

abcd4完

A - Competition

求める値をAとすると，

$$\frac{A}{Z}<\frac{Y}{X}\\ \ \\ A<\frac{YZ}{X}$$

上式より，この時のAの最大値は$\lceil \frac{YZ}{X}\rceil-1$となる．

X, Y, Z = map(int, input().split())

cal = -(-Z * Y // X) - 1
print(cal)

B - Xor of Sequences

2つの集合AとBの内，どちらかのみに出現する要素はAとBの排他的論理和(XOR)でおｋ．
最後にソートが要る．

_ = input()
A = set(map(int, input().split()))
B = set(map(int, input().split()))

print(*sorted(A ^ B))

C - Max GCD 2

解を全探索する．
解をcとした時，A以上B以下の範囲に$gcd(x,y)=c$となるx,yの組み合わせが存在するかを調べる．
そのためには，範囲内にcの倍数が2種類以上あるかを調べればおｋ．

A, B = map(int, input().split())

ans = 0
for i in range(1, B + 1):
    small = -(-A // i) * i
    large = B // i * i
    if A <= small <= B and A <= large <= B and small != large:
        ans = max(ans, i)

print(ans)

D - Nowhere P

最初の整数$A_1$は$1$以上$P-1$以下の数字から選べる．

$i$個目$(2\leq i\leq N)$の整数$A_i$の選び方を考える．
$A_i$を選んだ時，それ以前の要素の総和がPの倍数となる時，$m$を自然数として以下の式が成り立つ．

$$\begin{aligned} A_i + \sum_{j=1}^{i-1}A_j &= mP\\ A_i&=mP-\sum_{j=1}^{i-1}A_j \end{aligned}$$

この時，$1\leq A_i\leq P-1$より，$m$が取り得る値は1つだけである．
よって，i個目の整数$A_i$の選び方は$(P-1)-1=P-2$通りあると分かる．

N, P = map(int, input().split())
MOD = 10 ** 9 + 7

print((P - 1) * pow(P - 2, N - 1, MOD) % MOD)