atcoder.jp 数列 が与えられるので、 のすべてのxorを求めよという問題。解法は愚直にやればよいので、 程度の解法を求める必要がある。 xorの値を求める問題はbitごとに独立して行うというのが鉄則。そこで下位bitから求めていこう。最下位ビットはの偶奇で…

atcoder.jp が与えられるので、 を求めるというシンプルな問題。はいずれもからを動くとしてよい。(tex: i = j]のときは簡単に計算できるので、後から引けばよい) 一般に、 という形式の値を求める場合、 が間に合わないなら、 の形にしたいなと思うのが定石…

atcoder.jp 1,2,3->0,1,2と読み替えて良い。(N>=2、かつ2段目以降は+1分が相殺されるため) こういう問題はまずは偶奇を見る。 するとパスカルの三角形的に考えて、Σ n-1Ck a[k] の偶奇であることがわかる。これが奇数なら答えは1であることが確定する。 次に…

yukicoder.me ちょっと複雑な累積和。次のような状況を想定する。 [左の荷物群の初期位置] 運びたい位置X [右の荷物の初期位置] 累積和を取ることで、「左の荷物群をその荷物群の中での右端まで異動するためのコスト」のテーブルが構成できる。 あとは「左の…

yukicoder.me ダブリングの練習。 まず「次の場所 % n」の値をダブリングテーブルを前処理しておく。 for (int i = 1; i < m; i ++) { for (int j = 0; j < n ; J++) { table[i][j] = table[i-1][table[i-1][j]] } } ダブリングテーブル自体はこんな感じで更…