BIT

CODE FESTIVAL 2017 Final,E: Combination Lock

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_eまず区間の真ん中をまたぐ部分は考えなくていいです。 すると区間は左or右に寄った形になりますが、右にある区間を左に移しても問題ありません。 よって左半分に操作を行って右半分の文字列に…

COLOCON -Colopl programming contest 2018- Final

https://colopl2018-final-open.contest.atcoder.jp/A オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。B スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。C 一次式にしてもよくわからなかったので分割統治でやった。これ解け…

POJ 1854: Evil Straw Warts Live

BIT

http://poj.org/problem?id=1854蟻本には分割統治法と書いてあるがBITでやってしまった。同じ文字だったら一番右にあるのと一番左にあるのを回文のペアにするのが良くて、二番目三番目…についても同様である。 違う文字だったら、対称性よりどっちを先に端に…

POJいろいろ8/3

3109 http://poj.org/problem?id=3109座標圧縮+平面走査segtree。実装ややこしいはずだけど一発で通って気持ちがいい。実装ちゃんと練ればすんなりいくんだね。3735 http://poj.org/problem?id=37351+B+B^2...の形が出てくるので行列の累乗和を貼って終了、…

Codeforces Round #423C: DNA Evolution

http://codeforces.com/contest/827/problem/Ce int n; ll sum(ll *bit, int i) { ll s = 0; while(i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(ll *bit, int i, ll x) { while(i <= n) { bit[i] += x; i += i & -i; } } struct query { int…

AtCoder Regular Contest 075 E: Meaningful Mean

http://arc075.contest.atcoder.jp/tasks/arc075_c条件を数式に落とし込むと ∑(i=0→r)Ai - rK という値について考えればいいことがわかる。数式を使うと独立性に気付ける問題だった。 あとは適当に座圧してBITで数え上げればよい。 int n; //BIT 1-origin ll…