キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) E,F,G,H問題メモ
E - Swap
問題
K,E,Yの3種類の文字のみから成る文字列 $S$ が与えられる
$S$ の隣接する2文字を入れ替える操作を $K$ 回以下おこなって作ることの出来る文字列は何通り?
$2 \le |S| \le 30$
$0 \le K \le 10^9$
解法
数列の転倒数の考え方を使って、DP。
数列を隣接swapによりソートするときの最小操作回数は、
各要素につき「初期状態で自身より左にあって、最終状態で自身より右にある要素の個数」の総和となる。
4 2 5 1 3 2にとって 4 の1個が該当┐
↓ 1にとって 4,2,5の3個が該当┼計6回が最小操作回数
1 2 3 4 5 3にとって 4,5 の2個が該当┘
この時、同じ要素が含まれるなら同じ要素同士は操作する必要が無いので、並ぶ順番は最初と最後で変わらない。
a b c
3 1 4 1 5 9 2 6 5 3 5
↓
a b c 5に着目すると、
1 1 2 3 3 4 5 5 5 6 9 a,b,cの順序を変える必要は無い
以上を踏まえると、最終状態を先頭から決めていったとき、
「ここまでで部分的にかかる操作回数」というものを計算することができる。
4 2 5 1 3 1を先頭に持ってくるのに 3┐
↓ 2を 次 に持ってくるのに 1┴暫定コスト4
1 2
これを今回の問題に当てはめると、以下のようなDP(のふわっとしたイメージ)で計算できそう。
最終的に、$DP[N][K以下]$ の総和が答えとなる。
???の部分、同じDPにまとめられる途中経過の状態を考える。
「初期状態で自身より左にあって、最終状態で自身より右にある要素」を「swap対象」と呼ぶことにする。
i 1 2 3 4 5 6 3文字目まで決まり、4文字目に置く文字を考える
初期 K E Y K E Y ・Kの場合、初期で i=1 のKを使う。swap対象は無し
↓ ・Eの場合、もう既に全て使っている
最終 E Y E ? ・Yの場合、初期で i=6 のYを使う。swap対象はK,Kの2個
具体例を整理すると、
「Kを置けるか、置くなら初期のどの位置のKを使えばよいか」は、ここまでに既に使ったKの個数に依存する
その時のswap対象は、「初期で自身より左にあったE,Yのうち、最終でまだ置かれていないもの」となるので、前者を事前計算しておけば、後者はここまでに既に使ったE,Yの個数に依存する
よって、「ここまでに既に使ったK,E,Yそれぞれの個数」によって次の1文字を置くコストが計算できる。
逆に言うと、これらが同じ暫定文字列は、次の1文字を置くコストが同じであり、状態をまとめられる。
$DP[i][j][k][e][y]=$ 最終状態の $i$ 文字目までを決めたとき、暫定コスト $j$ で、K,E,Yを使った回数がそれぞれ $k,e,y$ な文字列の種類数
$j$ の状態数は $O(|S|^2)$、他は $O(|S|)$ で全体で $O(|S|^6)$ となりそうだが、
$i=k+e+y$ なので、$i,k,e$ が決まれば $y$ は自動的に決まる
$i$ の小さい内は $j,k,e,y$ ともに小さい
ため、実際にあり得るのはぐっと少なくなると期待できる。
DPの実装上は $(j,k,e,y)$ を1つのキーとして連想配列で持っておくと、
実際にあり得る状態だけを取り出しやすくなる。
Python3
from collections import defaultdict
s = input()
k = int(input())
indices = [[], [], []]
for c in s:
if c == 'K':
indices[0].append((len(indices[1]), len(indices[2])))
elif c == 'E':
indices[1].append((len(indices[0]), len(indices[2])))
else:
indices[2].append((len(indices[0]), len(indices[1])))
dp = defaultdict(int)
dp[0, 0, 0, 0] = 1
for i in range(len(s)):
new = defaultdict(int)
for (ck, ce, cy, t), pat in dp.items():
if ck < len(indices[0]):
me, my = indices[0][ck]
cost = max(0, me - ce) + max(0, my - cy)
if t + cost <= k:
new[ck + 1, ce, cy, t + cost] += pat
if ce < len(indices[1]):
mk, my = indices[1][ce]
cost = max(0, mk - ck) + max(0, my - cy)
if t + cost <= k:
new[ck, ce + 1, cy, t + cost] += pat
if cy < len(indices[2]):
mk, me = indices[2][cy]
cost = max(0, mk - ck) + max(0, me - ce)
if t + cost <= k:
new[ck, ce, cy + 1, t + cost] += pat
dp = new
print(sum(dp.values()))
F - Treasure Hunting
問題
$H \times W$ のマス目にそれぞれ正整数 $A_{i,j}$ が書かれている
左上 $(1,1)$ から右下 $(H,W)$ まで、1つ右か1つ下のマスへの移動を繰り返す
通った $H+W-1$ マスに書かれた整数のうち、大きい方から $K$ 個の和を移動コストとする
コストとしてあり得る最小値を求めよ
$1 \le H,W \le 30$
$1 \le A_{i,j} \le 10^9$
解法
一見、最短経路っぽく $DP[i][j]=(i,j)$ への最小コスト、とできそうに見えるが、上手くいかない。
$K=4$ で、途中のあるマスへ至るのに通過したマスが $\{1,1,100,100\}$ であるルートと $\{51,51,51,51\}$ であるルートでは、
そこまででは前者の方が低コストだが、その後に通過するマスに $52$ が敷き詰められていたりすると、
前者は $\{52,52,100,100\}$、後者は $\{52,52,52,52\}$ となり、逆転する。
途中までで何が最善かが、後のマスによって変わるため、何を残せばよいのか判断できない。
ここで、やや天啓的だが「最終的にコストに加算される値の下限 $X$」を固定すると現実的な状態数に落とし込める。
隣接マスへの遷移時、$X$ 以上ならコストに加算し、未満なら無視するようにする。
最終的に加算される値が $K$ 個ないといけないのでその個数は管理する必要があるが、
それさえ同じであれば、暫定コストの低い方が正義である。
コスト最小となる真のルートと真の $X$ が(現時点では不明ながらも)あったとして、
いずれにしろ誤った $X$ を仮定するとコストが大きくなるので、$X$ を全て試すことで最善が求まる。
注意点として、$A_{i,j}=X$ となるマスが複数あるとき、
その中の一部だけコストに加算され、残りは捨てられることがある。
これは、「$A_{i,j}=X$ なるマスへの遷移は、それをコストに採用して $k+1$ に遷移してもよいし、
採用しないで $k$ に遷移してもよい」とすることで、表現できる。
計算量は、$X$ としてあり得る値がマスの数 $O(HW)$、それぞれでDPに $O(HWK)$ なので、$O(H^2W^2K)$。
Python3
import os
import sys
import numpy as np
def solve(h, w, k, field):
INF = 1 << 60
ans = INF
for thr in np.unique(field):
dp = np.full((h, w, k + 1), INF, dtype=np.int64)
if field[0, 0] <= thr:
dp[0, 0, 0] = 0
if field[0, 0] >= thr:
dp[0, 0, 1] = field[0, 0]
for i in range(h):
for j in range(w):
for p in range(k + 1):
if dp[i, j, p] == INF:
continue
if i < h - 1:
if field[i + 1, j] <= thr:
dp[i + 1, j, p] = min(dp[i + 1, j, p], dp[i, j, p])
if p < k and field[i + 1, j] >= thr:
dp[i + 1, j, p + 1] = min(dp[i + 1, j, p + 1], dp[i, j, p] + field[i + 1, j])
if j < w - 1:
if field[i, j + 1] <= thr:
dp[i, j + 1, p] = min(dp[i, j + 1, p], dp[i, j, p])
if p < k and field[i, j + 1] >= thr:
dp[i, j + 1, p + 1] = min(dp[i, j + 1, p + 1], dp[i, j, p] + field[i, j + 1])
ans = min(ans, dp[h - 1, w - 1, k])
return ans
SIGNATURE = '(i8,i8,i8,i8[:,:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
cc = CC('my_module')
cc.export('solve', SIGNATURE)(solve)
cc.compile()
exit()
if os.name == 'posix':
# noinspection PyUnresolvedReferences
from my_module import solve
else:
from numba import njit
solve = njit(SIGNATURE, cache=True)(solve)
print('compiled', file=sys.stderr)
h, w, k, *field = map(int, sys.stdin.buffer.read().split())
field = np.array(field, dtype=np.int64).reshape((h, w))
ans = solve(h, w, k, field)
print(ans)
$O(H^2W^2)$ 解法
詳細は解説放送参照
最短経路探索の添字を $DP[i][j]$ だけにできる(個数 $k$ を省ける)。
$X$ に対し、各 $A_{i,j}$ を、$\max(A_{i,j}-X,0)$ とした上で最短経路探索する。
結果に対して $X \times K$ を加算すると、これは $X$ が正しい場合、正しい答えとなる。
さらに $X$ を真の値より大きくしても小さくしても、コストが大きくなってしまうことが示せる。
G - Divisors of Binomial Coefficient
問題
解法
二項係数・約数の個数の公式さえ知っていれば、E,F問題より何をすればいいかはわかりやすかったかも知れない。
正整数 $X$ の約数の個数は、$X$ を素因数分解して $x^ay^bz^c...$ と表せるとき、$(a+1)(b+1)(c+1)...$ となる。
二項係数 $\dbinom{N}{K}$ は、$\dfrac{N(N-1)(N-2)...(N-K+1)}{K(K-1)(K-2)...1}$ で計算できる。
$N(N-1)...(N-K+1)$ に含まれる素因数 $p$ の個数が $x$、$K(K-1)...1$ に含まれる素因数 $p$ の個数が $y$ 個だった場合、
$\dbinom{N}{K}$ に含まれる素因数 $p$ の総和は $x-y$ となる。
素因数毎にこれを求め $x-y+1$ の総積を取れば答え。
区間篩
$L~R$ の連続した整数を高速に全て素因数分解する方法。
(厳密には、区間篩とだけ言ったときはその中にある素数を列挙するアルゴリズムを指すのが一般的で、
素因数分解はちょっとだけ発展となる)
$R$ が大きく、$R-L$ が線形探索可能な程度の場合に有効。
今回は、$L~R$ を全てかけあわせた時の素因数がわかればよいので
各数値を個別に素因数分解する必要は無く、全てまとめた素因数の個数がわかればよい。
今回の問題にあわせて $L=N-K+1,R=N$ とする。
まず、$\sqrt{R}$ までの素数を列挙する。(計算量 $O(\sqrt{R} \log{\log{R}})$)
次に、$L~R$ の値を列挙した配列を作成する。
L=205 R=215
[ 205 206 207 208 209 210 211 212 213 214 215 ]
p = 2,3,5,7,... から順番に、以下を行う
【p=2】
・範囲内で最初のpの倍数を求める ceil(L/2) * 2 = 206
・そこからpごとの位置にある数字をpで割れるだけ割っていき、回数を記録する
206 208 210 212 214
↓1回 ↓4回 ↓1回 ↓2回 ↓1回 9回
[ 205 103 207 13 209 105 211 53 213 107 215 ]
→L~Rを全て掛け合わせた数に含まれる素因数2の個数は 9 個
【p=3】
・範囲内で最初のpの倍数を求める ceil(L/3) * 3 = 207
・そこからpごとの位置にある数字をpで割れるだけ割っていき、回数を記録する
207 105 213
↓2回 ↓1回 ↓1回 4回
[ 205 103 23 13 209 35 211 53 71 107 215 ]
→L~Rを全て掛け合わせた数に含まれる素因数3の個数は 4 個
これを列挙した全素数で繰り返す。
結果がこうなる
[ 41 103 23 1 19 1 211 53 71 107 43 ]
残っている2以上の数は素数である。
素数でないとしたら $\sqrt{R}$ 以上の数の合成数ということになるが、必ず $R$ を超過してしまい矛盾する。
この中で要素毎にカウントを取れば、残りの素因数とその個数もわかる。
$K \gt \sqrt{R}$ の場合は同じ素数が残る場合がある点に注意。
または、最初に素数列挙する段階で上限を $\max(K,\sqrt{R})$ としておけば、残る素数は必ず重複しなくなる。
$1~K$ の区間にも同じことをやれば答えが求まる。
この部分の計算量は評価が難しいが、$M=\max(K,\sqrt{R})$ として、$M \log{\log{M}}$ となるらしい。
Python3
def get_primes(n):
""" nまでの素数リスト """
candidates = [0, 1] * (n // 2 + 1)
if n % 2 == 0:
candidates.pop()
candidates[1] = 0
candidates[2] = 1
for p in range(3, int(n ** 0.5) + 1, 2):
if candidates[p]:
for m in range(p * p, n + 1, 2 * p):
candidates[m] = 0
return [p for p, b in enumerate(candidates) if b]
n, k = map(int, input().split())
MOD = 998244353
primes = get_primes(10 ** 6)
offset = n - k + 1
factor_remaining = list(range(offset, n + 1))
ans = 1
for p in primes:
if p > n:
break
tmp = 0
q = p
while q <= n:
s = ((offset - 1) // q + 1) * q - offset
for i in range(s, k, q):
factor_remaining[i] //= p
tmp += 1
q *= p
q = p
while q <= k:
tmp -= k // q
q *= p
ans = ans * (tmp + 1) % MOD
ans *= pow(2, sum(r > 1 for r in factor_remaining), MOD)
ans %= MOD
print(ans)
H - Eat Them All
問題
$3 \times 3$ の各マス $(i,j)$ に、猫缶がそれぞれ $A_{i,j}$ 個置かれている
1匹の猫が左上 $(1,1)$ にいて、以下の要領で移動を繰り返す
猫が全ての猫缶を食べ終えて $(1,1)$ で移動を終了するような移動経路を1つ構築せよ
$1 \le A_{i,j} \le 100$
解法
方針
マスを $(i,j)$ の2つの数字で表すのは冗長なので、説明上は以下のように番号を振りなおす。
⓪①②
③④⑤
⑥⑦⑧
あるマスに入ってきて出る、という操作で猫缶を1つ消費するので、
「マスを頂点とし、全ての頂点 $i$ に $A_i$ 本の辺が入り $A_i$ 本の辺が出る有向連結グラフ」を作り、
その全辺を一筆書きでなぞれるルート(オイラー閉路)を構築すればよい。
ルート構築は、そのようなグラフが作れたなら必ず出来る。
有向オイラー閉路の条件が、「頂点の入次数=出次数」が全頂点について満たされるかなので。
①から出た $A_1$ 本の辺が、隣接マスの⓪、②、④にそれぞれ何本ずつ向かうか、というのを各マスについて決めたい。
これは最大流で解ける。
in out S→各マスin、各マスout→T には、容量=Ai の辺を張る
,- ⓪ ⓪ -,
|- ① ① -| 各マスin→各マスout へは、隣接頂点間に容量INFの辺を張る
S-|- : : -|-T (図では表現しきれないので省略)
|- ⑦ ⑦ -|
`- ⑧ ⑧ -'
ここで、構築するグラフは向きを無くして「各頂点から $2A_i$ 本の辺が出た、無向連結グラフ」でもよい。
「各頂点から偶数本の辺が出た無向グラフ」でも必ずオイラー閉路を作れるし、その一例の構築方法も大きく変わらない。
その場合、グリッドが二部グラフであることを利用し、もう少し最大流を解くグラフを簡潔にできる。
(元から大して複雑でもないが)
,- ⓪ ① -, S→偶数頂点、奇数頂点→T には、容量=2Ai の辺を張る
|- ② ③ -|
S-|- ④ ⑤ -|-T 偶数頂点→奇数頂点 へは、隣接頂点間に容量INFの辺を張る
|- ⑥ ⑦ -' (図では表現しきれないので省略)
`- ⑧
$S→T$ へ最大流を流して、$A_i$ の総和分流せなければ不可能。
流せたら、流し終わった後のネットワークに、どの辺にどれだけ流したかの情報が残っている。
⓪→①に流量5を流していれば、目標の連結グラフでは⓪を出て①に入る辺を5本作ればよいことになる。
ただし最大流に任せると連結性が保証されない。
⓪→①⇄② こんなんでも解となり得てしまう
↑ ↓
③←④ ⑤
⇅
⑥⇄⑦⇄⑧
あらかじめ、外周をぐるっと1回だけループさせると決めうてばよい。
($A_4$ を除く $A_i$ を1ずつ減らしてフローを解き、グラフに反映させる段階で戻す)
⓪→①→②
↑ ↓
③ ④ ⑤
↑ ↓
⑥←⑦←⑧
各辺をこの向きに最低1回使うというのが重要で、実際に通る順番はバラバラでよい。
④は必ず①③⑤⑦のどれかと接続されるため、これで連結性は保証される。
「いやいや、⓪→①の辺を張ったら破綻するけど、使わなければ上手く流せるケースがあるんじゃないの?」と思うが、
どのような成立状態でも上手く辺の結び方と方向を変えることで、外周一周を使う成立状態に変換可能である。
証明
⓪→①の辺を使わないで条件を満たすルートで、
⓪→①を代わりに使う形に変換できないものを考え、それが存在しないことを示す。
グリッドの回転・反転、辺の向きの一斉反転を使えば、この1箇所だけ証明できれば十分。
以下のような図を使って、使わないことが確定した辺、使うことが確定した辺を決めていく。
→ → これ以降の図で、対応する位置に
⓪ ← ① ← ② ・矢印が書かれている: 使うことが確定した辺
↑↓ ↑↓ ↑↓ ・×印が書かれている: 使わないことが確定した辺
③ → ④ → ⑤ ・何も書かれていない: 未決定の辺
← ← とする。
以上を守って辺を変えても、⓪→①を使うようにできないものを考える。
×
⓪ ① ② ⓪→①を使わないとした場合、
↓ Ai >= 1より⓪から1本は辺が出るので、
③ ④ ⑤ ⓪→③の辺を使うことが確定する
【①→⓪を使う場合】
×
⓪ ← ①(←)② 現在の状態は条件を満たす(オイラー路を構築できる)ので、
↓ (↑) ①→⓪を通って①に戻る、交差しない閉路が必ず存在する。
③(→)④(→)⑤ (図は一例)
→ →
⓪ ① ② それを全て反転させることで⓪→①の辺を作れる。
↑ ↓ 反時計回りを時計回りに変換するので、他の外周辺を失うことはない。
③ ④ ⑤
← ←
よって、①→⓪の辺も使えないことがわかる。そして③→⓪の辺を使うことが確定する。
×
⓪ × ① ②
↑↓
③ ④ ⑤
【④→①を使う場合】
×
⓪ × ① ②
↑↓ ↑ ⓪→③ と ④→①のように互い違いの関係にある平行な2辺は、
③ ④ ⑤
→
⓪ × ① ② こう繋ぎ替えられる。
↑ つなぎ替えることで連結で無くなる可能性を考慮しなければならないが、
③ ④ ⑤ ③→⓪を使うことが確定しているため、連結は保たれる。
←
【①→④を使う場合】
×
⓪ ← ① ② 同様に、こう繋ぎ替えられる。
↓ 更に先ほどの、閉路の辺反転を使うことで、⓪→①の辺を作れる。
③ → ④ ⑤ 一時的に外周辺③→⓪を失うが、これを含めて辺反転させればよい。
よって、①→④、④→①の辺も使えないとなる。
すると、①を他と連結にするためには、②、⑤と連結するしか無くなる。
× →
⓪ × ① ← ②
↑↓ ×× ↑↓
③ ④ ⑤
以下、同様の議論が④⇄⑤にも適用され、これらの辺も使えないとなる。
すると⑤は連結を保つため、⑧、⑦と連結になる。
× →
⓪ × ① ← ②
↑↓ ×× ↑↓
③ ④ × ⑤
↑↓
⑦ → ⑧
←
これを繰り返すと、④⇄⑦、③⇄⑦ の辺も使えなくなり、④が孤立する。
よって矛盾する。
証明はそれなりに煩雑な場合分けが必要なため、公式Editorialの通り、
必ず流すと決める全域木を全探索したり、ランダムでフローの流し方を何通りか試す方が考察は速そう。
各頂点間の辺数が決まったら、あとはオイラー閉路の構築となる。
これは、DFSの帰りがけ順で通過頂点を記録するとよい。
同じ頂点間に辺が複数本あり、頂点ではなく辺について網羅しないといけないため、よくあるDFSとは若干コードが異なる点に注意。
複数本無ければ点と辺を逆転させて考える手もありだが、複数本ある場合は辺の数が大量にできてしまう。
10本 10本 このようなグラフで点と辺を逆転させた場合、
⓪ --→ ① --→ ② ① にどの辺から入ってどの辺から出るか、10 x 10 通りの辺を張らないといけない?
解法2
答えの1つには外周を一周するものが必ず存在するとわかったので、それをベースとしてもよい。
⓪1①3②
12 2 4 数字の順に、往復しながら移動する
③11④5⑤
10 8 6
⑥9⑦7⑧
各頂点が周囲の隣接マスとそれぞれ何回往復するか(合計で、外周マスは $A_i-1$ 回、④は $A_i$ 回)は最大流で求められる。
こうすると、オイラー閉路の構築が楽になる。
Python3
from collections import deque
class Dinic:
"""
Usage:
mf = Dinic(n)
-> mf.add_link(from, to, capacity)
-> mf.max_flow(source, target)
"""
def __init__(self, n):
self.n = n
self.links = [[] for _ in range(n)]
def add_link(self, from_, to, capacity):
self.links[from_].append([capacity, to, len(self.links[to])])
self.links[to].append([0, from_, len(self.links[from_]) - 1])
def bfs(self, s):
depth = [-1] * self.n
depth[s] = 0
q = deque([s])
while q:
v = q.popleft()
for cap, to, rev in self.links[v]:
if cap > 0 and depth[to] < 0:
depth[to] = depth[v] + 1
q.append(to)
return depth
def dfs(self, s, t, depth, progress, link_counts):
links = self.links
stack = [s]
while stack:
v = stack[-1]
if v == t:
break
for i in range(progress[v], link_counts[v]):
progress[v] = i
cap, to, rev = links[v][i]
if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
continue
stack.append(to)
break
else:
progress[v] += 1
stack.pop()
else:
return 0
f = 1 << 60
fwd_links = []
bwd_links = []
for v in stack[:-1]:
cap, to, rev = link = links[v][progress[v]]
f = min(f, cap)
fwd_links.append(link)
bwd_links.append(links[to][rev])
for link in fwd_links:
link[0] -= f
for link in bwd_links:
link[0] += f
return f
def max_flow(self, s, t):
link_counts = list(map(len, self.links))
flow = 0
while True:
depth = self.bfs(s)
if depth[t] < 0:
break
progress = [0] * self.n
current_flow = self.dfs(s, t, depth, progress, link_counts)
while current_flow > 0:
flow += current_flow
current_flow = self.dfs(s, t, depth, progress, link_counts)
return flow
def solve(grid):
if sum(grid[0::2]) != sum(grid[1::2]):
return False
path = [[i] for i in range(9)]
for i in range(9):
if i != 4:
grid[i] -= 1
mxf = Dinic(11)
s = 9
t = 10
for i in range(9):
if i % 2 == 0:
mxf.add_link(s, i, grid[i])
if i < 6:
mxf.add_link(i, i + 3, 100)
if i % 3 < 2:
mxf.add_link(i, i + 1, 100)
else:
mxf.add_link(i, t, grid[i])
if i < 6:
mxf.add_link(i + 3, i, 100)
if i % 3 < 2:
mxf.add_link(i + 1, i, 100)
flow = mxf.max_flow(s, t)
if flow != sum(grid[0::2]):
return False
for i in (1, 3, 5, 7):
for link in mxf.links[i]:
j = link[1]
if j == t or link[0] == 0:
continue
path[i].extend([j, i] * link[0])
grid[i] -= link[0]
whole_path = []
for i in (0, 1, 2, 5, 8, 7, 6, 3):
whole_path.extend(path[i])
whole_path.append(0)
ans = []
for i, j in zip(whole_path, whole_path[1:]):
if i - j == 1:
ans.append('L')
elif i - j == -1:
ans.append('R')
elif i - j == 3:
ans.append('U')
elif i - j == -3:
ans.append('D')
else:
raise AssertionError
return ''.join(ans)
grid = []
for _ in range(3):
grid.extend(map(int, input().split()))
ans = solve(grid)
if ans == False:
print('NO')
else:
print(ans)