Codeforces
問題 文字列sが与えられる。 文字列sのi文字目からj文字目を抜き出したものをs(i, j)とする。 s(i, j)のうち"bear"を連続する部分文字列として含むものはいくつあるか答えよ。 制約条件 sの長さ≦5000
問題 ハチミツ１バレルの値段が与えられる。i日目に売り買いするときはa[i]円。 i日目に友達にハチミツ１バレルを借りて、 その日に売り払ってa[i]円を得て、次の日にa[i+1]円払って買い戻して、 友達にハチミツと利子のc円を払う、ということを全体で一度だ…
問題 n枚のカードがあって、それぞれには1〜nの異なる整数どれかが書かれている。 何回でも次のような操作をすることができる。 残っているカードのうち連続するw枚のカードを選ぶ 数字が最小のカードを捨てる w点をもらう 操作を終えた後のカードの状態が与…
問題 有向グラフがinterestingであるとは、 多重辺が存在しない。 一つの頂点cがあり、cはほかのどの頂点へも辺があり、どの頂点からもcへの辺がある。 頂点cには一本だけ自己辺がある。 c以外の頂点は入次数、出次数ともに2である ことを言う。 多重辺の存…
問題 自然数の数列a[i]に対して次の操作を、要素が一つになるまで繰り返す。 好きなi, j（i != jかつa[i]≧a[j]）を選び、a[i]のうしろにa[j]を文字列としてくっつけて、新しくできた項をaに追加し、a[i], a[j]を削除する。 n桁の数字が与えられる。 このn桁…
問題 n問のコンテストを作る。i番目の問題の難易度はa[i]になるようにしたい。 持ってる問題はm問あって、i番目の難易度はb[i]. 問題の難易度はコスト0で小さくすることができるが、大きくすることはできない。 コンテストを開催するためには何問新たに問題…
問題 起床時刻sと睡眠時間tが与えられる。昨日の就寝時刻を求めよ。 時刻および時間はhh:mmの形で入力される。この形で出力せよ。 制約条件 hh:mmは0をつめる
問題 Innaは整数の配列a[i]を使って次のようなことをする。 a[i]を一列に全部書く。これをa1[i]とする。 次に、n - 1個の(a1[i] and a1[i + 1])を書く。（ただしandはビット演算のand） これをa2[i]とする。 次にn - 2個の(a2[i] and a2[i + 1])を書く…… を…
問題 n匹のバクテリアがいて、（匹？）、1〜nと番号がついている。 最初のc[1]匹が種類1,次のc[2]匹が種類2……で、全部でk種類である。 バクテリアu[i]からv[i]へまたはv[i]からu[i]へ、エネルギーを移すことがx[i]ドルで可能である。 このような関係がm個与…
問題 n行m列のグリッドにp個キャンディが置いてあって、i番目のキャンディはx[i]行y[i]列にある。 このグリッドをx回時計回りに90度、y回水平反転を、z回半時計回りに90度回転させる。 操作の後でそれぞれのキャンディは何行何列にあるか出力せよ。 制約条件…
問題 n行m列のグリッドがあって、それぞれ'*', 'G', 'S'のどれか。 '*'は何もないセルで、'G'はロボット、'S'は飴のあるセル。 一行には必ずちょうど一つずつだけ、GとSが含まれている。 号令をかけると、まだゴールしてない全てのロボットが一斉に動き出し…
問題 それぞれ'O'か'X'が描かれた12枚のカードがある。 i番目のカードにはs[i]が描かれている。 二数a, bを選び、このカードを次のように並べる。 最初のb枚を取って一列に、 次のb枚を取ってその下の列に一列に並べる…… こうして12枚のカードをa行b列に並べ…
問題 長さnの順列p[i]が与えられる。 p[i]よりも辞書順で前にある全ての順列について、転置の総数の和をmod 10^9 + 7で求めよ。 制約条件 n≦10^6とか
問題 n頂点からなる木が与えられる。頂点には数字が記憶されていて、最初は全て0. これにq個のクエリが来るので処理せよ。 1 v x k 頂点vにxを足す。 vの子孫全てにvからの距離がdならばx - k*dを足す。 0 v 頂点vの数字をmod 10^9 + 7で答える。 制約条件 n…
問題 u(n) = n以下の最大の素数 v(n) = nより大きな最小の素数 とするとき、与えられたnに対して Σ[i = 2 to n] 1 / u(i)v(i)を既約分数の形で求めよ。 制約条件 1テストにつき500個のnが与えられる。 n≦10^9
問題 n個の数aiが与えられる。 m = a1 * a2 * ... * anとする。 mをn個の数の積b1 * b2 * ... * bnとしてあらわす方法は何通りあるかmod 10^9 + 7で答えよ。 制約条件 n≦500 ai≦10^9
問題 集合Sがperfectであるとは、任意の（同一でもよい）a, b∈Sについて、 (a xor b)∈Sとなることを言うものとする。 全ての要素がk以下であるようなSの選び方は何通りあるか、 mod 10^9 + 7で求めよ。 制約条件 k≦10^9
問題 二人がゲームをする。 n個のカードの山があって、i番目の山にはsi枚のカードが積まれていて、上から順にci1, ci2, ..., cisiである。 先手は好きな山を選んで先頭からカードを一枚、後手は好きな山を選んで底からカードを一枚引くというのをカードがな…
問題 無向グラフで頂点1から2への最短パスの総数がちょうどk通りであるような頂点数1000以下のグラフを出力せよ。 答えが複数ある場合はどれを出力してもよい。 制約条件 解の存在は保証されている。
問題 n個の大きさ、重さが全て同じ箱があって、i番目の箱は自分の上に他の箱をxi個置ける。 一つの箱のすぐ上にはちょうど一つの箱しか置けないとき、 全ての箱をなるべく少ない数の山に分けて積み上げたい。 山の最小個数はいくつか。 制約条件 n≦100
問題 n個の点および凸なm角形が与えられる。 m角形の内部で、n個の点からの距離の二乗の和が最小になる場所における、 距離の二乗の和の最小値を求めよ。 制約条件 n≦10^5 m≦10^5 座標の絶対値は10^6以下
問題 n個の数が与えられる。自由に並べ替えてよい。 それぞれの数に対して何回でも+1または-1をすることができる。 1, -1し終えたあとで、数が非減少な等差級数になっているようにしたい。 必要な+1, -1の回数の合計の最小値はいくつか。 およびその最小値を…
問題 10, 11, 00のドミノが合計でn*m個与えられる。 これらを横向きにn*m個に並べる。 それぞれの列ごとにその列の数の和を求める。 この和の最大値が、最小になるようにしたい。最小値を求めよ。 ドミノは回転させることはできるが、縦に使うことはできない…
問題 p桁の数で、Leading zeroがなく、下一桁を一番上にもってくると元の数のx倍になるような数最小の数を求めよ。 そのような数がないときはImpossibleと答えよ。 制約条件 1≦p≦10^6 1≦x≦9
問題 |||+||=|||||のようなマッチ棒を使った式が文字列で与えられる。 A+B=C（A, B, C ＞ 0）のときに正しい式である。 誤っているかもしれない式が与えられるので、棒を一本動かして正しい式に出来るならその式を、そうでないならImpossibleを出力せよ。 +,…
問題 n項からなる数列A, B, Cが与えられる。 Aの先頭u項、Bの先頭v項、Cの先頭w項の和集合と、 A, B, Cの和集合が一致するような(u, v, w)について、u + v + wの最小値を求めよ。 制約条件 n≦10^5 各項≦10^9
問題 フィボナッチ数Fiは F1 = 1, F2 = 2, Fi+2 = Fi+1 + Fiであらわされる数列である。 n, kが与えられたとき、 Σ[1≦i≦n] Fi * i^kをmod 10^9 + 7で求めよ。 制約条件 n≦10^17 k≦40
問題 ハノイの塔がある。 通常のルールに加えて、軸iにささっている円盤を軸jに移動するときにcost[i][j]がかかる。 最初軸0にささっているn枚の円盤を、軸2に全て移動させるのにかかるコストの最小値を求めよ。 制約条件 n≦40 0≦cost[i][j]≦10000
すっごく久しぶりにratedのコンテストに参加。 いやなんか散々だった。 簡単なはずのAでn = 0のケースを忘れて3WA出してしまって物凄いペナルティを食らって、 Cむずいと思ってDをずっと考えてて解けずに終了して、実はC簡単だったという。 Bをせっかく２０…
問題 数列a[i]が与えられる。 それぞれの項から、引いた後0以下にならないように最大kを引くことができる。 なるべく出来た数列の最大公約数を大きくしたい。 最大値を求めよ。 制約条件 a[i]≦10^6 n≦3*10^5
