Codeforces

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…