$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出してた)
直前まで別の言語に触れてると、この辺って混乱することあるよね!(気付けよ)