2017-10-29から1日間の記事一覧

Codeforces Round #404 (Div.2) E. Anton and Permutation

問題文 http://codeforces.com/contest/785/problem/E 解法 平方分割 + 2次元BITで解いた.[0...m] x [0...n] で二次元.m は n / sqrt(n). l[i] から r[i] の間に完全に含まれているブロックは BIT 上で計算し,端っこの部分は生で持っている配列を使って…

Codeforces Round #404 (Div.2) D. Anton and School - 2

問題文 http://codeforces.com/contest/785/problem/D 解法 条件に合う部分列の,一番右端の "(" の位置を総当りして計算します. その位置から左に(その位置自体も含めて)"(" が $x$ 個あり,右に ")" が $y$ 個ある時,求める答えは $\displaystyle \sum…

Codeforces ECR #31 F. Anti-Palindromize

問題文 http://codeforces.com/contest/884/problem/F 解法 最小費用流で解ける. まず,各アルファベットに対応する26個の頂点と,N / 2 個からなる文字列の前半(ないし後半)に対応する頂点をもつグラフをつくる. それぞれのアルファベットから,文字列…