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

atcoder.jp

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日目となる。

atcoder.jp

累積GCDまでは思いついたが......という感じ。前から累積GCD取って、各クエリごとに「初めてGCDが1になるところはどこか？」を二分探索すればO(QlogN)で求まる。GCDが1にならないなら配列の最後とのGCDを求めてあげればいい。

atcoder.jp

部分列の和を求めるのはわかる。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を選んでくる」のようなことができていることになる。

めっちゃ賢い......

atcoder.jp

「ペア」なので、必ず二つの要素の組で考える。
大きい方から貪欲に、「ペア」を作れる相手を取ることを考える。（降順で固定する）

大小関係をつけることでわかることがある。例えば、今見ている要素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

atcoder.jp

必勝法ゲー。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となる。

atcoder.jp

BITを真面目に使った初めての問題。文字を入れ替えたら、BITの情報だけでなく元の文字列の情報も更新するのをお忘れなく

onlinejudge.u-aizu.ac.jp

巡回セールスマン問題。これ始点を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

atcoder.jp

まずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決して上がらない。
何故ならば種類は多いほど満足度が上がるし、そもそも最初にK個選んだ時点で美味しい順に取っているので、i未満の種類を選ぶことによって純粋な「美味しさの和」を上昇させることが不可能なためである。

したがって、ここから
１、種類を減らさずに（★逆に言えば、現時点で食べようと思っている寿司の中にないネタを選んで）
２、交換することで満足度が上昇するか
についてを、残りのN-K個の寿司について考える。（N-K個も美味しい順にソートしておく）

交換するのは、現時点で食べようと思っている寿司のうち、同じ種類のものが二つ以上あるものに限る。なぜなら、今確保している寿司よりも、残りのN-K個の寿司の方が美味しさが小さいため、純粋な一種類・一個の寿司のトレードで満足度を向上させられない（種類ボーナスは増えないし、美味しさが減るだけ）からである。

これを、現状2個以上残っている寿司の美味しさをheapqで持っておき、新たな寿司のネタと交換することで、美味しさを増やせるかどうかを見るだけ。種類が多くなればなるほど満足度が増える訳ではないことに注意。

atcoder.jp

閉路検出。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)

atcoder.jp

完全グラフから、nがoddなら[1,n-1]...を、nがevenなら[1,n],[2,n-1]...を除けばいい

は？？？？？

atcoder.jp

縦方向と横方向を一緒くたに考えようとすると混乱するので分解する。

とにかく「ゲーム終了時に盤面上に残っているには、最初にどこに駒があればいいのか？」を考えるため、操作を逆順に遡っていく。

先攻は「範囲を狭めようとする」動きをするのであんまり考えなくていいが、後手が結構ややこしい。
例えば、縦方向に見ていて先手を見終わって範囲が[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

atcoder.jp

逆元使って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

atcoder.jp

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))。

atcoder.jp

これ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

atcoder.jp

桁DP的な発想　解説読んでパッと理解できなかった

atcoder.jp

これも桁DP的発想

atcoder.jp

提出した後で「2,8とかの組み合わせの時無理じゃね？」とか気付く。ちゃんと考察をしましょう。

atcoder.jp

グラフの用語を知った。
・直径：一番遠い点間の距離
・二部グラフ：二つのグループに分けられるグラフ。グループAはグループBの頂点としか繋がっておらず、逆も然り。例えば三角形に頂点が並んでいるグラフは二部グラフではないが、四角形に並んでいたら二部グラフ。二部グラフの時、隣接する頂点のグループ番号を偶数、奇数、偶数、奇数……と交互にできる。

atcoder.jp

とにかく桁数がデカけりゃデカいほど強いので、それを目標にしてまずはDPで「マッチ棒ビッタリ使った時に最大何桁作れるか？」を求める。そしてそれが求まったら、dpの最後から遡ってどういう数字を各桁に割り当てればいいかを求める。賢い。

atcoder.jp

結局は高校数学。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の方が早そう

atcoder.jp

二分探索と、「二つの配列の各要素を掛け合わせた時の最大値をできるだけ小さくするにはどう掛けあわせるのが最適？」っていう問題をちゃんと考える。
二分探索で値を見つけるコードを覚えとこう。

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)

scrapbox.io

（こちらのサイトを参考にさせていただきました。ありがとうございました。）

復習 3/21

atcoder.jp

総和が不変であり、その約数が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

atcoder.jp

数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。

atcoder.jp

発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば

10**100-10
#9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990

10**100-9
#9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991

(10**100-9)//2
#4999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995(これは誤り)

みたいになる。math.floor()とかもそうだけど、大きな数字は割り算（切り上げ切り捨て）の操作に弱いので要注意。

atcoder.jp

0点の人間を除いて、ソートして溢れなかったらK番目にいる人の点数+1、溢れたら0だってさ　なんじゃこりゃ

復習 3/16,3/17

atcoder.jp

s = 10**100とかいう良く分からん表現に振り回された感がすごい

やることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える（これをやるときは、sを二つ繋げた文字で考えると良い）。これを前処理として表にしておく。

そして、tの前から見ていって、今見ている文字から次の文字まで何文字あるかな？ってのを、さっき作った表を参考にして調べていく。

言われればははぁんってなるけど思いつかへん......

atcoder.jp

作れない数列の条件（最初が0でない、増加するときに+1でない）はわかったんだけど、数が数えられなかった。

単調増加なら+1、そうでないなら+(要素の値)になる。新規で作るのに要素の値だけの手数が必要になるので、ってことだけどこれ気づかね〜〜〜〜
それっぽいことを考えたけど実装できませんでした。答えは案外シンプルなことが多い。

atcoder.jp

自力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パターンしか存在しないので、この二つを確認すれば良い。

復習 3/15

クッソサボってた　しょうがないね

atcoder.jp

s = 'AAA'
s = 'B' + s  #s = 'BAAA'

上の例みたいに、文字列の先頭に新たな文字をくっつけるのは、末尾にくっつけるよりもかなり時間がかかるので注意すべし

atcoder.jp

サイズ付きUF木で一撃　こういうのが普通にできるようにしたい

atcoder.jp

こういう辞書順最小みたいなのは、前回作った奴を再利用するタイプが使える

atcoder.jp

1文字と2文字を扱おうとするからごちゃごちゃになる　2文字を1文字として扱うべし

桁DP

桁DPは、例えば「0以上N以下の数字で、ある条件を満たす数字がいくつあるか」などを数えるのに便利な手法である。

発想が単純なものと、複雑なものの2パターンある。

＜単純な方＞
例えばこの問題↓
atcoder.jp

?はワイルドカード（0~9のいずれでもいい）の時、?5?という形をしている3桁の数字で、13で割って5余るような数字はいくつ存在するかを数える。

上から順に数字を見ていく。まず、「n桁目を見たところまでで、13で割って5余る数字は何通りか？」を管理するために、「n桁目を見たところまでに13で割ってi余る数字」をdp[i]とする配列dpを考える。

例えば?5?であれば、一番左（最初）の桁が?なので、dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]となる。（?には0~9が入るため、ここまでを13で割った結果がdpになる）
次に、真ん中の桁が5になるので、?5を13で割った余りは、dp = [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]となる。(例えば、dp[2]について、25を13で割った余りは12になるので、もともとdp[2]にあった1はdp[12]に移る）
最後に、一番右の桁が?なので、dp = [8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 7, 8]となる。dp[5]は、すべての0~12のiについて、(10*i+j) % 13 == 5となるようなj（つまりワイルドカードの?）を試し、その場合の数を加算してあげればいい。

その他の例
atcoder.jp

＜複雑な方＞

例えば「N以下で4の入った数字はいくつありますか？」という問いかけで、N=50であれば、十の位を1~9まで全部見ても、十の位で弾けるから簡単だが、N=1234とかだった場合に、千の位が1だった時に、単純にdpを作ろうと思っても「1100」と「1200」で扱いが変わってきたりする。（前者は十の位がなんでもいいけど、後者だと十の位の動きに制限が出る）

そういうのを管理するために、単純なdpではなく、
dp[今見ている桁][Nよりも明らかに小さいか、同じか][すでに4が登場しているか]
という配列で管理するのが良い。これを用いて遷移を場合分けしていけばいいんだけど、かなり面倒。

atcoder.jp

abc007.contest.atcoder.jp

atcoder.jp

復習2/6,2/7

atcoder.jp
＜ずる＞
O((HW)**2)とは分かったものの一個だけTLEが取れない。全部道である場合のみ特例で除外したら通ったけどこれPythonの正攻法はなんなんやろね。

atcoder.jp
＜解説AC＞
ロボットアームの動ける範囲の右端でソート→右端が小さい方から順番に、次のアームの左端が範囲に引っかかってたら入れない、大丈夫なら入れる、を繰り返す。右端を常に更新して管理しておくこと。

atcoder.jp
＜凡ミス＞
発想はあってたのに計算順序をミスったらWAが取れず1時間溶けた。たかが掛け算・割り算の順序と侮ってはいけない。次からはこういうことがないようにする。

atcoder.jp
＜解説AC＞
問題文の意味が理解できなかった。最初に与えられているのは「全点間の最小距離」である。
一回ワーシャルフロイドっぽいことをしてみて、与えられた全点間の距離のデータより小さくなってしまう（三角不等式において、a+b < cとなってしまうような状況。ここでa,b,cは全て「最短距離」であるはずなので、a+bがc未満になってしまうと都合が悪い）ケースが出てきてしまったら、その時点で調査を打ち切る。
a+b == cとなるケースにおいては、迂回した場合と直接向かった場合の距離が等しい→直接向かうような辺は削除してもオッケー（というか削除するべきで、なぜなら迂回した方が回れる点が多いので）なので削除。
ここで気をつけるべきは、一回削除したら「迂回するケース」の探索を打ち切ること。なぜなら、探索を続けてもう一つでもa+b == cとなるケースが出てきてしまった場合、削除すると決めた辺をもう一度消す事になってしまうから。

■

http://pr.cei.uec.ac.jp/~terada/lectures/comporg/2018/08.pdf