AtCoder Problems Hard No.41~50解説

#Hard No.41 : C - Triangular Relationship
[C - Triangular Relationship]( https://atcoder.jp/contests/arc102/tasks/arc102_a)
##発想
$a,b,c$が全て$K$の倍数であれば、$a+b,b+c,c+a$も全て$K$の倍数になります。次に、$a,b,c$は$K$の倍数ではないが問題の条件を満たす場合はあるかなと考えます。$a,b,c$それぞれを$K$で割った時のあまりがちょうど$K/2$であれば問題の条件を満たします。そしてこの場合、$K$は偶数でなければならないです。
##実装

```python
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
[D – Insertion]( https://atcoder.jp/contests/abc064/tasks/abc064_d)
##発想
最初から正しい括弧列になっている部分が邪魔なので、それを初めに消去します。残った括弧列の文字数と同数の’(‘か’)’を追加すれば良いです。
##実装

```python
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
[D – Wall]( https://atcoder.jp/contests/abc079/tasks/abc079_d)
##発想
0から9までの全ての数字を1に変えます。各数字から1に直接変化させるのに必要な魔力が与えられています。この魔力の値によっては、直接1に変化させるよりも別の数字をいくつか経由して1に変化させた方が必要な魔力は小さい場合があります。このときに必要な魔力の最小値を求めます。これはワーシャルフロイド法そのままの考え方です。つまり$i$から$j$に移動するのに$k$個の数字を経由した時の必要な魔力の最小値です。
##実装

```python
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
[C - HonestOrUnkind2]( https://atcoder.jp/contests/abc147/tasks/abc147_c)
##発想
$N$が15以下であることに注目します。答えも$N$以下になるので誰が正直者なのかを全探索できそうです。ちなみに

```math
log_{10}(2^{29}) ≒ 8.73\\
log_{10}(2^{30}) ≒ 9.03
```
なので$2^{30}$あたりが競プロでTLEしない限界かと思います。全探索したときに矛盾した発言が1つもない場合を答えとします。
##実装
矛盾した発言があった場合は２重ループを抜けるようにしています。

```python
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
[D - 2017-like Number]( https://atcoder.jp/contests/abc084/tasks/abc084_d)
##発想
クエリごとに毎回”2017に似た数”を数え上げていたらTLEします。$x$は$10^5$までなので、$10^5$までの”2017に似た数”をあらかじめ求めておきます。このように「クエリが与えられたときに、あらかじめ必要な計算をしておくことでTLEしないようにする」という考え方は競プロでたびたび見かけます。クエリが与えられるごとに$l$と$r$の位置を二分探索すれば$O(Qlog(N))$で間に合いそうです。
##実装

```python
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
[A - STring]( https://atcoder.jp/contests/agc005/tasks/agc005_a)
##発想
‘S’と’T’は同じ数だけあります。’S’が現れるごとに答えに2を足し、’T’が現れるごとに2を引けば良いです。
##実装

```python
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
[D - Lunlun Number]( https://atcoder.jp/contests/abc161/tasks/abc161_d)
##発想
どの桁の数も隣の桁の数との差の絶対値が1以下です。最初に0~9までの数を答えのリストに入れ、順次桁数を増やした数を追加していく形がいいです。
##実装

```python
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
[E - Crested Ibis vs Monster]( https://atcoder.jp/contests/abc153/tasks/abc153_e)
##発想
求めるものは必要な魔力の最小値です。モンスターの残り体力によって必要な魔力の値は変わります。状態が刻々と変化しますので、動的計画法を使うと良さそうだなと考えます。$dp$の定義はこんな形にします。
$dp[i]$ : モンスターの体力を$i$減らすのに必要な魔力の最小値
##実装

```python
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
[D – Bouquet]( https://atcoder.jp/contests/abc156/tasks/abc156_d)
##発想
異なる$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$について、以下が成り立つ

```math
a^{P-1} ≡ 1 \quad (mod \ M)
```

今回は$M$が$10^9+7$であり、これは素数なので

```math
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}$をかけることは等しいとわかる。

```python
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
[D - Grid Repainting]( https://atcoder.jp/contests/abc088/tasks/abc088_d)
##発想
できるだけたくさんのマスを黒に変えたいです。($(1, 1)$から$(H, W)$までの距離)+1は通ってきた白マスの数に等しいです。白マスの総数から($(1, 1)$から$(H, W)$までの距離)+1を引けば、これが黒に変えられるマスの個数になります。
##実装

```python
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)
```