A - T or T
問題ページ : A - T or T
考察
$N \times A$と$B$の小さいほうを出力。
$if$文でも良いですが$min$関数もすっきりします。
コード
N, A, B = map(int, input().split())
print(min(N*A,B))
B - Good Distance
問題ページ : B - Good Distance
考察
$N,D \leq 10$なので全数計算で十分間に合います。
数$n$が平方数であるかは$int(\sqrt{n})$もしくは小数誤差も懸念して$int(\sqrt{n})+1$の自乗が$n$になるかで判定可能です。
コード
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
def check(n):
ret = False
for i in range(int(n**0.5)+2):
if i * i == n:
ret = True
return ret
ans = 0
for i in range(N-1):
for j in range(i+1,N):
dd = 0
for k in range(D):
dd += (X[i][k] - X[j][k]) ** 2
if check(dd):
ans += 1
print(ans)
C - Remainder Minimization 2019
問題ページ : C - Remainder Minimization 2019
考察
$$(i \times j)\ mod\ 2019 = (i\ mod\ 2019) \times (j\ mod\ 2019)$$
はよく使う計算法です。
$L \leq i,j \leq R$の区間が$2019$よりも大きな場合は必ず2019の倍数を含むので解は$0$。
$2019$よりも小さい場合は全数計算すれば良いですね。
コード
mod = 2019
L, R = map(int, input().split())
if R - L + 1 >= 2019:
print(0)
exit()
A = [x % mod for x in range(L,R+1)]
num = len(A)
ans = float("inf")
for i in range(num-1):
for j in range(i+1,num):
ans = min(ans, (A[i] * A[j]) % mod)
print(ans)
D - Rain Flows into Dams
問題ページ : D - Rain Flows into Dams
考察
問題文からいきなりコードを書くのは難しそうなので$N=5$の場合を考えてみます。
途中計算を簡略化するために各山iには$2x_{i}$の雨が降ったとします。各ダムiに貯まった水の量$A{i}$との関係は以下のようになります。
\begin{align}
x_1 \ + \ x_2 \ &= \ A_1 \tag{1}\\
x_2 \ + \ x_3 \ &= \ A_2 \tag{2}\\
x_3 \ + \ x_4 \ &= \ A_3 \tag{3}\\
x_4 \ + \ x_5 \ &= \ A_4 \tag{4}\\
x_5 \ + \ x_1 \ &= \ A_5 \tag{5}\\
\end{align}
変数$5$個に対して$5$個の連立一次方程式となりますので一意に解が決定します。
各式を$(1) - (2) + (3) - (4) + (5)$と交互に足し引きすると
$$2x_1 = A_1 - A_2 + A_3 - A_4 + A_5$$
となり$x_1$が求まります。
なお$(1)$式から$x_2 = A1 - x_1$として$(2)$式へ代入、以下同様に$(3)～(5)$式へ代入していっても同じ式が得られます。
あとは求まった$x_1$を$(2)$式へ代入し$x_2＄が求まり、これを$(3)へ代入し・・・、と順次計算していけば$x_1～x_5$がすべて求まります。
コード
N = int(input())
A = list(map(int, input().split()))
ans_half = [0] * N
ans = [0] * N
Z = 0
pol = 1
for i in range(N):
Z += pol * A[i]
pol *= -1
ans_half[0] = Z // 2
for i in range(1,N):
ans_half[i] = A[i-1] - ans_half[(i-1)]
for i in range(N):
ans[i] = 2 * ans_half[i]
print(*ans)
E - Virus Tree 2
問題ページ : E - Virus Tree 2
考察
任意の頂点を根として（コード上では頂点1を根としました）、根から各頂天へBFSで順次訪問し着色可能な色の数をかけていきます。
最初に根は$K$色任意の色を選べますが、それ以外の頂点は距離$2$以下の頂点と同色は選べないという制約を考慮する必要があります。
この制約は
・親と同色は選べない
・親の親（存在すれば）と同色は選べない
・すで着色された（訪問した）同じ親の子と同色は選べない
ということになります。
下図が具体例になります、
白抜きの文字がBFSの訪問順、赤字が選択できる色の数になります。
コード
mod = 10 ** 9 + 7
from collections import deque
N, K = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
a,b = map(int, input().split())
a -= 1
b -= 1
G[a].append(b)
G[b].append(a)
ans = K
v = [-1] * N
v[0] = 0
Q = deque([0])
while len(Q)>0:
x = Q.popleft()
if v[x] == 0:
para = 1
else:
para = 2
for nx in G[x]:
if v[nx] != -1:continue
v[nx] = v[x] + 1
Q.append(nx)
ans = (ans * (K-para)) % mod
para += 1
print(ans)
F -
問題ページ : F -
青色diff以上は後日挑戦