区間dp の問題。区間dp とは、dp[ i ][ i+j ] = list[ i : i+j ] での最大(最小)値として、最大値の遷移を考えるもの。 今回は、dp[ i ][ j ] = ケーキが i+1 番から i+j+1 番まで残っているときの JOI 君の取り分の最大値 として問題を解く。 ケーキが円状…

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

素数についての謎の知識を二つ得た 1. p が素数のとき、x^n % p = x^(n%(p-1)) % p 2. p-1 > c > 1 のとき、x^n+y^n≡c (mod p) を満たす個数は０または x^n+y^n≡1 (mod p) を満たす個数に等しい。 証明はここをみてください。 フェルマー方程式/Fermat(JOI20…

atcoder.jp与えられた’１’のマスを移動できる最大値を求める問題。 普通の bfs だと例えば 1 1 0 1 1 0 1 0 0 が与えられたときに a[1][1]をスタートとしても 3 2 0 2 1 0 3 0 0 のような移動距離を返してくる（本当は a[2][0] = 5となってほしい） そこで通…