AtCoder Problems Hard No.31~40解説

#Hard No.31 : D - Preparing Boxes
D - Preparing Boxes
##発想
何言ってんだこいつって気持ちに一瞬なります。前から見ていくと、例えば
1の倍数が描かれた箱は1, 2, 3, ...
2の倍数が描かれた箱は2, 4, 6, ...
となるので、考えなければならない箱の数が多くて辛いです。1からNまでの整数の中でNの倍数はNのみなので、後ろから見れば楽そうだなと考えます。
##実装
初期状態として、まだどの箱にもボールは入っていない状態にします。後ろから箱を見ていきます。$i$の倍数が書かれた箱に入っているボールの個数の和を2で割った余りと$a_i$が異なるなら$i$番目の箱にボールを入れるという操作を繰り返せばよいです。

N = int(input())
A = list(map(int, input().split()))
Box = [0]*N
B = []
ans = 0

for i in range(N-1, -1, -1):
    if sum(Box[i::i+1])%2 != A[i]:
        Box[i] = 1
        B.append(str(i+1))
        ans += 1

print(ans)
print(' '.join(B))

#Hard No.32 : C - Factors of Factorial
C - Factors of Factorial
##発想
$N$の正の約数の個数は($N$を素因数分解したときのそれぞれの素因数の個数)+1をすべてかけた値です。高校数学でもありがちな問題です。$N!$なのでforループで回しても全体の計算量は$O(N^{3/2})$程度です。
##実装

import collections

A = []
#素因数分解
def prime_factorize(n):
    global A
    while n % 2 == 0:
        A.append(2)
        n //= 2    
    f = 3
    while f*f <= n:
        if n % f == 0:
            A.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        A.append(n)
    
    return n

N = int(input())
for i in range(1, N+1):
    prime_factorize(i)
C = collections.Counter(A)
#各素因数の個数のリストexp
exp = list(C.values())

ans = 1
for i in exp:
    ans *= i+1
    ans %= 10**9 + 7

print(ans)

#Hard No.33 : D - Rain Flows into Dams
D - Rain Flows into Dams
##発想
山に降った雨の総量とダムに溜まった雨の総量は等しいです。山$i$に降った雨量を$M_i$とすると

M_1 = sum(A) – (M_2 + M_3 + … + M_N)

となります。また、それぞれのダムについて

M_1 + M_2 = 2A_1\\
M_2 + M_3 = 2A_2\\
…\\
M_{N-1} + M_N = 2A_N

となるので、これの偶数行目を取り出せば

M_1 = sum(A) – 2(A_2 + A_4 + … + A_N-1)

となり、山1の雨量を求められます。全ての山についてこの計算をすると$O(N^2)$でTLEします。しかし、

M_2 = 2A_1 - M_1\\
M_3 = 2A_2 – M_2\\ 
…\\
M_N = 2A_N - M_{N-1}\\

というように$M_i$は$M_{i-1}$を使って求められるので$O(N)$で解けます。
##実装

N = int(input())
A = list(map(int, input().split()))
M = []
odd = 0
for i in range(1, N-1, 2):
    odd += A[i]

M1 = sum(A) - odd*2
M.append(M1)

for i in range(1, N):
    Mi = 2*A[i-1] - M[i-1]
    M.append(Mi)

for i in range(N):
    print(M[i], end=' ')

#Hard No.34 : C - Lining Up
C - Lining Up
##発想
自分の左右の人数差の絶対値ということで同じ値が2回出てきそうだなと考えます。つまり$N$が偶数のとき、$N-1, N-3, …, 3, 1, 1, 3, …, N-3, N-1$という形です。$N$が奇数の時だけ真ん中に0が出てくるので場合分けします。
##実装

import collections

N = int(input())
A = list(map(int, input().split()))

C = collections.Counter(A)
ans = 1
#Nが偶数の時
if N % 2 == 0:
    #0が1個でも出てきたらダメ
    if C[0] > 0:
        print(0)
        exit()
    else:    
        for c in C:
            #同じ値が必ず2回現れる
            if C[c] != 2:
                print(0)
                exit()
            else:
                ans *= 2
                ans %= 10**9+7
#Nが奇数の時
else:
    #真ん中に0が1回だけ現れる
    if C[0] != 1:
        print(0)
        exit()
    else:
        for c in C:
            #0を除いて同じ値が必ず2回現れる
            if c == 0:
                continue
            if C[c] != 2:
                print(0)
                exit()
            else:
                ans *= 2
                ans %= 10**9+7
                
#Aに現れる値の差は0か2
A = sorted(A)
for i in range(N-1):
    if A[i+1] - A[i] != 0 and A[i+1] - A[i] != 2:
        print(0)
        exit()

print(ans)

#Hard No.35 : D - Katana Thrower
D - Katana Thrower
##発想
同じ刀なら投げつけた方が与えられるダメージは高いので、できるだけ投げつけた後で残りの刀（の中で最大のダメージを与えられる刀）で振り続けた方が良さそうです。
##実装

import bisect

N, H = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
B = sorted(B)
#投げつけに使う刀の最小値の位置kを探す
maxA = max(A)
k = bisect.bisect_left(B, maxA)
sumB = 0
for i in range(k, N):
    sumB += B[i]

ans = 0
#投げつけても魔物のHPが残っている場合
if H > sumB:
    #刀を投げつける回数
    ans += N-k
    #刀を振る回数
    ans += (H - sumB)//maxA
    #魔物の残りのHPが刀1回で与えられるダメージで割り切れない時
    if (H-sumB) % maxA != 0:
        ans += 1
#投げつけだけで魔物を倒せる場合
else:
    for i in range(N-1, -1, -1):
        H -= B[i]
        ans += 1
        if H <= 0:
            break

print(ans)

#Hard No.36 : A – Triangle
A – Triangle
##発想
3点$P_1, P_2, P_3$とすると、1点は原点に固定しても良いです。もう少し考えると、2点目も例えば$(10^9, 0)$に固定できるのではと考える。3点目の$x$座標は0に固定できるし、結局は3点目の$y$座標だけ求めれば良いのではと考える。しかしこの場合、あらゆる面積を作れるが、$y$座標が整数になってくれないから不適だということに気づく。大学数学を少し齧れば三角形の面積は外積で出せるので（ぶっちゃけ今のたいていの高校生は知ってそう）、それを使う。$P_2(x_2, y_2), P_3(x_3, y_3)$とすると

S = |x_2y_3 – y_2x_3|

なので$x_2 = 10^9, y_2 = 1$とし、絶対値の中身が正とすると

S = 10^9 y_3 – x_3

となる。ここで

S = 10^9(y’-1) + x'

とみなせば$y’-1$と$x’$はそれぞれ$S$を$10^9$で割った商とあまりになる。$y’-1$と$x’$から$y_3$と$x_3$を求められる。
##実装

S = int(input())


y = S // 10**9 + 1
x = 10**9 - S % 10**9 

if S % 10**9 == 0:
    y -= 1
    x = 0
print(0, 0, 10**9, 1, x, y)

#Hard No.37 : C - Strawberry Cakes
C - Strawberry Cakes
##発想
区切りの入れ方としては、上から見ていって
（１） イチゴを発見するたびに、その行の上側に区切りを入れる
（２） 同じ行にイチゴが複数ある場合、同じ行の中でイチゴを発見するたびに、そのイチゴの手前に区切りを入れる
の2つを続ければ正解しそうです。ただし0行目にイチゴがなかった場合に注意が必要です。
##実装

H, W, K = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

Ans = []
k = 1
for i in S:
    #イチゴが1行に1個もない
    if i == '.' * W:
        if Ans:
            Ans.append(Ans[-1])
        else:
            Ans.append([0]*W)
    else:
        #イチゴを初めて見つけた列まで番号を入れる
        f = i.index('#')
        Ans.append([k] * (f + 1))
        #k以降に番号を入れる
        for j in i[f + 1:]:
            if j == '#':
                k += 1
            Ans[-1].append(k)
        k += 1

#0行目から初めてイチゴを発見した行の手前まで番号を入れる
for i in range(H):
    if Ans[i] != [0]*W:
        for j in range(i):
            Ans[j] = Ans[i]
        break
        
for i in Ans:
    print(*i)

#Hard No.38 : D - Maze Master
D - Maze Master
##発想
迷路の距離の問題なので幅優先探索をすれば良さそうです。全点を始点としても計算量的には問題なさそうです。毎回の距離の最大値を取ってきてその中の最大値を答えとすれば良いです。
##実装

from collections import deque

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

ans = 0
#全点始点の幅優先探索
for i in range(H):
    for j in range(W):
        #始点からの距離dist
        dist = []
        for _ in range(H):
            dist.append([-1]*W)
        #スタートが壁でない時に探索する
        if S[i][j] == '.':

            Q = deque()
            Q.append([i, j])
            dist[i][j] = 0
            #キューから取り出しながら探索する
            while len(Q) > 0:
                y, x = Q.popleft()
                #4方向の探索
                for y2, x2 in [[y+1, x], [y, x+1], [y-1, x], [y, x-1]]:
                    #マスからはみ出たらアウト
                    if not (0 <= y2 < H and 0 <= x2 < W):
                        continue
                    #壁だったらアウト
                    if S[y2][x2] == '#':
                        continue
                    if dist[y2][x2] == -1:
                        dist[y2][x2] = dist[y][x] + 1
                        Q.append([y2, x2])
                        ans = max(ans, dist[y2][x2])

print(ans)

#Hard No.39 : C – Stones
C – Stones
##発想
黒石の右側にある白石は黒色にすべきだし、白石の左側にある黒石は白色にすべきです。どこか適当な場所に仕切りを置いて、その仕切りより右側の白石の個数と左側の黒石の個数の和が色を変更しなければならない石の個数です。仕切りを左端から右端まで移動した時の最小値を求めれば良いです。何かしらの物が一列に並んでたら仕切りを置いてみるのは定石のように思います。
##実装

N = int(input())
S = list(input())
tmp = S.count('.')
ans = S.count('.')

for i in range(N):
    if S[i] == '#':
        tmp += 1
    else:
        tmp -= 1
    ans = min(ans, tmp)

print(ans)

#Hard No.40 : C - Inserting 'x'
C - Inserting 'x'
##発想
回文判定をするときは元の文字列とreverseした文字列が一致するかどうかを考えることが僕は多いです。しかしこの問題だとうまくいかなそうです。もう一つの考え方は先頭と末尾を同時に取り出しながら一致するかどうか判定するというものです。
##実装

from collections import deque

S = deque(input())
ans = 0

while len(S) > 0:
    front = S.popleft()
    #Sが空文字になってしまったらbreak
    if len(S) == 0:
        break
    behind = S.pop()

    if front == behind:
        continue
    #片方のみ'x'でなかったら'x'でない文字を戻す
    elif front == 'x' and behind != 'x':
        ans += 1
        S.append(behind)
    elif front != 'x' and behind == 'x':
        ans += 1
        S.appendleft(front)
    else:
        print(-1)
        exit()

print(ans)