目次
AtCoder Beginner Contest 167 C～F問題メモ
C - Skill Up
問題
- 本が $N$ 冊あり、それぞれアルゴリズム $1～M$ について学べる
- 本 $i$ の価格は $C_i$ 円で、読むと各 $j=1～M$ についてアルゴリズム $j$ の理解度が $A_{i,j}$ 進む
- 今、全てのアルゴリズムの理解度は0
- 全てのアルゴリズムの理解度を $X$ 以上にするために必要な金額の最小値を求めよ
- $1 \le N,M \le 12$
解法
$N$ が小さいので、どの本を買って、どの本を買わないか $2^N$ 通りを全て試せばよい。
1回試すのに $O(NM)$ かかるが、$O(2^NNM)$ は最大値を当てはめても60万程度なので十分高速。
組み合わせを順に列挙していくのはbit演算を用いてもよいが、Pythonなら時間に多少余裕がある場合は、itertools.product() を使うと復元が楽になる。
n = 4
for books in product([False, True], repeat=n):
print(books)
# =>
# (False, False, False, False)
# (False, False, False, True)
# (False, False, True, False)
# (False, False, True, True)
# ...
さらに、NumPyを使うとこのようなbool値のlistによる配列アクセスはTrueの行のみを抽出する操作となるので、買う本のみの抽出を簡潔に書くことができる。
cost = np.array([10, 20, 30, 40]) cost[[True, False, True, False]] # => [10 30] cost[[True, False, True, False]].sum() # => 40
from itertools import product
import numpy as np
n, m, x = map(int, input().split())
cost = []
aaa = []
for _ in range(n):
c, *a = map(int, input().split())
cost.append(c)
aaa.append(a)
cost = np.array(cost, dtype=np.int64)
aaa = np.array(aaa, dtype=np.int64)
ans = 10 ** 18
for books in product([True, False], repeat=n):
books = list(books)
if (aaa[books].sum(axis=0) >= x).all():
ans = min(ans, cost[books].sum())
if ans == 10 ** 18:
print(-1)
else:
print(ans)
D - Teleporter
問題
- $N$ 個の街がある
- 各街にはテレポーターが1個ずつあり、街 $i$ からは街 $A_i$ にテレポートする
- 街 $1$ から $K$ 回移動を繰り返すと、どの街に着くか答えよ
- $2 \le N \le 2 \times 10^5$
- $1 \le K \le 10^{18}$
解法
$K$ が大きすぎるのでシミュレーションは無理だが、街の数からして必ずどこかでループする。
1 → 6 → 4 → 5
↑ ↓
2 ← 3
各街につき、街1からのテレポート回数を保存しておいて、既に回数が求まっている街に再び着いたとき、そこがループ起点となる。
ループを検出するとそこから「街1からループにたどり着くまでの移動回数 $s$」「ループの周期 $\lambda$」を計算できる。
もちろん、ループになる前に $K$ 回に達した場合はそれが答え。
それ以外では、$(K-s) / \lambda = d あまり m$ とすると、ループは $d$ 周し、残り $m$ 回移動すればよいことになる。
つまり、街1から数えると、$s+m$ 回移動した先が答え。これがどの街になるかは、最初にループを検出するまでに求まっている。
import sys
n, k, *aaa = map(int, sys.stdin.buffer.read().split())
shortest = [-1] * n
v = 0
d = 0
while shortest[v] == -1:
shortest[v] = d
v = aaa[v] - 1
d += 1
if d == k:
print(v + 1)
exit()
first = shortest[v]
loop = d - first
remaining = (k - first) % loop
ans = shortest.index(remaining + first) + 1
print(ans)
ダブリングによる解法
こっちの方が計算量は若干かかるが、$K$ がループ未満だったらとか細かなこと気にしないで短く書ける。
初期状態の $A$ は1回だけ移動した先だが、各 $i$ につき $B[i]=A[A[i]]$ とすることで、$B$ は各街から2回移動した先を表す。
さらに $C[i]=B[B[i]]$ で4回先、さらに8回、16回、32回……と倍々の移動先を計算していける。
さて、$K$ がたとえば49だったら、これを2のべき乗の和で表すと $49=1+16+32$ なので、1回移動→16回移動→32回移動、とすれば49回移動したことになる。
16回分の移動、32回分の移動というのは上記の方法で一気に計算できるので、都市1からの移動は実質3回しか行わないで済む。（32回分移動の配列を求めるのは必要だが）
$K \le 10^{18} \lt 2^{60}$ なので、最大値であっても2倍2倍を繰り返したら多くとも60回の移動の計算で済み、時間内に間に合う。
import sys
n, k, *aaa = map(int, sys.stdin.buffer.read().split())
aaa = [0] + aaa
p = 1
while k:
if k & 1:
p = aaa[p]
aaa = [aaa[a] for a in aaa]
k >>= 1
print(p)
E - Colorful Blocks
問題
- $N$ 個のボールを一列に並べ、それぞれを $M$ 種類の色のどれかで塗る
- 隣り合う2つのペア（$N-1$ 個ある）のうち、2つの色が同じペアが $K$ 個以下になるような色の塗り方のパターン数を求めよ
- $1 \le N,M \le 2 \times 10^5$
解法
色が同じペアが $k$ 個ちょうどのとき、どうなるか？
色が同じのを -- で結ぶ N=8 k=3 o o o -- o -- o o o -- o 色の選び方 M M-1 `-- M-1 --' M-1 ` M-1 ' = M * (M-1)^4
「--」で結んだものは同じ色だから、まとめて1色を選べばよい。 最初以外は、1つ前の色と被らない色を選べばよいので、$M-1$ 通りから1色選ぶ。
色の選び方は、どのペアを同じにしようが $k$ が同じなら同じで、
o -- o o -- o o o -- o o `- M -' ` M-1 ' M-1 ` M-1 ' M-1 = M * (M-1)^4
なので、各 $k$ につき、以下の2つを掛け合わせたものが、その $k$ に対する色の塗り方のパターン数となる。
- $N-1$ 箇所のペアから、色を同じにするペアの選び方: ${}_{N-1}C_{k}$ 通り
- 色の塗り方: $M \times (M-1)^{N-k-1}$ 通り
あとは、$k=0～K$ までの結果を足し合わせればよい。
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
n, m, k = map(int, input().split())
MOD = 998244353
facts, invs = prepare(n, MOD)
ans = 0
for s in range(k + 1):
p = n - s
ans = (ans + m * pow(m - 1, p - 1, MOD) * facts[n - 1] * invs[s] * invs[n - s - 1]) % MOD
print(ans)
F - Bracket Sequencing
問題
- '(' と ')' からなる文字列が $N$ 個与えられる
- 好きな順に連結できる
- 上手く順番を決めて、全て連結した結果を正しい括弧列にすることが可能か判定せよ
- 正しい括弧列の定義は問題ページ参照
解法
正しい括弧列の判定は、定石としては '(' を +1、')' を -1として前から計算していったとき、以下の2つを満たすものである。
- 途中で1度も0未満にならない
- 最終結果が0
+1,-1するのは、「今、いくつの括弧を開いているか」と言い換えてもよい。
従って、各文字列につき、重要なのは以下の2つで、この他の情報は捨ててしまってよい。
- 一番最初を0として、
- $m$: どこまで下がるか（途中で取り得る最小値）
- $t$: 最終的な相対位置
m t (() ... ( 0, 1) )((( ... (-1, 2) ()))) ... (-3, -3)
とりあえずまずは、$t$ の総和が0以外なら、'(' と ')' の数が釣り合ってないのでアウト。
以下、釣り合っているとする。
連結する順番を決めたとき、破綻するかどうかは、以下のように判定できる。
- 開いている括弧の数を保持する変数を $x$ とする。最初、$x=0$
- foreach 連結する文字列 $(m, t)$
- $x+m \lt 0$ なら、途中で0となるためアウト
- $x←x+t$
- 最後まで破綻しなければ可能
さて、ではどう順番を決めればよいか。
とりあえず、まずは $t$ が正のものを集めて、括弧を開けるだけ開いておいた方が安全な気がする。
証明は後でするとして、まずはそれで文字列を分類する。
すると、$t$ が正の中では連結するたびにどんどん括弧は開いていくので、$m$ が小さければ後回しにして、より括弧が開いた後に連結させた方がよい。
m t )))))(((((((( (-5, 3) ← xが5以上の状態で連結する必要がある ()()()( ( 0, 1) ← xが0以上の状態なら連結して大丈夫
よって、$m$ の降順にソートして連結させればよい。それでも無理なら無理である。
$t$ が負のものは、右から考えれば ')' で開き '(' で閉じることになるので、見る向きと意味合いを反転させれば正と同じように考えられる。
これで、貪欲に並び順を決めることができた。
$t$ が正のものだけを先に集めてくっつけて、負のものを後に集めるのが、正しいか確認する。この並べ方を「並び順1」とする。
一部の $t$ が負のものを先に持ってくれば本来可能なのに、並び順1では不可能と判定されてしまうケースがあったとする。この時の並べ方を「並び順2」とする。
$m$ の値は捨て置いて、$t$ だけで $x$ の増減グラフを書くと、並び順1は必ず1つの山、2では一部に谷ができる。
並び順1 並び順2
| ／＼ |
| ／ ＼ | ／＼
| ／ ＼ | ／＼／ ＼
|／ ＼ |／ ＼
+--------------------- +---+------+---------
| |←並び順1との差分
さて、並び順1で破綻した文字列を、$s_1=(m_1,t_1)$ とする。$t_1$ は正とする。（負でも前後反転させれば一緒）
グラフ上では「／」として表されている中の1つである。
並び順1で破綻ということは、判定処理の途中で $x+m_1 \lt 0$ になった、つまり $s_1$ の処理までに $x$ を $m_1$ 以上にできなかったということ。
これを、並び順2で $m_1$ 以上にできるか？
途中で負なんて挟み込んでいるので、余計に無理である。
よって、矛盾するので、$t$ が正のものを先に固めてしまって問題ない。
def check(pt, brackets):
brackets.sort(reverse=True)
for m, t in brackets:
if pt + m < 0:
return -1
pt += t
return pt
n = int(input())
brackets_p = []
brackets_m = []
pt = 0
mt = 0
for _ in range(n):
s = input()
total = 0
mini = 0
for c in s:
if c == '(':
total += 1
else:
total -= 1
mini = min(mini, total)
if total >= 0:
if mini == 0:
pt += total
else:
brackets_p.append((mini, total))
else:
total, mini = -total, mini - total
if mini == 0:
mt += total
else:
brackets_m.append((mini, total))
pt = check(pt, brackets_p)
mt = check(mt, brackets_m)
if (pt == -1) or (mt == -1) or (pt != mt):
print('No')
else:
print('Yes')
Pythonでは 0 == False はTrueです。（check()の破綻したときの戻り値をFalseにして、0の時と区別できなくてWA出してた）
直前まで別の言語に触れてると、この辺って混乱することあるよね！（気付けよ）
