Codeforces

Codeforces Round #407 (Div. 2) D. Weird journey

問題文 http://codeforces.com/contest/789/problem/D 解法 まず,同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます. 自己辺を考えるのはめんどうなので,とりあえずない場合を考えると,条件を満たすパスがあるかどうかは,「一度のDFSによ…

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 個からなる文字列の前半(ないし後半)に対応する頂点をもつグラフをつくる. それぞれのアルファベットから,文字列…

Codeforces Round #185 (Div. 1) B. Cats Transport

問題文 http://codeforces.com/problemset/problem/311/B 問題概要 N個の地点があり,順に 0 から N-1 とする.地点 i と i + 1 の間の距離は d[i] である. また,猫が m 匹いて,猫 j は時刻 t[j] に地点 h[j] にあらわれるものとする.それぞれの猫は,餌…

Codeforces Round #230 (Div.1) B. Tower of Hanoi

問題文 http://codeforces.com/contest/392/problem/B 問題概要 ハノイの塔のパズルの最小手数は 2^n - 1 であることは有名な事実であるが,今回は以下の問題を考えるとする. ある段を位置 i から位置 j に移すのにコストが t[i][j] かかるとするとき( 1 ・…

Codeforces Round #433 (Div. 2) D. Jury Meeting

問題文 http://codeforces.com/contest/853/problem/B 問題概要 街が n + 1 あり,それぞれナンバリングされている.また人が n 人いて,人 i は街 i に存在する.0番目の街は首都であり,人はいない. ここで,飛行機のスケジュールが m 個与えられる.スケ…

Codeforces Round #238 (Div. 1) D. Hill Climbing

問題文 http://codeforces.com/problemset/problem/406/D 問題概要 山が一直線上に n 山ならんでいる.それぞれの山の座標は x[i],高さは y[i] である. 山と山にはスロープがかかっている.スロープは以下のようにかかっている. 各山 a は,a の頂上から…

Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess

問題文 http://codeforces.com/contest/559/problem/C 問題概要 H * W のグリッドがある. このグリッドのうち,ある N マスは使えないようになっている. この時,左上から右下まで行く方法は何通りあるか.ただし,マスを移動するときは,右または下にしか…

Codeforces Round #429 (Div. 2) E. On the Bench

問題文 http://codeforces.com/contest/841/problem/E 問題概要 数列 {a_n} が与えられる. 任意の 1 並び替えた結果が同じものでも,並び替え方が違えば別として数えるものとする.・制約 1 1 解法 まず,掛け合わせることで平方数になってしまうという関係…

Codeforces Round #296 (Div.1) D. Fuzzy Search

問題文 http://codeforces.com/contest/528/problem/D 問題概要 文字列 S と T が与えられる.それぞれの文字数を n, m とする. また,数 k が与えられるとする. このとき,以下の条件をみたすような位置 p の数を求めよ.すべての i (0 ・制約 1 0 文字列…

Codeforces Round #292 (Div. 1) D. Drazil and Morning Exercise

問題文 http://codeforces.com/contest/516/problem/D 問題概要 木 T が与えられる.また,クエリが q 回投げられる.それぞれのクエリは L を投げてくる. 木 T の頂点 i に対して,i からそこから最も遠い葉までの距離を D(i) とする. 各クエリに対し,T …

Codeforces Round #356 (Div. 1) B. Bear and Tower of Cubes

問題文 http://codeforces.com/contest/679/problem/B 問題概要 整数 m があたえられる.m 以下の整数 X で,以下を満たす (n, X) を求める. X を超えない最大の a^3 (立方数)を選び,X = X - a^3 と更新する. X に対して上記の操作を繰り返す. 上記の…

Codeforces Round #363 (Div. 1) C. LRU

問題文 http://codeforces.com/contest/698/problem/C 解法 10^100なので実質無限大の時間がたったと考えて良い. 正規マルコフだし,十分大きな時間が経過したあとは定常状態に落ち着く. この時,過渡状態にいる確率はほぼ0で,キャッシュは(できるかぎり…

Codeforces Round #326 (Div.1) E. Duff as a Queen

問題文 http://codeforces.com/contest/587/problem/E 問題概要 n 個の数からなる数列 {a_n} が与えられる. また,q 個のクエリが投げられるものとする.クエリは以下の2種類. ただし,以降は + を XOR, * を AND とする. 1. l 2. a_l, ..., a_r からいく…

Codeforces Round #361 (Div. 2) D. Friends and Subsequences

問題文 http://codeforces.com/contest/689/problem/D 問題概要 長さ N の数列 A, B が与えられる. max{A(l), ..., A(r)} = min{B(l), ... B(r)} となる (l, r) (l ・制約 1 解法 Sparse table を書いてみたのでそのテストに使った.なので Sparse table で…

Codeforces Round #406 (div.2) C

問題 http://codeforces.com/contest/787/problem/C 問題概要 円上に n 個のマスがある.それぞれ 0 から n-1 まで番号が振られている. 0 番目はブラックホールである. また,どこかのマスに一匹のモンスターがいる. これらを使って2人でゲームをする.2…