Hard No.51 : D - Knight
発想
$(+1, +2)$への移動回数を$n$とします。$(+2, +1)$への移動回数を$m$とします。このときどちらの方向に進んでもマンハッタン距離は3になります。よって$(X, Y)$までのマンハッタン距離が3で割り切れなければ、答えは0です。さらに、$n,m$は
n = 2Y-X\geq0\\
m = 2X-Y\geq0
が成り立ちます。よって$n<0$または$m<0$の場合の答えは0です。
あとは、同じものをそれぞれ$n,m$個含む順列
\frac{(n+m)!}{n!m!}
を計算しますが、これは$_{n+m}C_n$に等しいです。
実装
$_{n+m}C_n$の計算はHard No.49 : D – Bouquetの解説と同じように計算をします。
X, Y = map(int, input().split())
mod = 10**9 + 7
d = X+Y
if d % 3 != 0:
print(0)
exit()
n = (2*Y - X)//3
m = (2*X - Y)//3
if n < 0 or m < 0:
print(0)
exit()
a, b = 1, 1
for i in range(n):
a = a*(n+m-i) % mod
b = b*(i+1) % mod
else:
ans = (a*pow(b, mod-2, mod))%mod
print(ans)
Hard No.52 : D - Partition
発想
$a_1$から$a_N$まで全て同じ値である時に最大公約数（gcd)は最大値を取ります。その値は$M$を$N$で割った商（$g_{max}$）になります。よって1から$g_{max}$まで全探索すれば答えを求められますが、TLEしてしまいます。何かもうひとつgcdに関する条件が欲しいです。ここでgcdを$g$とおいて、a_i$が
a_i = x_i×g
のように表せるとすると
M = sum(x)×g
と表せるので、gcdは$M$の約数であることが分かります。$M$の約数は$O(\sqrt{N})$で求められますから、$M$の約数を全探索することでTLEせずに答えを求めることができます。
実装
N, M = map(int, input().split())
def divisor(n):
i = 1
table = []
while i * i <= n:
if n%i == 0:
table.append(i)
table.append(n//i)
i += 1
table = list(set(table))
return table
maxg = M//N
GCD = sorted(divisor(M))
for gcd in GCD:
if gcd > maxg:
break
if (M - gcd*(N-1)) % gcd == 0:
ans = gcd
print(ans)
ちなみにgcdが$M$の約数であることに気づかずに1から$g_{max}$まで全探索すると、テストケースのうちTLEするのは1つだけでした。このケースは明らかに$N=1,{ \ }M=10^9$ですので、このケースだけ狙い撃ちした悪い子もACします。
N, M = map(int, input().split())
maxg = M//N + 1
if N == 1 and M == 10**9:
print(10**9)
exit()
for i in range(1, maxg):
if (M - i*(N-1)) % i == 0:
ans = i
print(ans)
Hard No.53 : B - Picking Up
発想
よくよく読めば2点の$x$座標、$y$座標それぞれの差が$p$、$q$であるときにコストが0になります。$N$個の点から2点を選ぶ全ての組み合わせを試して2点の差$(p_{ij}, q_{ij})$を保存します。そして同じ値をとる個数の最大値を$N$から引けばそれが答えです。
実装
個数を数えるのはpythonのCounter()を使います。
import collections
N = int(input())
XY = []
for i in range(N):
x, y = map(int, input().split())
XY.append([x, y])
PQ = []
for xi, yi in XY:
for xj, yj in XY:
if xi == xj and yi == yj:
continue
PQ.append((xi-xj, yi-yj))
C = collections.Counter(PQ)
ans = 0
for c in C:
ans = max(ans, C[c])
ans = N - ans
print(ans)
Hard No54 : E - Red and Green Apples
発想
とりあえず赤色のリンゴも緑色のリンゴもおいしさの大きい順に並べます。赤色のリンゴも緑色のリンゴもそれぞれ$X+1$個目、$Y+1$個目以降は食べないことがわかります。そのあとは赤色、緑色、無色のリンゴをひとつのリストに格納しておいしさの大きい順に並べた時に、$X+Y$個目まで食べればよいことがわかります。なぜなら$X+Y$個目までの赤色のリンゴがいくつか減ったとしても、その減った分は無色のリンゴが赤色になってくれますし、緑色も同様だからです。
実装
X, Y, A, B, C = map(int, input().split())
R = list(map(int, input().split()))
G = list(map(int, input().split()))
S = list(map(int, input().split()))
R = sorted(R, reverse=True)
R = R[:X]
G = sorted(G, reverse=True)
G = G[:Y]
Ans = R + G + S
Ans = sorted(Ans, reverse=True)
Ans = Ans[:X+Y]
ans = sum(Ans)
print(ans)
Hard No.55 : D - Walk and Teleport
発想
最初は一番左端の町にいるので、途中で往復したりすると余計に疲労がたまります。すぐ右隣りの街に移動するときに毎回歩くのがいいか、テレポートするのがいいのかを判定していけばよいです。
実装
N, A, B = map(int, input().split())
X = list(map(int, input().split()))
ans = 0
for i in range(N-1):
Ad = (X[i+1]-X[i])*A
if Ad > B:
ans += B
else:
ans += Ad
print(ans)
Hard No.56 : B - Two Arrays
発想
操作回数の総和は
\sum{b_i} - \sum{a_i}
になります。$b_i > a_i$のとき、いくらか操作した後に$b_i = a_i$となるための操作回数は
[(b_i - a_i + 1)/2]
になります。これが操作回数の総和を超えてはいけないので、
[(b_i - a_i + 1)/2] \leq \sum{b_i} - \sum{a_i}
となれば良いです。
実装
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
numA = 0
for i in range(N):
d = B[i] - A[i]
if d > 0:
numA += (d+1)//2
if numA <= sum(B) - sum(A):
print('Yes')
else:
print('No')
Hard No.57 : A - Zero-Sum Ranges
発想
連続部分列とはいえしゃくとり法はうまくいかなそうです。累積和を取ったらどこかで0になる部分があるのはすぐに分かります。現在の値がある値$a(a\neq0)$であったときに、その場所から累積和を取って同じ値$a$に戻ってくる場合があったとします。その場合、収支は0になっていなければならないので、その部分列の総和は0になります。ある値$a$である場所が$n$個あるときは、そこから2個を選ぶ場合の数を数えれば良いです。
実装
import collections
import math
def combinations_count(n, r):
return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = list(map(int, input().split()))
S = [0]*(N+1)
for i in range(N):
S[i+1] = S[i] + A[i]
ans = 0
C = collections.Counter(S)
for c in C:
if C[c] >= 2:
ans += combinations_count(C[c], 2)
print(ans)
Hard No.58 : D - DivRem Number
発想
実験してみるしかないです。$N-1$が"お気に入りの数"になることはわかりそうです。他の場合も、$N$のある約数$a$に対して、$a-1$が"お気に入りの数"になります。
実装
N = int(input())
#約数列挙
def divisor(n):
i = 1
table = []
while i * i <= n:
if n%i == 0:
table.append(i)
table.append(n//i)
i += 1
table = list(set(table))
return table
A = divisor(N)
A = sorted(A)
#約数1は除く
A = A[1:]
ans = 0
#全ての(A[i]-1)に対して"お気に入りの数"になるか調べる
for i in range(len(A)):
if N % (A[i] - 1) == N // (A[i] - 1):
ans += A[i] - 1
print(ans)
Hard No.59 : C - 755
発想
1から$N$まで全探索するとTLEしてしまいます。再帰関数を使うのがスマートかと思いますが、別のやり方もあります。答えの候補は各桁に'3','5','7'しか含みませんので、'3','5','7'を答えの候補の末尾に順次追加し、条件を満たすものを数えれば良いです。
実装
import collections
N = int(input())
#答えの候補Can
Can = ['3', '5', '7']
#桁数length
length = 1
ans = 0
while length < len(str(N)):
#次の桁数の候補を入れるB
B = []
for can in Can:
for i in ['3', '5', '7']:
b = can + i
B.append(b)
#答えの候補をBに変える
Can = B
for can in Can:
C = collections.Counter(list(can))
#答えの候補のうち、'3','5','7'を全て1個以上持ち、かつ値がN以下
if C['3']*C['5']*C['7'] > 0 and int(can) <= N:
ans += 1
#桁数を1増やす
length += 1
print(ans)
Hard No.60 : D - Handstand 2
発想
1から$N$までのある数$n$を考えます。$n$の先頭の桁の数と末尾の桁の数をそのままの順番で繋げた数$a$は1~99のいずれかの数になります。$n$が1桁の場合、$a$は11,22,...99のいずれかになります。$n$の末尾が0の場合、$a$は1~9になります。1~$N$まで全て探索して$a$になる個数を数えます。$a$の個数と$a$をreverseした数$b$の個数の積を足していけば答えになります。
実装
$a$が1~10のとき、$b$の先頭は0になってしまうので$a$が11~99のときを計算すれば良いです。
N = int(input())
A = [0]*100
for i in range(1, N+1):
#先頭front, 末尾behind
front, behind = str(i)[0], str(i)[-1]
a = int(front+behind)
A[a] += 1
ans = 0
for a in range(11, 100):
b = int(str(a)[::-1])
ans += A[a]*A[b]
print(ans)