Codeforces
問題 長さがnの数列 1 2 3 4 ... n-1 nがある。 この数列に対して3回以下、以下のような操作を行った。 l, rを選びaの区間[l, r]の順番を反転させる。 結果の数列が与えられるとき、操作の仕方としてありえるものをどれか一通り出力せよ。 制約条件 n≦1000
問題 長さが2^nの配列が与えられる。 配列に対する値vを以下のように計算する。 (a[0] or a[1]), (a[2] or a[3]), (a[4] or a[5]) ...を新たな数列aとする (a[0] xor a[1]), (a[2] xor a[3]), (a[4] xor a[5]) ...を新たな数列aとする というように、隣接す…
新環境のテストも兼ねて出てました。がDの誤読で酷いことになった。 問題 1〜10までの重さの錘のうち、使うことができる種類のものが与えられる。 個数に制限はなく、無限に使える。 これをm回天秤に以下のルールで乗せる。 交互に違う皿に置く。 2回連続で…
問題 nxnのグリッドがあり、(x, y)の点がt = 0において色がついている。 1秒ごとに、色のついているマスと辺を共有している色のついてないマスに色がつく。 全体でc個以上のマスに色がつくのにかかる時間を求めよ。 制約条件 n≦10^9
問題 nxmのアルファベット小文字の書かれたグリッドがある。 このグリッドの部分長方形うち、四隅のアルファベットが同じで、含まれている'a'の個数がk個であるようなものの個数を求めよ。 制約条件 n, m≦400 k≦nm
問題 問題文中の擬似コードにしたがって(m+1)x(m+1)の行列を埋めたとき、 最後の行に現れる1の数がtに等しいようなmのうち、 m≦nを満たすものはいくつあるか求めよ。 行列の埋め方は要約すると以下の通り。 1行目は右上だけを1にする。 a[i][j] = a[i-1][j-1…
問題 相異なる2以上のn個の整数a[i]を全て含むようなdivisor treeのうち、頂点数が最小のものの頂点数を求めよ。 ただしdivisor treeとは以下のような木である。 各頂点には整数が書かれている 葉の頂点の整数は素数 そうでない頂点の整数は、その子の頂点の…
問題 n頂点からなる木のうち、m個の頂点から被害が出ている。 頂点のうち1箇所に悪霊がいて、被害の出ている頂点は全て、悪霊のいる頂点からの距離がd以内である。 このとき、悪霊のいる頂点としてありうる頂点の個数を求めよ。 制約条件 n, m, d≦10^5
問題 n問のクイズをやって、ちょうどm問正解した。 このクイズは正解すると1問につき1点で、 k回連続で正解すると、（1点が加えられた後で）現在の得点が倍になる。 （その後、連続正解数のカウントは０に戻る） 得られた得点の最小値を求め、mod 10^9+9で出…
問題 n頂点からなる木が与えられる。 木のそれぞれの頂点に、以下のような条件を満たすように'A'から'Z'の一文字のラベルを割り当てる。 同じラベルを持つ任意の頂点u, vについて、uからvへのパス上に、uのラベルよりも 小さいアルファベットのラベルを持つ…
問題 黒板に二行に数字を書く。 最初、上の行に0, 下の行に1を書いた後で次の操作を繰り返す。 Tの操作 上の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 Bの操作 下の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 これをn回行った…
問題 長さnの英小文字からなる文字列が与えられる。 この文字列の（必ずしも連続しない）部分文字列で、長さがちょうど100の回文は存在するか。 存在するならそれをどれか一つ、存在しないなら、部分文字列の回文のうち最も長いものをどれか一つ出力せよ。 …
問題 n個の数列がある。 この中からk個以下の数字を削除して、連続する同一の数字の長さを最大にしたい。 その最大値を求めよ。 制約条件 n≦2 * 10^5
問題 n人が一隻のボートを使って河を渡りたい。 ボートにはwKgまでの人が乗れる。i番目の人の重さはa[i]で、全て50または100kgのどちらかである。 ボートは一人以上の人間が乗っていないと動かせない。全員が向こう岸に最短回数のボートの移動で移るような移…
問題 n個の数列a[i]を互いに素な二つのグループにわける。片方が空であってもよい。 f(i, j)を、i, jが違うグループのときa[i] + a[j] + h, 同じグループのときa[i] + a[j]とする。max{f(i, j) | 1≦i＜j≦n} - min{f(i, j) | 1≦i＜j≦n}が最小となるようなわけ…
問題 hxwの行列がある。 この行列のうち、(a, b)を左上(c, d)を右下とするような長方形を選ぶ。 角の4つの数字の最小値の最大値を求めよ。 制約条件 h, w≦1000 数字≦10^9
問題 n人の人がいて、それぞれの人の大きさはa[i]である。 n人はn!通りの並び方を等しい確率で選んで並ぶ。 大きさの和がp以下であるような部分だけ、列の先頭から人がレストランに入れる。 入る人が、入れない人を飛ばすことはできない。 レストランに入れ…
問題 無向木が与えられる。 この木上を、m個の出発点とゴールの組(ui, vi)について、 uiから一人が出発し、viへゴールする。 それぞれの辺について、合計何人が通るか求めよ。 制約条件 n≦10^5 m≦10^5
問題 01からなる文字列で、0がn個1がm個ちょうど含まれているものを考える。 この文字列に対して、以下の操作を繰り返した後で、最後にgになるものの個数を求めよ。 操作： 文字列が1文字になっていたら終了 末尾が00のとき、1に置き換える 末尾が01のとき、…
問題 n個の正の整数a[i]が与えられる。 a[i]から異なるk個を選びb[0], ..., b[k-1]とする。 b[0] & b[1] & ... & b[k-1]を割り切る2^vのうち、vの最大値を bの美しさと呼ぶ。（&はビット演算のand） ただし最大値が存在しないときは美しさは-1である。 美し…
問題 平面上に半径Rの円が2m個ある。 A1〜Amは中心が座標((2i - 1)R, 0)にあり、 B1〜Bmは中心が座標((2i - 1)R, 2R)にある。 円Aiの中心から円Bjの中心へ、2m個の円の内部または周だけを通って行くときの最短距離をd(i, j)とする。 全ての1≦i, j≦mに対するd…
問題 長さnの数列a[i]が与えられる。 a[i]の空でない、（必ずしも連続しない）非減少部分列のうち、異なるものを全て取り出す。 それぞれに対して、それより"小さな"列の個数を求め、足し合わせる。 個数の総和はいくつか。 ただし、列xiよりyiが小さいであ…
問題 文字列aをb回繰り返すことを(a, b)と書く。 文字列a, cおよびそれらの繰り返し回数b, dが与えられる。 w = [a, b], q = [c, d]としたとき、 [q, p]がwの（必ずしも連続しない）部分文字列となるような最大の整数pを求めよ。 そのような正の整数pが存在…
問題 n個の町がn^2本の道でつながっている。 車がm個あり、それぞれの車で町iからjまで行くのにかかるコストが与えられる。 ここでr回のレースをする。 i回目のレースではsiからtiまで移動する。 この際、車をki回まで乗り換えてよい。 車は任意の町で、時間…
問題 n桁の正整数であって、 0, 1, 2... ,9の数字がそれぞれa[0], a[1], ..., a[9]回以上現れるようなものはいくつあるか、求めよ。 leading zeroは許されない。 制約条件 n≦100
問題 nxnのそれぞれのマスに数字a[i][j]が書かれたグリッドがある。 Aさんがグリッドの左上から右下まで、右か下だけに移動しながら移動する Bさんがグリッドの右下から左上まで、左か上だけに移動しながら移動する このとき、「二人の少なくともどちらかが…
問題 数列a[i]が与えられる。 数列の連続する部分列(a[i], a[i+1], ... a[j])のうち、 同一の値をk個以上含むものの個数を求めよ。 制約条件 n≦4*10^5
問題 n種類のコインを投げて、出た面を順番に記録する。 i番目のコインが表の確率はp[i]である。このとき、連続する○の大きさの二乗の総和 （たとえば○○×○××だったら、2^2 + 1^2 = 5）の期待値を求めよ。 制約条件 n≦10^5 0≦p≦1
問題 辺に文字列のついた根付き木が与えられる。 この木から文字列を以下のようにして作ることができる。 始点の(枝，枝の文字の何番目か）、終点の（枝，枝の文字の何番目か）を選ぶ。 必ず始点のほうが根に近いほうを選ぶものとする。 始点枝から終点の枝…
問題 n行m列のグリッドが与えられる。各マスは'.'または'#'である。 #のマスが連結であるとは、「どの二つの#のマスも、辺を共有するような'#'を経由してたどり着ける」ことを言う。 #が一つだけのグリッド、#が一つもないグリッドは連結であることに注意す…
