問題 長さnの01からなる文字列が与えられる。 この文字列に大して以下の操作を行うことができる。 任意の1文字の0,1を反転する 先頭からk*m文字の0,1を反転する（ただしkは任意の自然数） 操作を終えたあと、文字列の先頭からn-m文字の部分文字列と、末尾か…

問題 R, G, Bのどれかの色をした歯車がn個ある。 同じ色をした歯車は、すべて同じ向きに回転している。 歯車のうち、いくつかは噛み合っていて、噛み合っている歯車は必ず反対向きの回転をしている。 同じ色をした歯車同士が噛み合っていることはない。 この…

問題 英小文字からなる文字列が与えられる。 文字列に対して、文字x, yを選び、文字列に現れるすべてのxをyに置換することができる。 このときにかかるコストはxが現れている回数である。 この操作を繰り返し行い、文字列を回文になるようにしたい。 かかる…

問題 長さが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…

問題 n頂点からなる無向完全グラフで表される都市と道がある。 ここに雨がふって、それぞれの道がroads[i][j] / 8の確率で残り、 それ以外の確率で破壊される。 残った道が、木になっている確率を求めよ。 制約条件 n≦16

問題 正の整数a, b, cが与えられる。 a + b = cが成り立つように、それぞれの数字を 数字を一つ削除するごとにコストdelCost 数字を一つ挿入するごとにコストinsCost 数字を一つ置換するごとにコストrepCostで、 何回でも削除、挿入、置換ができる。 ただし…

問題 相異なる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個のドアがある。 i番目のドアを開けるのに、赤の鍵がdoorR[i]個、緑の鍵がdoorG[i]個必要である。 i番目のドアを開けると、（最初の一回だけ） 赤の鍵がroomR[i]個、緑の鍵がroomG[i]個、白の鍵がroomW[i]個得られる。 一度使った鍵は壊れるのですぐ…

問題 n個の歌があり、それぞれの歌の長さはduration[i], トーンがtone[i]である。 Tの時間のうちに異なる歌をできるだけ多く歌いたい。 トーンがaである歌の直後にトーンがbの歌を歌おうとすると、|a - b|の時間の休憩が必要である。 最大でいくつの歌を歌え…

問題 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が存在…