ウマ娘 ミホノブルボン 育成
ミホノブルボンでURA優勝したのでその時の記録を残します
最終ステータス
ついさっき気付いたけど長距離適性がBだったりするのでそこは因子で補正してあげると勝ちやすいかも
方針
〜春天
スタミナ＞スピード＝根性＝賢さ＞パワー
それ以降〜
スピード＞賢さ＝スタミナ＞根性＝賢さ
今回の場合では最初はどれもバランス良く伸ばしていったが、メジロマックイーンやトウカイテイオーなどのように途中で春天（3200m）が挟まるので、それまではスタミナを重視しつつ、それ以降はスピードや賢さなどに振った。スタミナに関して言えば、春天皇までに円弧のマエストロが獲得できれば400で足りるが、獲得できなければ450~500まで伸ばさないと厳しい。
サポートは色々と考えたが、スピードばかり伸ばしても根性が足りずに途中で順位を落としたりすることや、スタミナが後々必要になってくること、そしてパワーを上げることによって（気持ち）最終コーナーを一着で回ってこれることが多くなった気がしたので、スピード2、スタミナ1、パワー1、根性1とした（開いたところはたづなさんを入れた）
育成の流れ
継承のタイミングはスプリングS直後と春天直前なので、それを見越してスキルを取っていきたい。
5回くらいやってみて、どうやら春天を突破するにはスタミナ480、スピード400（円弧のマエストロなし）が必要っぽそう。最難関は最後の有馬1着で（正味URAよりムズいんじゃないか？）、どう頑張っても4番人気くらいまでしかなれなかったしここで2回コンティニューすることになった。有馬はスピード600、根性450、賢さ500くらいは欲しいところ。
区切り感としては、
・日本ダービー（オール300）
・春天（スピード400、スタミナ480）
・ジャパンカップ（スピード600、根性450、賢さ500）
をイメージしていた。
URAの距離
ミホノブルボンのストーリーの都合上、最初はマイルから始まって次第に中、長距離を走ることになるので、URAに進出した際にどのくらいの距離を走らされるのかが微妙な部分になる。
2回URAまで出た時点で、出走したレースによって
短0 マ2 中2 長3でURAはマイル（1800m）
短0 マ3 中3 長4でURAは中距離（2200m）
になったので、スタミナを伸ばしてURAで長距離走らせたいとなると相当長距離レースに出走させなければダメそうな気がする。
ログ
（凡例）
スピード-スタミナ-パワー-根性-賢さ
順位
メイクデビュー（スキル:先駆け）
192-182-151-208-203 ◎◎○◎◎
2
TS（スキル:コーナー回復）
274-210-233-222-241 ◎○○◎◎
1
スプリングS（スキル:逃げ直線○）
320-232-284-235-287 ◎○◎◎◎
1
皐月
337-245-287-239-291 ◎○◎○◎
1
日本ダービー（スキル:サイレンススズカの固有スキル「先頭の景色は譲らない...！」）
340-275-390-351-299 ◎○○○○
1
菊花賞
395-347-358-329-312 ◎○◎○○
3
天皇賞（春）（スキル:アイネスフウジンSSRのサポカ「じゃじゃウマ娘」）
437-489-384-377-365 ◎○○○○
1
ジャパンカップ
546-513-450-458-470 ◎◎○◎○
1
有馬（スキル:円弧のマエストロ）
557-516-458-461-464-506 ○△△○△
2->2->1
URA予選2200m
564-519-461-464-506 ◎○○○◎
1
URA準決勝（スキル:末脚）
575-530-472-470-517 ○○x△◎
1
URA決勝
590-541-487-490-528 △○x○○
5->1
ウマ娘 トウカイテイオー 育成
最近ハマってアニメも一瞬で追いついてしまったウマ娘なのですが、トウカイテイオーの育成がメチャムズだったので成功した例を記録したいと思います。
最終ステータス
トウカイテイオー、かわいいね。
方針
ステータス
スピード>>パワー=根性=賢さ>スタミナ
だいたい最終目標が650-400-500-500-500くらいなので、そんな感じになるように育てる
スキル
必須：円弧のマエストロ
あると良い：マックイーンの固有スキル（「貴顕の使命を果たすべく」を継承で手に入れる）、右回り◎、末脚
長距離（菊花、天皇）はスタミナが330あれば円弧のマエストロありで勝てる 大体最後に伸びずに負けるのは根性が足りないためなのでスタミナよりは根性を伸ばす方向で育成する（そうしないと後は中距離ばかりなのでステイヤー路線だとキツい）
その他
途中で春天皇とかの長距離が挟まるが、それはスキル「円弧のマエストロ」でカバーできるのでスタミナxでもなんとかなる
バランスよく育てるのもアリかもしれないが、最後の有馬でシンボリルドルフに押し負けるのでスピードと根性がある程度ないとダメ
育成の流れ
基本的にスピードを重視してトレーニングさせながら、根性を伸ばすトレーニングをする（根性トレーニングはスピード・パワーも伸びるのでお得）
スタミナを伸ばす時はパワーのトレーニングで一緒に伸ばせるのでそれで伸ばすように
ログ
（凡例）
スピード-スタミナ-パワー-根性-賢さ
順位
若駒
284-162-210-257-237 ◎○◎◎◎
1
皐月
336-167-240-291-285 ◎x○◎◎
1
日ダ
339-188-243-301-288 ◎△△◎◎
2
菊花
434-233-322-379-307 ◎x◎◎○
2
天皇
434-233-322-379-307 ◎x◎◎○
2
ジャパンC
609-366-471-472-448 ◎△○◎◎
1
有馬
618-369-474-475-466 ◎x○◎○
（3->1 最初はシンボリルドルフじゃなくてスペシャルウィークに負けた）
URA予選
626-372-481-489-469 ◎x○◎○
1
URA準決勝
643-384-493-501-498 ◎xx○○
1
URA決勝
675-396-511-513-510 ◎xx○△
1
チュウニズム クリスタル（プラス）までを振り返って
ベスト枠平均が15.8343でした。去年の12月にはMAX15.8を達成しました。
ベスト枠詳細↓
下限から15.7を追い出したりして、ゆっくりながら(この一年で700クレやっていました)まあまあ成長できたかなあとは思います。
11月にリングフィットアドベンチャーをやり始めてからは特に成長した気がします。筋肉がついて多少のことでは腕がへこたれなくなったり、指先に力が入るようになってそれなりに正確にノーツを押せるようになったことが原因かと思います。
正直初めて一週間くらいで神威が7200出たのはびっくりしたし、この曲は腕にどれだけ力を入れ続けられるかの（瞬発力よりは）持久力をかなり問うてくる曲だと思います。
しかし未だに京急はSSSが取れません。どうして…………………………………………………………………………………………………………………………
次回作のチュウニズムパラダイスも楽しみです。
Pythonの深さ優先探索で失敗した話
ハミルトン閉路が存在するか判定する問題。入力は、
n m
x_1 y_1
x_2 y_2
... ...
x_m y_m
で与えられる。（nは頂点数、mは辺の数。x_i,y_iは頂点x_iとy_iを結ぶ辺が存在することを表す）
#合ってるコード(しかしこれもn=15くらいだと落ちるね......) n,m = map(int,input().split()) edge = [] for i in range(n): T = [0]*n edge.append(T) for i in range(m): x,y = map(int,input().split()) edge[x][y] = 1 edge[y][x] = 1 def dfs(cur, checked, rest): #curは現在いる点、checkedは訪れた点、restはこれから訪れる点 if len(rest) == 0: if edge[cur][0] == 1: #全点探索が終了したら、現在いる点と点0の間に辺があるかどうかを判定 print('Yes') exit() else: for i in range(n): if edge[cur][i] == 1: if (i in rest) and (i not in checked): L = [] for j in range(len(rest)): if rest[j] != i: L.append(rest[j]) temp = [i] for j in range(len(checked)): temp.append(checked[j]) #ここcopyに注意 dfs(i, temp, L) P = [i for i in range(1, n)] #これから訪れる頂点のリスト dfs(0, [], P) #点0からスタート print('No')
間違えた理由はいくつかあって、まず
・dfsを同じ深さのfor文でやると、前の処理がそのまま後ろのfor文に引き継がれる（同時並行で進むわけではない）
・pythonの = は参照渡し（なので値だけコピーしたいならdeepcopyを使わないといけないけど、deepcopyはバカ遅い）
#間違っているコード n,m = map(int,input().split()) edge = [] for i in range(m): s,e = map(int,input().split()) edge.append([s,e]) def dfs(cur, checked, rest): if len(rest) == 1: flag = False for i in range(len(edge)): if edge[i][0] == 0: if edge[i][1] == rest[0]: flag = True break elif edge[i][1] == 0: if edge[i][0] == rest[0]: flag = True break if flag: return True else: return False else: flag = False for i in range(len(edge)): temp = checked if edge[i][0] == cur: if edge[i][1] in rest: if edge[i][1] not in checked: flag = True L = [] for j in range(len(rest)): if rest[j] != edge[i][1]: L.append(rest[j]) temp.append(edge[i][1]) return dfs(edge[i][1], temp, L) elif edge[i][1] == cur: if edge[i][0] in rest: if edge[i][0] not in checked: flag = True L = [] for j in range(len(rest)): if rest[j] != edge[i][0]: L.append(rest[j]) temp.append(edge[i][0]) return dfs(edge[i][0], temp, L) if not flag: return False P = [i for i in range(1, n)] if dfs(0, [], P): print('Yes') else: print('No')
復習 4/18,4/19
O(n)で前計算することで、各nCrをO(1)で求められるようにする。
mod = 10**9+7 MAX = 10**5+1 #nは10**5までを想定 fact = [1]*(MAX+1) for i in range(1, MAX+1): fact[i] = (fact[i-1]*i)%mod inv = [1]*(MAX+1) for i in range(2, MAX+1): inv[i] = inv[mod%i]*(mod-mod//i)%mod fact_inv = [1] * (MAX + 1) for i in range(1, MAX + 1): fact_inv[i] = fact_inv[i-1]*inv[i]%mod def comb(n, r): if n < r: return 0 return fact[n]*fact_inv[n-r]*fact_inv[r] % mod
atcoder.jp
例えば(10**5)**(10**5)を10**9+7で割りたい、みたいな気持ちになった時に、for文で10**5を10**5回回してるとどエライ事になってしまう。a**bをmで割った余りは、pow(a,b,m)で高速に求められる。
atcoder.jp
ナップサックはi番目のものまで見たときに使う、使わないのふた通りの場合分けをちゃんと行うこと。サボるとどっかでミスる。
復習 4/9,4/10,4/11
1からkまでのiに対して、
・「i回目に働くのは一番早くて何日目？」
・「i回目に働くのは一番遅くて何日目？」
というのを格納した配列A,Bを考える。いずれも、oxの列を前から、後ろから見ていくことで可能。
結論から言うと、A,Bについて、A[i] == B[k-i-1]となる日付が「働くべき日」に該当する。
例えば、ooxoxoxoという配列で、「必ず1日以上開けて働かなくてはいけない」という制約をつけたらどうだろうか。
働く日数が二日であれば、上の配列はそれぞれ、
[0,3]
[5,7]
となることだろう。1回目に働くのは、遅くとも5日目に働けばいい。そう考えると、0,1,3日目に働く必要はない。同様に、0日目に働いてもいい。そうすれば、5日目を待たずとも二回仕事を終えることもできる。
以上より、「必ず働く日」というのは存在しない。
働く日数が三日であれば？ 配列はそれぞれ、
[0,3,5]
[7,5,3]
となる。この場合も、実は働くべき日は存在しない。2回目に働く日は3,5日目のいずれかから選ぶことができるし、選んだ日付によって、例えば2回目に働く日を3日目にすれば、1回目、3回目に働く日はそれぞれ0と(5,7)日目になるし、5日目を選べば、1回目、3回目に働く日はそれぞれ(0,1,3)と7日目になるからだ。
最後に、働く日が四日であれば、配列は
[0,3,5,7]
[7,5,3,1]
になる。この時、最初に働く日付のみが問題になり、後の3,5,7日目については必ず働かなくてはならない。（A[i] == B[k-i-1]なので）
ということで、この場合は3,5,7日目となる。
累積GCDまでは思いついたが......という感じ。前から累積GCD取って、各クエリごとに「初めてGCDが1になるところはどこか？」を二分探索すればO(QlogN)で求まる。GCDが1にならないなら配列の最後とのGCDを求めてあげればいい。
部分列の和を求めるのはわかる。bitがk個以上立っている桁を大きい方から取ればいいのもわかる。しかし大きなbitがk個以上立っているものをまたかき集めて、その中から次の桁のbitが立っているものを選んで......とやっていると日が暮れるので、視点を「n(n+1)/2個部分和」ではなく、「k個選んできた後の論理積の最大値」に移す。これをxとすれば、二進法で表した時にたかだか40通りなので、各bitについて立てるか立てないかを、bitの大きい方から検討していけば良い。
具体的に言えば、ans = 0として、
ans = 0 for i in range(40, -1, -1): temp = ans+2**i cur = 0 for j in range(len(list_sum)): if temp&list_sum[j] == temp: cur += 1 if cur >= k: ans += 2**i
（擬似的なコードなので粗はあるけどこんな感じ）
上のような実装をしてあげればいい。ansについては過去の結果を持ち越すことになるので、「上からbitがk個以上立っている集合を選んできて、その中でまたk個以上立っているような下のbitを選んでくる」のようなことができていることになる。
めっちゃ賢い......
「ペア」なので、必ず二つの要素の組で考える。
大きい方から貪欲に、「ペア」を作れる相手を取ることを考える。（降順で固定する）
大小関係をつけることでわかることがある。例えば、今見ている要素pに対して、相手となる要素q（p>qとする）を取ってきた時、p+q=2^kとなるような2^kは、確実に2^(k-1) <= p < 2^kを満たしている。
ペアの和が2^kよりも大きい2のべき乗になることはない。例えばp<2^kとして、q = 2^(k+1)-pとすれば、p>qよりp > 2^(k+1)-pとなるので2p > 2^(k+1)となり、p>2^kから矛盾が生じる。よって、p+qでできる二のべき乗は、pより大きくて、そのなかで最も小さいような2^kに限られる（ここに気付けるかが肝心）
ここまでくれば大体OKだが、相手となる要素の個数を管理するのにpythonではCounterという便利なデータ構造がある。
例えば
from collections import Counter L = [3, 11, 14, 5, 13, 3] C = Counter(L) #Counter({3: 2, 5: 1, 11: 1, 13: 1, 14: 1}) #C[3] = 2 #C[14] = 1
となる。これを使うことで、delete()などを使わなくても要素数を減らす操作が簡単にできる。
復習 4/2,4/3
必勝法ゲー。dpで遷移を見る。「j枚目で回ってきたときに勝てるか？」をdp[j]で管理する。
取れる枚数がn種類（a_1...a_n）あったとき、dp[j-a_i]が全て「win」であれば、必ず相手に「勝てる」状態で回してしまうことになるため、dp[j] = lose
逆にdp[j-a_i]がLoseになるものが一つでもあれば、相手に「負け」の状況を押し付けることができるのでdp[j] = winとなる。
BITを真面目に使った初めての問題。文字を入れ替えたら、BITの情報だけでなく元の文字列の情報も更新するのをお忘れなく
巡回セールスマン問題。これ始点を0に固定しているけど、どの頂点から出発したとしても、必ず0は通るわけで、そのあとの道のりは全く同じになるので、別に頂点0にスタートを固定しても問題はなさそう。
すなわち、頂点i~頂点0(経路A)→頂点0~頂点i（経路B)は、B→Aとしても最小コストが変わらない。
v,e = map(int,input().split()) #v:頂点, e:辺 graph = [[] for i in range(v)] cost = [[float('inf')]*v for i in range(v)] for i in range(e): x,y,z = map(int,input().split()) cost[x][y] = z dp = [[float('inf')]*v for i in range(1<<v)] #(1<<v)-1 == 2**v-1 dp[(1<<v)-1][0] = 0 #全ての頂点を訪れて帰ってきた時（ここがゴール） for i in range(2**v-2, -1, -1): #まだ見ていない頂点集合に対して for j in range(v): #現在いる頂点から for k in range(v): #次に行く頂点について if i>>k & 1 != 1: #まだ訪れていないならば dp[i][j] = min(dp[i][j], dp[i|1<<k][k]+cost[j][k]) #dp[i|1<<k]は「kを訪れた状態」を指す。 #視点を変える。「今kにいる状態からゴールに至るのに必要なコスト」+「j→kに必要なコスト」は、 #「今jにいる状態からゴールに至るのに必要なコスト」になる（遡る） #これを「今0にいる状態からゴールに至るのに必要なコスト」まで遡って計算する。 if dp[0][0] != float('inf'): print(dp[0][0]) #まだどこも訪れていない状態から、ゴールである0を目指して進む else: print(-1)
シフト演算子が結構便利であることに気づいた。
復習 3/31,4/1
まずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決して上がらない。
何故ならば種類は多いほど満足度が上がるし、そもそも最初にK個選んだ時点で美味しい順に取っているので、i未満の種類を選ぶことによって純粋な「美味しさの和」を上昇させることが不可能なためである。
したがって、ここから
１、種類を減らさずに（★逆に言えば、現時点で食べようと思っている寿司の中にないネタを選んで）
２、交換することで満足度が上昇するか
についてを、残りのN-K個の寿司について考える。（N-K個も美味しい順にソートしておく）
交換するのは、現時点で食べようと思っている寿司のうち、同じ種類のものが二つ以上あるものに限る。なぜなら、今確保している寿司よりも、残りのN-K個の寿司の方が美味しさが小さいため、純粋な一種類・一個の寿司のトレードで満足度を向上させられない（種類ボーナスは増えないし、美味しさが減るだけ）からである。
これを、現状2個以上残っている寿司の美味しさをheapqで持っておき、新たな寿司のネタと交換することで、美味しさを増やせるかどうかを見るだけ。種類が多くなればなるほど満足度が増える訳ではないことに注意。
閉路検出。BFSするだけだけどもっとマシなコード（実装法）が知りたい。
n,m = map(int,input().split()) graph = [[] for i in range(n)] for i in range(m): u,v = map(int,input().split()) graph[u-1].append(v-1) graph[v-1].append(u-1) visited = [0]*n ans = 0 start = 0 while sum(visited) != n: while visited[start] == 1: start += 1 stack = [start] flag = True while len(stack) != 0: t = stack.pop() if visited[t] == 0: visited[t] = 1 for j in range(len(graph[t])): if visited[graph[t][j]] == 0: if graph[t][j] not in stack: stack.append(graph[t][j]) else: flag = False if flag: ans += 1 print(ans)
完全グラフから、nがoddなら[1,n-1]...を、nがevenなら[1,n],[2,n-1]...を除けばいい
は？？？？？
縦方向と横方向を一緒くたに考えようとすると混乱するので分解する。
とにかく「ゲーム終了時に盤面上に残っているには、最初にどこに駒があればいいのか？」を考えるため、操作を逆順に遡っていく。
先攻は「範囲を狭めようとする」動きをするのであんまり考えなくていいが、後手が結構ややこしい。
例えば、縦方向に見ていて先手を見終わって範囲が[2,3]だった時に（範囲は1~hとする）、後手が"D"を持ってきたら、後手がDを出して[2,3]の範囲に居られるようにするためには、後手の行動前に駒が[1,2,3]のどこかにいなくちゃいけないな〜みたいに、「後手が行動する前に駒はどこにあるべきか？」を考える。
セグメント木、BIT（反転数）
・セグメント木
書きようによっては任意の区間のGCDを求めたりもできるっぽいけど、とりあえずは任意の区間の最小値を求めることにする。
n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 t = 1 while t <= n: t *= 2 segtree = [float('inf')]*(t-1) #tはn以上で最小の2のべき乗の数 def init(LIST): for i in range(n): segtree[i+n-1] = LIST[i] #配列のi番目をセグ木のi+n-1番目（葉）に格納 for i in range(n-2, -1, -1): segtree[i] = min(segtree[2*i+1], segtree[2*i+2]) def update(k, a): #k番目（0-indexed）の値をaに変更 k += n-1 segtree[k] = a while k > 0: k = (k-1)//2 segtree[k] = min(segtree[2*k+1], segtree[2*k+2]) def query(a, b, k, l, r): #[L[a],L[b])の範囲の最小値を求める。kは今見ている節点の番号、l,rはkの対応している範囲を表す。 #L[a]~L[b]の最小値を求めたければ、query(a,b+1,0,0,n) if r <= a or b <= l: #求める場所が範囲外 return float('inf') elif a <= l and r <= b: return segtree[k] else: u = query(a, b, 2*k+1, l, (l+r)//2) v = query(a, b, 2*k+2, (l+r)//2, r) return min(u, v) init(L) print(segtree) while True: i,p,q = map(int,input().split()) #i==1でL[p]~L[q]のminを求める。i==2でL[p]をqに変更 if i == 1: print(query(p, q+1, 0, 0, n)) elif i == 2: update(p, q) print(segtree) else: break
実行例
>>8 >>5 3 7 9 6 4 1 2 [1, 3, 1, 3, 7, 4, 1, 5, 3, 7, 9, 6, 4, 1, 2] >>2 0 2 #L[0]を5から2に変更 [1, 2, 1, 2, 7, 4, 1, 2, 3, 7, 9, 6, 4, 1, 2] >>1 0 0 #L[0]の値 2 >>1 0 3 #L[0]~L[3]の最小値 2 >>1 0 7 #L[0]~L[7]の最小値 1 >> 1 4 3 #範囲が前後する inf
・BIT
任意の区間の和を求めることができる嬉しい配列。
n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 BIT = [0]*(n+1) #1-indexed def sum_1_to_i(i): #L[1]~L[i]の和を求める ans = 0 while i > 0: ans += BIT[i] i -= i & -i #ビットが立っている最下位の桁を0に return ans def update(i, x): #L[i]にxを加算する while i <= n: BIT[i] += x i += i & -i return for i in range(n): update(i+1, L[i]) print(BIT) while True: i,p,q = map(int,input().split()) if i == 1: print(sum_1_to_i(q)-sum_1_to_i(p)) else: break
実行例
6 1 2 3 4 5 6 [0, 1, 3, 3, 10, 5, 11] >>1 3 6 #4+5+6 15 >>1 2 6 #3+4+5+6 18 >>1 0 3 #1+2+3 6 >>1 0 6 21
・1~nを適当に並べた配列における反転数（バブルソートの回数）を求めるコード
※反転数＝バブルソートの回数なのは、①一回の入れ替えで反転数は-1、②昇順に並んでる時の反転数は0、の二つから従う。
n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 BIT = [0]*(n+1) #1-indexed def sum_1_to_i(i): #L[1]~L[i]の和を求める ans = 0 while i > 0: ans += BIT[i] i -= i & -i #ビットが立っている最下位の桁を0に return ans def update(i, x): #L[i]にxを加算する while i <= n: BIT[i] += x i += i & -i return times_of_swap = 0 for i in range(n): times_of_swap += i-sum_1_to_i(L[i]) update(L[i], 1) print(times_of_swap)
参考：
転倒数 - 個人的な競プロメモ
復習 3/30
逆元使ってn_C_k（を10**9+7で割った余り）を高速で求める、それはそうみたいな問題なんだけど、流石にテンプレをペタって貼り付けてn=10**5,kを1~10**5まで計算するのはしんどい（factorialの都合上）
n_C_k-1からn_C_nまでを一気に求める問題であれば、以下のような実装でまあなんとかなる。（色々杜撰なのは多めにみてね）
n = 10, k = 3なら、2C0, 3C1,...,9C7まで求めることになる
import math mod = 10**9+7 n,k = map(int,input().split()) #n_C_kのn,k a = math.factorial(k-1)%mod b = math.factorial(k-1)%mod c = 1 fact = [0]*(n-k+1) <s>#fact[j]は、n_C_(j+k-1)を表す</s> for i in range(k-1, n): if i == k-1: fact[0] = (a*pow(b*c, mod-2, mod))%mod else: a = a*i%mod #前の結果を再利用 c = c*(i-k+1)%mod #前の結果を再利用 fact[i-k+1] = (a*pow(b*c, mod-2, mod))%mod
i番目の鍵を使うか？でDPを行う。また、dp[i][j]について、iは「i番目までの鍵を見た（使った、使わないは無視）」、jは0から2**n-1までの値を取り、「二進数に直した時にビットが立っているところは、宝箱が空いている」とみなす。
例えば宝箱が3つあり、dp[3][6]であれば、「3番目の鍵まで見て、6→110、つまり箱1,2が空いている状態において、最小のコスト」が入るようにする。
dp[i][j]の遷移についてだが、まずi番目の鍵を使わないのであれば、開く箱はi-1番目の鍵を見た時と変化がないので、dp[i][j] = dp[i-1][j]となる。
i番目の鍵を使うのであれば、
dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0]) #j|key[i][1]はor演算子を使っている。dp[i][j]までで開いている箱に、新たに鍵iを使った時に開く箱の状態に遷移した時、その鍵を使った方が最適かどうかを判断している。
という式で遷移が書ける。
最後にdp[m-1][2**n-1]を出力してあげればいい。（全部開けられないかの判断もここでする）
計算量は、鍵1~mを開けるか否かについてと、それについての0~2**n-1通りの箱の開き方があるのでO(m*(2**n))。
これ1000人も通してたってマ？
いもす法で前から見ていくのだが、区間全部の累積和を取るのではなく、「爆発の及ぶ範囲」の端と橋をプラス、マイナスしておいて、今見ているところの累積和s[i]がモンスターの体力h[i]以上であれば爆発せずに次へ、小さかったら足りない分だけ爆発させて右端（爆発の及ばないところ）にマイナスし、s[i+1]にs[i]で与えた分だけ増やす、という方式を繰り返す。
例で言えば、例えば爆発の及ぶ距離が左右に2、爆発のダメージを2として、
[1,2,5,9,11]
という位置にいるモンスターが
[10,12,8,14,9]
という体力を持っていたとしよう。
s = [0,0,0,0,0,0]（一つ多く取っておく。s[i]にi番目のモンスターに与える累積ダメージが後々入ることになる）
まず、最初に1にいるモンスターを左端と見て、ここを爆発させると位置2,5のモンスターも巻き添えを食らう。位置1にいるモンスターを倒すには10のダメージ（爆発5回）が必要で、これを表した状態は、
s = [10,0,0,-10,0,0]
となる。
次に進む前にs[1] += s[0] をするので、
s = [10,10,0,-10,0,0]
となる。
次に、距離2にいるモンスターに着目すると、現在与えられているダメージはs[1]=10で、倒しきるのにあとダメージが2（爆発が1）必要である。
ここを左端にして爆発させると、巻き添えを食らうモンスターは位置5のみ。（位置5はもう倒してるけどそれは放っておく）
というわけで、一回爆発させた状態を表現した配列sは、
s = [10,12,0,-12,0,0]
となる。
次に進む前にs[2] += s[1] をするので、
s = [10,12,12,-12,0,0]
となる。
次は距離5にいるモンスターだが、s[2] > h[2] = 8なのでもう爆発させる必要がない。
というわけで次に進むので、s[3] += s[2]をして
s = [10,12,12,0,0,0]
となる。（ここで、s[3]の累積ダメージが0になっていることに着目したい。s[3]を見るまでs[3]に入っていた値は累積ダメージを表現していなかったが、前から累積和をとることによって、s[3]を見る時にはうまく帳尻があう（正確なダメージが入る）事になる）
次に距離9にいるモンスターに注目する。現状、累積ダメージは0なので、7回の爆発（ダメージ14）が必要である。この爆発で、距離11にいるモンスターも巻き添えを食らうので、配列sは
s = [10,12,12,14,0,-14]
となる（配列の要素を一つ余分に取っておいたのがここでうまく作用する）
次に進むので、s[4] += s[3]をして、
s = [10,12,12,14,14,-14]
となる。
最後にs[4]だが、s[4] > h[4] = 9なのでもう爆発の必要はない。よってs[5] += s[4]をして、
s = [10,12,12,14,14,0]
となり、これで全部倒し切って終わり。O(N)で十分間に合う（ぶっちゃけ計算量的には前処理のソートの方が支配的）
復習 3/26, 3/27
桁DP的な発想 解説読んでパッと理解できなかった
これも桁DP的発想
提出した後で「2,8とかの組み合わせの時無理じゃね？」とか気付く。ちゃんと考察をしましょう。
グラフの用語を知った。
・直径：一番遠い点間の距離
・二部グラフ：二つのグループに分けられるグラフ。グループAはグループBの頂点としか繋がっておらず、逆も然り。例えば三角形に頂点が並んでいるグラフは二部グラフではないが、四角形に並んでいたら二部グラフ。二部グラフの時、隣接する頂点のグループ番号を偶数、奇数、偶数、奇数……と交互にできる。
とにかく桁数がデカけりゃデカいほど強いので、それを目標にしてまずはDPで「マッチ棒ビッタリ使った時に最大何桁作れるか？」を求める。そしてそれが求まったら、dpの最後から遡ってどういう数字を各桁に割り当てればいいかを求める。賢い。
結局は高校数学。1<=i<=kのそれぞれのiに対して、(n-k+1_C_i)*(k-1_C_i-1)を求めてあげればいいだけの話。考え方は「最初に赤いボールn-k個を並べて、①その間のi個のどこにボールを入れるか、②その場所に何個のボールを入れるか、の二つをかけたもの」
逆元の求めかたを、例外処理（例えば4C6なんてのは存在しない）も入れて書き直した。
import math mod = 10**9+7 def comb(p,q): if p >= q: a = math.factorial(p)%mod b = math.factorial(q)%mod c = math.factorial(p-q)%mod return ((a*pow(b*c, mod-2, mod))%mod) else: return 0
どうでもいいけどn=10**3くらいだったらpythonの方が早そう
二分探索と、「二つの配列の各要素を掛け合わせた時の最大値をできるだけ小さくするにはどう掛けあわせるのが最適？」っていう問題をちゃんと考える。
二分探索で値を見つけるコードを覚えとこう。
n,k = map(int,input().split()) A = list(map(int,input().split())) F = list(map(int,input().split())) A.sort() F.sort() F.reverse() t = sum(A) ok = 10**12 ng = -1 if t <= k: print(0) else: while abs(ok-ng) > 1: cur = 0 mid = (ok+ng)//2 for i in range(n): temp = mid/F[i] if int(temp) == temp: cur += max(0, int(A[i]-temp)) else: if A[i]-temp > 0: cur += int(A[i]-temp)+1 if cur > k: ng = mid else: ok = mid print(ok)
（こちらのサイトを参考にさせていただきました。ありがとうございました。）
復習 3/21
総和が不変であり、その約数がgcdの候補であることは気づけた。そしてその後に分配するフェーズで余りを横に並べて右側はプラスされる側、左側はマイナスされる側と分けてそれぞれをチェックするところまでは発想できた。
（例）
約数＝5で割った余りが1 1 1 1 2 2 3 4
1 1 1 1 2 2 3 / 4 →4はあと1プラスすればmod5=0、左側は全部4に移すので手数が11かかる
1 1 1 1 2 2 / 3 4 →3,4はそれぞれ2,1プラス（合計3）すればmod5 = 0、左は全部移して手数8、よって合計で手数8
1 1 1 1 2 / 2 3 4 →2,3,4 はそれぞれ3,2,1プラス（合計6)すればmod5 = 0、左は全部2,3,4に移して手数6、よって合計で6
1 1 1 1 / 2 2 3 4 →2,2,3,4は手数9、左を移すのは手数4、実際は左を全部2,4に移してmod5=0にして、あとは2を3に移せばいいので手数は6（だが便宜上9にしておく）
みたいなのを最後までやっていき、手数最小になるものがk以下になるものの中で最も大きい約数を出力
答え見てACしちゃったけど割と嘘書いてそうで心配
復習 3/19,3/20
数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。
発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば
10**100-10 #9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990 10**100-9 #9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991 (10**100-9)//2 #4999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995(これは誤り)
みたいになる。math.floor()とかもそうだけど、大きな数字は割り算（切り上げ切り捨て）の操作に弱いので要注意。
0点の人間を除いて、ソートして溢れなかったらK番目にいる人の点数+1、溢れたら0だってさ なんじゃこりゃ
復習 3/16,3/17
s = 10**100とかいう良く分からん表現に振り回された感がすごい
やることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える（これをやるときは、sを二つ繋げた文字で考えると良い）。これを前処理として表にしておく。
そして、tの前から見ていって、今見ている文字から次の文字まで何文字あるかな？ってのを、さっき作った表を参考にして調べていく。
言われればははぁんってなるけど思いつかへん......
作れない数列の条件（最初が0でない、増加するときに+1でない）はわかったんだけど、数が数えられなかった。
単調増加なら+1、そうでないなら+(要素の値)になる。新規で作るのに要素の値だけの手数が必要になるので、ってことだけどこれ気づかね〜〜〜〜
それっぽいことを考えたけど実装できませんでした。答えは案外シンプルなことが多い。
自力ACできたけど、結構ちゃんと条件を押さえないといけなくて教育的だなって思ったので復習
数字iを二進数に直すには、自身より小さい2の累乗の数と&（ビット演算）を取るのが早い(e.g. 24と27は二進数に直すと11000と11011なので、11000&11011は両方のbitが立っている桁のみ1になることから24&27=11000&11011=11000=24となる)
あとNが小さいのでO(2**N)が使える
あとは証言を全部舐めてって矛盾が生じた時点でアウトの処理をすればいいけど、矛盾が出るのは、
①証言者が正直（bitが立っている）かつ、言及先が本当は正直者(bitが立っている）なのに「不親切」と言及している
②証言者が正直（bitが立っている）かつ、言及先が本当は不親切(bitが0）なのに「正直者」と言及している
の2パターンしか存在しないので、この二つを確認すれば良い。