一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

頂点１を根として、dfs をしていき、それまでの xor 和を defaultdict (D) で管理して、現在のxor和 = X^a を満たす a が今までの xor和に含まれていればいいので、dfs 順に D [ 現在のxor和^X ] を足していけばいい。根からの xor和がちょうど X になるとき…

解法１ dp[ i ][ j ][ k ] : i 行 j 列まで見たときに差が k になれるかどうか、なれるなら１、なれないのなら０を記録する。遷移は c = abs(a[ i ][ j ] - b[ i ][ j ]) として (dp[i+1][ j ][k+c] = 1, dp[i+1][ j ][abs(k-c)] = 1 if dp[ i ][ j ][ k ] =…

4完 パフォ1412 でした。最近パフォが1400 くらいで安定している。今はいいけど水色になってからは困るなあ。 コンテスト後に F を通しました。考察はあと一歩だったけど、実装の場合分けは無理でした。まず、Nim の必勝法は A1^A2^...^An = 0 なら 後手が必…

python だと難易度が爆上がりするやつ。 E - Exclusive OR QueriesCPSCOのsession1のEをPythonで通そうと頑張ってみたけどダメそうということがわかった(はい)(ごめんなさい)— てんぷら (@tempura_cpp) May 12, 2019 本編まで飛ばしていいよ。 やるべき動作…

自力AC。解説は dp しとるな。これが bitDP ってやつか？ 制約が N=12 だったので bit 演算関係あるんかなと考えると、とりあえず入力される鍵を 例えば N=6 で 2 3 5 を開ける鍵だとすると、key1 = 2**(2-1)+2**(3-1)+2**(5-1) とかはできるなあと思った。 …

XOR の知識 1．a^a = 0, a^b^a = a^a^b = b（交換法則） 2．n%4 = 1 のとき 1^2^...^n = 1, n%4 = 3 のとき 1^2^...^n = 0 (ABC121 D)2. から 1^2^...^2**m-1 = 0 となり、1. から k 1^2^,...,^k-1^k+1^,...,^2**m-1 = k となる。 考察はできたが実装が手こ…

R XOR操作が出てくるので i を２進数表示したときの n 桁目を (i>>n)&1 であらわす。 全探索は行ごとでするのに、総和は列ごとに数えるのが面倒くさい。 numpy を使って転置するか、A.sum(axis=0) で列ごとに和を取っていくとよい。 np.count_nonzero(A,axis…

尺取り法：数列の連続した部分列にあてはまる条件を O(n) で求めてくれる優れもの。 XOR四天王の二人目を倒しました。(弱さも多分2番目) 個人的な尺取り法の実装については、条件を満たさなくなった瞬間に（部分列の長さ - 1）を使って求めたいものを求めて…

Code Jam - Google’s Coding CompetitionsAしか解けず５点差で通過できず。C何とかして部分点取りたかった。インタラクティブはまだ入力の仕方がわからないので諦め。 Aは４方向に i 回目に 2**(i-1) 移動でき、(x,y) = (0,0) から、最終的に目的の座標に到…

maspy さんの解説をひたすら読んだ [AtCoder 参加感想] 2019/12/08:ABC 147 | maspyのHP XOR関連の共通した着目点は、各桁ごとのbit 演算は独立して計算できるということ i を2進数表示したときの n 桁目は ( i >> n ) & 1 で表せる ある桁のXORのｎ個の総和…

a から b までのXORの累乗和を計算する問題 1から１５までのXORの累乗和を順に求めていくと、 １、１１、０、１００、１、１１１、０、１０００、１、１０１１、０、 １１００、１、１１１１、０ となっていき、3 (mod4)のときに０になることがわかる また、…