Hard No.41 : C - Triangular Relationship
発想
$a,b,c$が全て$K$の倍数であれば、$a+b,b+c,c+a$も全て$K$の倍数になります。次に、$a,b,c$は$K$の倍数ではないが問題の条件を満たす場合はあるかなと考えます。$a,b,c$それぞれを$K$で割った時のあまりがちょうど$K/2$であれば問題の条件を満たします。そしてこの場合、$K$は偶数でなければならないです。
実装
N, K = map(int, input().split())
#Nまでの整数の中でKの倍数の個数はN//K個、これがa,b,cの3通りある
ans = (N//K)**3
#Kが偶数のとき
if K % 2 == 0:
tmp = N//K
if N % K >= K//2:
tmp += 1
ans += tmp**3
print(ans)
Hard No.42 : D – Insertion
発想
最初から正しい括弧列になっている部分が邪魔なので、それを初めに消去します。残った括弧列の文字数と同数の’(‘か’)’を追加すれば良いです。
実装
N = input()
S = T = input()
p = '('
q = ')'
o = '()'
#消去できる括弧列を消去する
while o in S:
S = S.replace(o, '')
f = S.count
#残ったqと同数のpと残ったpと同数のqを元の括弧列に加える
print(p*f(q) + T + q*f(p))
Hard No.43 : D – Wall
発想
0から9までの全ての数字を1に変えます。各数字から1に直接変化させるのに必要な魔力が与えられています。この魔力の値によっては、直接1に変化させるよりも別の数字をいくつか経由して1に変化させた方が必要な魔力は小さい場合があります。このときに必要な魔力の最小値を求めます。これはワーシャルフロイド法そのままの考え方です。つまり$i$から$j$に移動するのに$k$個の数字を経由した時の必要な魔力の最小値です。
実装
import collections
INF = 1_000_000_000_000_000_000
H, W = map(int, input().split())
dist = []
for i in range(10):
dist.append([INF]*10)
for i in range(10):
c = list(map(int, input().split()))
for j in range(10):
dist[i][j] = c[j]
for i in range(10):
dist[i][i] = 0
#ワーシャルフロイド法
for k in range(10):
for i in range(10):
for j in range(10):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
A = []
for i in range(H):
a = list(map(int, input().split()))
A += a
ans = 0
C = collections.Counter(A)
for c in C:
if c == 1 or c == -1:
continue
#数字cから1に移動するのに必要な魔力×cの個数
ans += dist[c][1] * C[c]
print(ans)
Hard No.44 : C - HonestOrUnkind2
発想
$N$が15以下であることに注目します。答えも$N$以下になるので誰が正直者なのかを全探索できそうです。ちなみに
log_{10}(2^{29}) ≒ 8.73\\
log_{10}(2^{30}) ≒ 9.03
なので$2^{30}$あたりが競プロでTLEしない限界かと思います。全探索したときに矛盾した発言が1つもない場合を答えとします。
実装
矛盾した発言があった場合は２重ループを抜けるようにしています。
N = int(input())
D = []
for i in range(N):
D.append([])
#D[i] : 人iは人xをyと証言した
for i in range(N):
a = int(input())
for j in range(a):
x, y = map(int, input().split())
D[i].append([x-1, y])
ans = 0
#誰が正直者かを全探索
for i in range(2**N):
#true : 正直者
true = []
for j in range(N):
if i>>j&1 == 1:
true.append(j)
for t in true:
#正直者tについてtの証言を調べる
for x, y in D[t]:
#xが正直者trueの中にいるのにtはxを不親切な人と証言している
if true.count(x) == 1 and y == 0:
break
#xが正直者trueの中にいないのにtはxを正直者だと証言している
if true.count(x) == 0 and y == 1:
break
else:
continue
break
else:
ans = max(ans, len(true))
print(ans)
Hard No.45 : D - 2017-like Number
発想
クエリごとに毎回”2017に似た数”を数え上げていたらTLEします。$x$は$10^5$までなので、$10^5$までの”2017に似た数”をあらかじめ求めておきます。このように「クエリが与えられたときに、あらかじめ必要な計算をしておくことでTLEしないようにする」という考え方は競プロでたびたび見かけます。クエリが与えられるごとに$l$と$r$の位置を二分探索すれば$O(Qlog(N))$で間に合いそうです。
実装
import bisect
import collections
A = []
def divisor(n):
global A
i = 2
while i * i <= n:
if n%i == 0:
return
i += 1
return n
#10^5までの素数をAに入れる
for i in range(2, 10**5 + 1):
D = divisor(i)
if not D:
continue
A.append(D)
#Bに入るのは"2017に似た数"
B = []
C = collections.Counter(A)
for i in A:
if i == 2:
continue
if C[(i+1)//2] == 1:
B.append(i)
Q = int(input())
for i in range(Q):
l, r = map(int, input().split())
#lの位置cur_l, rの位置cur_r
cur_l = bisect.bisect_left(B, l)
cur_r = bisect.bisect_right(B, r)
print(cur_r - cur_l)
Hard No.46 : A – String
発想
‘S’と’T’は同じ数だけあります。’S’が現れるごとに答えに2を足し、’T’が現れるごとに2を引けば良いです。
実装
X = input()
ans = 0
for i in X:
if i == 'S':
ans += 2
elif ans >= 2:
ans -=2
print(ans)
Hard No.47 : D - Lunlun Number
発想
どの桁の数も隣の桁の数との差の絶対値が1以下です。最初に0~9までの数を答えのリストに入れ、順次桁数を増やした数を追加していく形がいいです。
実装
K = int(input())
A = [i for i in range(10)]
#length : 桁数
length = 1
while len(A) <= K:
B = []
for a in A:
a = str(a)
if len(a) < length:
continue
#取り出した数aの1桁目の数
num1 = a[-1]
#num1より1小さい数
num2 = ''
#num1より1大きい数
num3 = ''
if int(num1) > 0:
num2 = str(int(num1) - 1)
if int(num1) < 9:
num3 += str(int(num1) + 1)
Num = num2 + num1 + num3
#取り出した数aの末尾に1桁数字を加える
for num in Num:
B.append(int(a+num))
A += B
A = list(set(A))
length += 1
print(A[K])
Hard No.48 : E - Crested Ibis vs Monster
発想
求めるものは必要な魔力の最小値です。モンスターの残り体力によって必要な魔力の値は変わります。状態が刻々と変化しますので、動的計画法を使うと良さそうだなと考えます。$dp$の定義はこんな形にします。
$dp[i]$ : モンスターの体力を$i$減らすのに必要な魔力の最小値
実装
H, N = map(int, input().split())
#dpの中身は大きな値で初期化
dp = [10**18]*(H+1)
dp[0] = 0
for _ in range(N):
a, b = map(int, input().split())
for i in range(H):
#i+aがHを超える場合があるのでmin(i+a, H)にする
dp[min(i+a, H)] = min(dp[min(i+a, H)], dp[i] + b)
print(dp[H])
Hard No.49 : D – Bouquet
発想
異なる$n$個のものから$k$個を選ぶ場合の数は$_nC_k$ですが、この$k$を1から$n$まで動かしたときの和から$k = a, k = b$の場合を引いたものが答えです。この和の部分は二項定理を考えれば$2^n$になることは有名です。$n$個のものそれぞれに対して取る取らないを選択するから$2^n$とも考えられます。よって$_nC_a$, $_nC_b$を求めれば勝ちです。
実装
Pythonの便利な関数pow()を使います。例えばpow(2, $n$, $m$)は$2^n$を$m$で割ったときの余りを返します。
$_nC_a$, $_nC_b$を計算するときには分数の形が出てきます。分数は扱いたくないです。分数を扱わなくて済むようにフェルマーの小定理を用います。
フェルマーの小定理：$P$が素数のとき、$P$の倍数でない整数$a$について、以下が成り立つ
a^{P-1} ≡ 1 \quad (mod \ M)
今回は$M$が$10^9+7$であり、これは素数なので
a^{(10^9+7)-1} ≡ 1 \quad (mod \ 10^9+7)\\
a^{ \ }・a^{(10^9+7)-2} ≡ 1 \quad (mod \ 10^9+7)
となるので、$a^{(10^9+7)-2}$が$a$の逆元になることがわかる。つまりmodの世界では$a$で割ることと$a^{(10^9+7)-2}$をかけることは等しいとわかる。
import math
n, a, b = map(int, input().split())
mod = 10**9 + 7
ans = pow(2, n, mod) - 1
p = 1
q = 1
for i in range(1, b+1):
p = (p*(n-i+1)) % mod
q = (q*i) % mod
if i == a:
nCa = p*pow(q, mod-2, mod)
else:
nCb = p*pow(q, mod-2, mod)
ans = (ans - nCa - nCb) % mod
print(ans)
Hard No.50 : D - Grid Repainting
発想
できるだけたくさんのマスを黒に変えたいです。($(1, 1)$から$(H, W)$までの距離)+1は通ってきた白マスの数に等しいです。白マスの総数から($(1, 1)$から$(H, W)$までの距離)+1を引けば、これが黒に変えられるマスの個数になります。
実装
from collections import deque
H, W = map(int, input().split())
S = []
for i in range(H):
S.append(input())
dist = []
for i in range(H):
dist.append([-1]*W)
dist[0][0] = 0
Q = deque()
Q.append([0, 0])
#(1, 1)から(H, W)までの距離を幅優先探索で求める
while len(Q) > 0:
i, j = Q.popleft()
for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
i2 = i + di
j2 = j + dj
if not (0 <= i2 < H and 0 <= j2 < W):
continue
if S[i2][j2] == '#':
continue
if dist[i2][j2] == -1:
dist[i2][j2] = dist[i][j] + 1
Q.append([i2, j2])
tmp = 0
#白マスの総数
for i in range(H):
for j in range(W):
if S[i][j] == '.':
tmp += 1
ans = tmp - dist[H-1][W-1] -1
if dist[H-1][W-1] == -1:
ans = -1
print(ans)