AtCoder Beginner Contest 179 振り返り
D - Leaping Tak
1からNまでの移動する通りの数を求める．
ただし，移動する際はK個の区間によって形成されたマスの数しか移動できない．
[1,2] [5,6,7] [9,10]など．
N は2*10**5以下．
MOD ＝998244353
解）
愚直に全部足すとO(N**2)の計算量．
Kの区間ごとに区間和を足すことで，O(KN)まで抑えられる．
解の数列とは別に累積和の数列を作っておくことにより，区間和を高速に求めることができる．
例）sum(A[3:8]) = S[7] - S[2]
初期値設定
dp = [0] * n
dp[0] = 1
acc_dp = [1] * n
それぞれの区間Kについて，足していく
for d in lr:
a = i - d[0]
if a < 0:
continue
b = i - d[1] - 1
val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
（参考）
Submission #16904040 - AtCoder Beginner Contest 179
E - Sequence Sum
二乗してMODを取るのを繰り返す数列の要素和．
長さN，初期値X，MODがM．
解）取り得る値の種類はM通りしかないため，繰り返しが起きるまで計算することでO(M)で解ける．
ループ前＋ループ＋ループ後を足すことで答えになる．
そんなに難しくないはずなのに答えが合わなかったのは何故
AtCoder Beginner Contest 177 振り返り
D - Friends
・友達の友達は友達
・友達同士がいないように分ける場合，最低何グループ必要か
解）
最大の友達集合の大きさを求めればよい．
Union Find 木構造が役に立つ．
実装：
parent[] は大きさN，-1を初期値とし，parent[i]には i の根を格納．
iが根の場合はグループの要素の数を負で格納．
根を見つけ，道中にある数字の根も書き換える関数．
負の数（グループの構成要素数）
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
根をつなぎなおす関数
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
例：
入力を
7 5
1 7
2 6
3 5
4 5
4 6
とすると，
#i について
f:0
[-1, -1, -1, -1, -1, -1, -1]
i:0
#j について
f:6
[-1, -1, -1, -1, -1, -1, -1]
j:6
#unite内のparent書き換え
[6, -1, -1, -1, -1, -1, -2]
f:1
[6, -1, -1, -1, -1, -1, -2]
i:1
f:5
[6, -1, -1, -1, -1, -1, -2]
j:5
[6, 5, -1, -1, -1, -2, -2]
f:2
[6, 5, -1, -1, -1, -2, -2]
i:2
f:4
[6, 5, -1, -1, -1, -2, -2]
j:4
[6, 5, 4, -1, -2, -2, -2]
f:3
[6, 5, 4, -1, -2, -2, -2]
i:3
f:4
[6, 5, 4, -1, -2, -2, -2]
j:4
[6, 5, 4, 4, -3, -2, -2]
f:3
[6, 5, 4, 4, -3, -2, -2]
f:4
[6, 5, 4, 4, -3, -2, -2]
i:4
f:5
[6, 5, 4, 4, -3, -2, -2]
j:5
[6, 5, 4, 4, 5, -5, -2]
# 答え
5
（参考）
Submission #16326133 - AtCoder Beginner Contest 177
E - Coprime
集合｛Ai｝から任意の2つの要素を選んでも互いに素であれば pairwise coprime
上記を満たさないが全要素の最大公約数が1であれば setwise coprime
上二つの条件を満たすかどうかを判定する．
（制約）Ai の長さNは10**6以下，要素の大きさも10**6以下．
解）高速で素因数分解をし，要素に重複があるか調べればよい．
前計算で2と奇数から約数候補を生成する．
def facs(n):
"""試し割り法における割る数を生成する。"""
yield 2
for x in range(3, n, 2):
yield x
main関数では，最初に各数字を入れた配列を作成する．
for x in array:
histogram[int(x)] += 1
ここで先ほど作成した約数候補を用いて，約数の重複がなければpairwise coprime
for divider in facs(MAX_A):
count = sum(histogram[divider::divider])
if count > 1:
break
else:
return 'pairwise coprime'
setwise coprime はgcd関数を利用すればよい.
3つ以上の数の最大公約数を求めるには複数回使用する必要があるが，reduce関数を利用することで簡潔に書ける．
from math import gcd
from functools import reduce
gcd_total = reduce(gcd, array)
if gcd_total == 1:
return 'setwise coprime'
（参考）
Submission #16392807 - AtCoder Beginner Contest 177
F - I hate Shortest Path Problem
右あるいは下に動くことができる．
K+1番目までの最短ルートを求めたい．
解）
縦方向の移動量は等しいので，横方向の移動の最小量を求めればよい．
初期位置と現在位置のずれが最小であるものを求めたい．
各行における答え ret，
初期位置と現在位置を保管しておくdp0とdp，
直進できる場合のインデックスと直進できない場合の最小値のインデックスをarg0，argとして更新していく．
def solve(a, b, H, W):
ret = np.empty(H, i8)
for i in range(H):
ret[i] = -1
dp0 = np.arange(W) #初期位置
dp = np.arange(W) #現在位置
arg0 = W - 1
arg = 0
for i in range(H):
r1 = np.searchsorted(dp, a[i])
r2 = np.searchsorted(dp, b[i])
if b[i] == W: #右端まで壁が続く場合
if r1 == 0:
return ret
else:
dp0 = dp0[: r1] #壁があるところより先は無視する
dp = dp[: r1]
else:
dp[r1:r2] = b[i] #合流させる
if arg0 > -1: #直進する流れが残っている場合
if r1 <= arg0 < r2: #壁がある場合
for j in range(r1 - 1, -1, -1):
if dp[j] == dp0[j]:
arg0 = j #ここまで直進してきた他の流れに乗り換える
ret[i] = i + 1
break
else:
arg0 = -1
arg = np.argmin(dp - dp0) #残っている値の中での最小値
ret[i] = dp[arg] - dp0[arg] + i + 1
else:
ret[i] = i + 1
else:
if r1 <= arg < r2:
arg = np.argmin(dp - dp0)
ret[i] = dp[arg] - dp0[arg] + i + 1
このままでも計算できるが，TLEするものが一つある．
1000行おきに一回流れをまとめて初期位置，現在位置などを残っている流れに応じて初期化することで計算時間を短くすることができる．
if i % 1000 == 999:
m = 0
prev = dp[0]
for k in range(1, dp.shape[0]):
if dp[k] > prev: #dp[0]とは別の流れにあるものについて
dp0[m] = dp0[k - 1] #最小のずれを持つもののみ残してまとめる
dp[m] = prev
m += 1
prev = dp[k]
else: #流れが一つのみの場合はこの流れの実を追いかける
dp0[m] = dp0[dp0.shape[0] - 1]
dp[m] = prev
m += 1
dp0 = dp0[: m]
dp = dp[: m]
if arg0 > -1: #現在最小である流れなどの情報も更新しておく
for j in range(m - 1, -1, -1):
if dp[j] == dp0[j]:
arg0 = j
break
else:
arg = np.argmin(dp - dp0)
（参考）
AtCoder Beginner Contest 176 振り返り
D - Wizard in Maze
魔術師が迷路にいる．
上下左右に移動する，あるいはコスト1で自分を中心とした5×5のマスのどれかにワープすることができる．
なるべく少ないワープ回数で移動したい．
解）
ワープ回数0のエリア，1のエリア，…と分けていき，ゴールまでたどり着けばよい．
具体的な実装は以下のコードのものを参考にした．
Submission #16141246 - AtCoder Beginner Contest 176
ワープ回数をdist，現在位置をdeqとする．これらは一次元配列にして計算速度を早くする．
初期設定：
def main(wall, Sx, Sy, Tx, Ty):
INF = 1 << 30
H, W = wall.shape
S = Sx * W + Sy
T = Tx * W + Ty
dist = np.full(H * W, INF, np.int64)
deq = np.empty(H * W + 100, np.int64)
dist[S] = 0
deq[0], l, r = S, 0, 1
実際に移動するところは以下のように実装する．
while l < r:
v, l = deq[l], l + 1
vx, vy = divmod(v, W)
# そのままあるく
wx, wy = vx + dx, vy + dy
if not (0 <= wx < H):
continue
if not (0 <= wy < W):
continue
if wall[wx, wy]:
continue
w = wx * W + wy
if dist[w] <= dist[v]:
continue
dist[w] = dist[v]
deq[l - 1], l = w, l - 1
# ワープする
for dx in range(-2, 3):
for dy in range(-2, 3):
wx, wy = vx + dx, vy + dy
if not (0 <= wx < H):
continue
if not (0 <= wy < W):
continue
if wall[wx, wy]:
continue
w = wx * W + wy
if dist[w] <= dist[v] + 1:
continue
dist[w] = dist[v] + 1
deq[r], r = w, r + 1
ans = dist[T]
if ans == INF:
ans = -1
return ans
numbaを利用すると時間内に通る．
numbaをインポートし，関数の頭に@njitをつけることで使用できる．
import numba
from numba import njit, b1, i4, i8, f8
@njit*2
最大値を取り得るマスの数を数え，そのすべてのマスに箱がおかれているかチェックする．
cnt = A.count(a) * B.count(b) - len([0 for h, w in HW if A[h] == a and B[w] == b])
置かれていたら縦と横の和から1を引き，それ以外はそのまま和を出力すればよい．
print(a + b - (cnt == 0))
Submission #16187005 - AtCoder Beginner Contest 176
def main(wall, Sx, Sy, Tx, Ty):
参考：
E - Bomber
十字に爆発する爆弾を仕掛け，なるべく多くの箱を壊したい．
縦と横の箱の個数を数えればよいが，箱のあるマスに仕掛けることもでき，ここに爆弾を置くかどうかで場合分け．
フィールドは最大で3*10^5 四方，，箱の数も最大3*10^5 個.
解）
箱があるマスはzip関数で記録しておくと良い．
H, W, M, *HW = map(int, open(0).read().split(
M-SOLUTIONS プロコンオープン 2020 振り返り
E - M's Solution
N個の集落が効率よく通勤できるように鉄道を敷く．
解法：
愚直に全パターン計算しようとすると，(4**N) * (N**2) ．
事前にコストを計算しておくこと，縦と横を別々に分けることで (3**N) * N になる．
事前にX方向のみ路線を引いた場合，Y方向のみ路線を引いた場合について，各集落のコストを求めておく．計算時間は
(路線を敷く場所) * (各路線から各集落までの距離) = (2**N) * (N**2)
2次元の問題を解く際は，路線の数 = K に対して
2 ** K * nCK 通りの路線の選び方があり，
これは K=0~Nまで足すと 3**N通り．
事前にコストを計算しているため，最小コストはこれにNをかけた時間で求まる．
Submission #15454214 - M-SOLUTIONS Programming Contest 2020
F - Air Safety
飛行機がぶつかるか判断．
ぶつかる場合は最小時刻を求める．
解法：
まずはY方向での正面衝突を考える．Xの順に並べ，同一のXについて衝突までの時間を計算する．
バイナリを使うと効率的に並べ替えられる．
def f(X1, Y1, X2, Y2):
# x1,y1 から y が増える側に移動 vs x2,y2 から y が減る側に移動
ret = 10**18
key1 = (X1 << 32) + Y1
key2 = (X2 << 32) + Y2
ind = key1.argsort()
X1, Y1, key1 = X1[ind], Y1[ind], key1[ind] # X，Yの大きさ順
ind = key2.argsort()
X2, Y2, key2 = X2[ind], Y2[ind], key2[ind]
js = np.searchsorted(key2, key1) # key2にkey1を挿入する場合のインデックス
for i in range(len(key1)):
j = js[i]
if j == len(key2):
continue
if X1[i] != X2[j]:
continue
ret = min(ret, Y2[j] - Y1[i])
return ret
列の終わりに来たり，Xが異なったりしたら次に行く．
飛行機の方向の保存は，
for _ in range(N):
x, y, u = readline().split()
U.append(u)
U = np.array(U, 'S1') # 長さ1のstrを保存
i_u = U == b'U' # [True False False]など該当する部分のみTrueになる
Xu, Yu = X[i_u], Y[i_u] # Upのみ反映される
などで書く方向について書ける．
左右の衝突や90°回転の衝突は変数を変換すればよい．
ans = min(ans, f(Xu, Yu, Xd, Yd)) # 上、下
ans = min(ans, f(Yr, Xr, Yl, Xl)) # 右、左
ans = min(ans, f(Xr + Yr, Xr - Yr, Xu + Yu, Xu - Yu)) # 右、上
ans = min(ans, f(Xu - Yu, Xu + Yu, Xl - Yl, Xl + Yl)) # 上、左
ans = min(ans, f(Xr - Yr, Xr + Yr, Xd - Yd, Xd + Yd)) # 右、下
ans = min(ans, f(Xd + Yd, Xd - Yd, Xl + Yl, Xl - Yl)) # 下、左
エイジング プログラミングコンテスト 2020 振り返り
D - Anything Goes to Zero
popcount(n)をnを2進数表記した時の'1'の個数とする．
n %= popcount(n)としたとき，nが0になる回数をf(n)とする．
あるNについて，Nを二進数表記した後，一つの桁のビットを反転させたものについてf(n)を求めよ．
解法：
単純に変換し愚直に計算するとTLE
一回の操作で大体NがlogNに変化することを考えると，各操作はせいぜい5~6回．
X1,X2,..., XNにたいしてpopcountで割る際，初回のコストが特に高いので，これを高速に実行する．
popcount(Xi) = popcount(X)±1 であることを考えると，X mod(popcount(X)+1 )，X mod(popcount(X)-1) を事前に計算しておき，同じく事前に計算した 2**i mod(popcount(X)+1 )や 2**i mod(popcount(X)-1 )
を足せばよい
（ただし操作回数0回の場合に注意）
E - Camel Train
N頭のラクダを並べる．
i頭目のラクダについて，Ki 番目以内にいればうれしさがLi，それ以外はRiである．
嬉しさが最大の時の嬉しさを求めよ．
（このようなケースがT個ある．）
解法：
最初に全体でL，Rの最小値の合計を求めた後，可能な限り答えを大きくしていく．
L>RのラクダとL<Rのラクダに分ける．（L=Rのラクダはどこにいてもいいので，都合の良いところに置けばよい）
この時，最適解において，L<Rのラクダが常にL>Rのラクダより右側に存在する解がある．（そうでない場合，これを満たすように並べ変えても嬉しさが変化しない）
つまり，別々に最適解を求めればよい．
L>Rのラクダについてリスト camels を作成し，（L-R）をK番目のリストにappendする．
camels のすべての要素について，数えたラクダの合計がラクダのいる番号を越えないようにする．
具体的にはheapqを使用して，
for i in range(N):
for j in camels0[i]:
heappush(H,j)
while len(H) > i+1:
heappop(H)
ans += sum(H)
とすればよい．これにより，最小値からHに放り込まれた後，超過する分について再び最小値が削られていく．
L>Rのラクダについても同様に右側から計算してやることで答えが求まる．
Submission #15195468 - AIsing Programming Contest 2020
F - Two Snuke
解法：
まずはs1,n1,u1,k1,e1が0の場合について考える．
この場合、掛け算の和はcombで表すことができる．
N個のボールに5個の仕切りを入れ，先頭から順に割り振る．掛け算の和は，仕切られた中から選ぶ方法の数と対応している．
これはN-5個のボールに(5+5)個の仕切りを入れる方法と同値である．
次に， s1,n1,u1,k1,e1が0出ない場合について考える．
Δs = s2-s1, s = 2s1, ...
と設定すると，
s+n+u+k+e + Δs+Δn+Δu+Δk+Δe ≦ Nを満たせばよいことになる．
これはN-5個のボールに(5+5+5)個の仕切りを入れることに対応する（最初5つのセグメントは偶数）．
前半5個は偶数，後半11個は奇数か偶数．
2個セットの偶数で扱えば，前半5個はすべて偶数になる．
後半11個も扱うために，後半11個の偶奇の可能性を全探索し，奇数のところには1個追加すればよい．Nとの偶奇を合わせるために，奇数は 1,3,5,7,9,11個 か 2,4,6,8,10 個である．
for i in range((N-5)%2, 12, 2):
r += math.comb(11,i) % MOD * math.comb((N-5-i)//2 + 15, 15) % MOD
