bit 全探索
bit全探索、横の列を固定して、縦ごとに見る、defaultdict の操作、などのメモ import sys input = sys.stdin.readline from collections import deque, defaultdict h,w = map(int,input().split()) s = [list(map(int,input().split())) for i in range(h)…
172 4完 パフォ1421 173 4完 パフォ1319 まあ失敗ではないけど大成功でもない感じ。次で水色なりたいね。 172は包除原理の一般法則を知らなかったのが原因。Fは難しかった。 #172 E import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.re…
bit dp の問題。ゴールした順に bit を作っていくとうまく dp が作れる。 例えば 1 よりも 2 が早くゴールしているときは、今ゴール済みの人を s で表すと、 s & 1 == 0であれば、まだ1がゴールしていないので s から s | 1 n,m = map(int,input().split())…
bit dp の問題。dp[ i ][ k ] = (a,b) として、今まで通った頂点を表す bit i と今いる頂点 k が入りその時の最小値 a と最小値をとりうる通り方の総数 b が保管されている。 k から次の頂点 j に行けるのは i の j の位が0であるときで、 かつ、dp[ i ][ k…
100分フルに消費して4完。レート微増。参加者のレベルも上がっている気がする?自分の成長速度があまり感じられない。二連続ぐらいで水パフォ取れると安定しそうだけどなぁ cは2回続けて全探索に殺されてたので流石にできた。c は numpy で行ごとに足せれる…
R XOR操作が出てくるので i を2進数表示したときの n 桁目を (i>>n)&1 であらわす。 全探索は行ごとでするのに、総和は列ごとに数えるのが面倒くさい。 numpy を使って転置するか、A.sum(axis=0) で列ごとに和を取っていくとよい。 np.count_nonzero(A,axis…
i = 1 ~ 2**10-1 まで bit 全探索する問題。 与えられた F を 2 進数としてみると、i & F =1となっている桁の個数でどの P になるかが決まる。 '10' をそのまま 2 進数として扱いたいときは int( '10', 2 ) としてやる。 ( print すると 10 進数表記の 2 …