問題 https://beta.atcoder.jp/contests/arc092/tasks/arc092_b [0<= i <= n-1], [0<= j <= n-1] の i, j について a_i + b_j のそれぞれの xor をとった結果を求めよ。 方針 「桁ごとに独立して考えること」がポイントである。xor演算は繰り上がりがないの…

問題 https://beta.atcoder.jp/contests/abc027/tasks/abc027_d 数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。 このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から末尾まで順に実行される。 M…

概要 特定の区間上の複数回の操作における計算量を落とすテクニックについて考えます。累積和に近い考え方です。 問題設定 という9つの要素を含む数列 がある。数列の添字は から始まるものとする。 ここでは の次の要素は に戻るような循環する数列を考える…

bit演算を使って部分集合を実装 競技プログラミングをやっていると、集合 のべき集合を求めよ～ とか、数列 の部分列の総和を求めよ～とかでできます。 bit演算で簡単に実装できることを学びました。 具体例として、集合 として、 が与えられたとします。 集…

最小全域木の探索について アルゴリズム ナイーブな実装だと計算量が 程度。ノード数が多いグラフでは計算量をいかに落とすかがポイントっぽい。 プリム法 グラフ の頂点全体の集合を 最小全域木(MST)に属する頂点の集合を とする。 から任意の頂点 を選び、…