$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)
$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)
色が同じペアが $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$ に対する色の塗り方のパターン数となる。
あとは、$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)
正しい括弧列の判定は、定石としては '(' を +1、')' を -1として前から計算していったとき、以下の2つを満たすものである。
+1,-1するのは、「今、いくつの括弧を開いているか」と言い換えてもよい。
従って、各文字列につき、重要なのは以下の2つで、この他の情報は捨ててしまってよい。
m t (() ... ( 0, 1) )((( ... (-1, 2) ()))) ... (-3, -3)
とりあえずまずは、$t$ の総和が0以外なら、'(' と ')' の数が釣り合ってないのでアウト。
以下、釣り合っているとする。
連結する順番を決めたとき、破綻するかどうかは、以下のように判定できる。
さて、ではどう順番を決めればよいか。
とりあえず、まずは $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出してた）
直前まで別の言語に触れてると、この辺って混乱することあるよね！（気付けよ）