AtCoder Problems Hard No.21~30解説

#Hard No.21 : D - Binomial Coefficients
D - Binomial Coefficients
##発想
$_nC_r$が最大になるような$n, r$をリストAから見つけます。$a_i$については素直に最も大きなものにすれば良いです。試しに$_nC_{r+1}/_nC_r$を計算してみると$r<=n/2$のときに$_nC_r$は大きくなります。よって$a_j$はこの条件を満たす最大のものにすれば良いです。
##実装

n = int(input())
A = list(map(int, input().split()))
A = sorted(A)

ai = A[-1]

aj = 10**9+1
for i in range(n):
    if abs(ai - 2*A[i]) < abs(ai - 2*aj):
        aj = A[i]

print(ai, aj)

#Hard No.22 : C - String Transformation
C - String Transformation
##発想
Sのある英小文字とTのある英小文字を1対1に対応させてSをTに近づけていきます。つまりSとTの文字種ごとの数を数えるCounterを使い、Counterの値が完全一致すればYes、しなければNoとなります。
##実装

import collections

s = input()
t = input()
S = collections.Counter(s)
T = collections.Counter(t)

if sorted(S.values())==sorted(T.values()):
	print("Yes")
else:
	print("No")

#Hard No.23 : C - 白昼夢
C - 白昼夢
##発想
Sを前からみたときに例えば’dream’で区切ればいいのか’dreamer’で区切ればいいのか判断がしづらいです。逆に後ろから見ていくと、'maerd'、'remaerd'、'esare'、'resare'は全て末尾に到達する前に区別がつくので、区切る位置は1通りに決まります。「前から見てダメなら後ろから見る」というのは競プロでたびたび見かける考え方です。
##実装

from collections import deque

S = list(input())
S = list(reversed(S))
Q = deque()

for i in range(len(S)):
    Q.append(S[i])

D = ''
for i in range(len(S)):
    j = Q.popleft()
    D += j
    
    if D == 'maerd':
        D = ''
    if D == 'remaerd':
        D = ''
    if D == 'esare':
        D = ''
    if D == 'resare':
        D = ''

if len(D) >= 1:
    print('NO')
else:
    print('YES')

#Hard No.24 : B - Robot Arms
B - Robot Arms
##発想
区間スケジューリングな問題です。ロボット同士がぶつからないためには、1個手前のロボットの稼働範囲の最大値が現在のロボットの最小値以下であることです。稼働範囲の最大値でソートをかけて順番に見ていけば良いです。
##実装

N = int(input())
A = []
#ロボットの稼働範囲のうち大きい方でソートする
for i in range(N):
    X,L = map(int, input().split())
    A.append([X-L, X+L])
A = sorted(A, key=lambda x: x[1])

#現在位置tmp, 置けるロボットの個数count
tmp = -10 ** 10
count = 0
for i in range(N):
    if tmp <= A[i][0]:
        count += 1
        tmp = A[i][1]

print(count)

#Hard No.25 : C - Special Trains
C - Special Trains
##発想
判断すべきことは2つです。
（１） 駅$i$に到着した時刻がその駅の始発より早いかどうか
（２） 駅$i$に到着した時刻が列車の発車間隔で割り切れるか
##実装

N = int(input())
C = []
S = []
F = []
for i in range(N-1):
    c, s, f = map(int, input().split())
    C.append(c)
    S.append(s)
    F.append(f)

for i in range(N):
    t = 0
    for j in range(i, N-1):
        #駅iに到着した時刻がその駅の始発より早いかどうか
        if t - S[j] < 0:
          t = S[j]
        #駅iに到着した時刻が列車の発車間隔で割り切れるか
        elif t % F[j] != 0:
          t += F[j] - t % F[j]

        t += C[j]

    print(t)

#Hard No.26 : B - K個のケーキ
B - K個のケーキ
##発想
最も個数の多いケーキをまず1列に並べます。そのケーキたちの間に別の種類のケーキをできるだけ挟むと、連続して同じ種類のケーキを食べる日数を最小にできます。
##実装

K, T = map(int, input().split())
A = list(map(int, input().split()))
Amax = max(A)
Asum = sum(A) - Amax
D = Amax - Asum - 1

if D >= 0:
  print(D)
else:
  print(0)

#Hard No.27 : D – Ki
D – Ki
##発想
例えば頂点1, 2, 3がこの順番で連結されているとき、頂点1の値は$x_1$、頂点2の値は$x_1+x_2$、頂点3の値は$x_1+x_2+x_3$になる。よって深さ優先探索をしたときに深くなるごとに$x_i$を足し、戻るごとに$x_i$を引くことでその頂点の値を求められます。
##実装

import sys
sys.setrecursionlimit(1000000)

N, Q = map(int, input().split())
G = []
for i in range(N):
    G.append([])
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

visited = [False]*N
#頂点pに達したときに足される値
count = [0]*N
for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x

tmp = 0
Ans = [0]*N
def dfs(i):
    global tmp

    visited[i] = True
    #1つ木の深いところに達したら値を足す
    tmp += count[i]
    #頂点iに現在値を入れる
    Ans[i] = tmp
    for j in G[i]:
        if not visited[j]:
            dfs(j)
    #頂点を戻るごとに値を引く
    tmp -= count[i]

dfs(0)

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

#Hard No.28 : C – Candles
C – Candles
##発想
火をつけるロウソク同士が離れていると、離れている分だけ余計に移動する距離が長くなります。よって連続するK本のロウソクに火をつけるのが最短距離になります。移動距離は原点と左端と右端の座標によってのみ決まります。原点から最初に左端に行くか、右端に行くかのうち移動距離の小さい方を採用していきます。
##実装

N, K = map(int, input().split())
X = list(map(int, input().split()))

ans = 10**9+1

for i in range(N-K+1):
    xl = X[i]
    xr = X[i+K-1]
    ans = min(ans, abs(xl) + abs(xr-xl), abs(xr) + abs(xr-xl))

print(ans)

#Hard No.29 : B - Colorful Creatures
B - Colorful Creatures
##発想
大きさの小さい順にソートします。合体を繰り返した大きさは累積和になります。次に吸収しようとする生き物$i$の大きさが現在の累積和の2倍よりも大きかったら、生き物$i$を吸収することはできません。ということは、生き物$i$より小さい生き物は全て最後の1匹になることができません。
##実装

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
#累積和
sumA = []
tmp = 0
for i in range(N):
    tmp += A[i]
    sumA.append(tmp)

num = -1
for i in range(N-1):
    #次の生き物を吸収できるかどうか
    if 2*sumA[i] < A[i+1]:
        num = i

ans = N - num - 1
print(ans)

#Hard No.30 : A - Getting Difference
A - Getting Difference
##発想
全てのボールの最大公約数を$g$とする。2つのボールの差をとったとき、その数字は$g$を変化させることはない。箱の数字の最大値$m$と$g$で差をとり続けると、出ててくる数字は$m-g, m-2g, m-3g$というように最大公約数$g$の数字が全て出てくるので、$K$が$m$以下かつ$g$の倍数であれば良い。
##実装

import math

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

g = A[0]
for i in range(N):
    g = math.gcd(g, A[i])

if max(A) >= K and K % g == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')