TopCoder
問題 aまたはbからなる文字列が与えられる。 このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。 文字列が同じときは一つと数える。 制約条件 文字列は乱数により生成される。 n≦10^5
問題 nxn行列が与えられる。 この行列から以下の条件を満たすようにいくつか要素を選ぶ。 ・それぞれの行の中に選んだ要素が奇数個ある ・それぞれの列の中に選んだ要素が奇数個ある ・選んだ要素の積が平方数である 要素の選び方は何通りあるか、mod 10^9 +…
問題 fibonacci進法は以下の擬似コードで表されるような位取り記法である。 int[] toFibonacci(int d){ for(int i = inf; i > 0; i--){ if(fib[i] <= n){ n -= fib[i]; digit[i] = 1; } else digit[i] = 0; } return digit; } ここでfib[i]はi番目のフィボナ…
問題 n頂点からなる無向木が与えられる。 この木の辺を何本か切断して、直径がそれぞれmaxDist以下であるような木いくつかにしたい。 最小でいくつの木に分ければよいか求めよ。 制約条件 n≦51 辺の長さ≦500 maxDist≦500
問題 n頂点からなる有向グラフが与えられる。 このグラフの辺(i, j)であって、二頂点(a, b)を結ぶ最短路の一部となりうるような(a, b)の組がT個以上であるような辺(i, j)の重みw(i, j)の総和を求めよ。 制約条件 n≦50 T≦5000
問題 hxwのボードがあり、それぞれのマスは'W'または'B' 以下の操作を好きなだけ行うことができる。 種類1: マス(i, j)を選び、その隣接する４マスの色を全て反転させる。 種類2: マス(i, j)を選び、その隣接する４マスおよび(i, j)の色を全て反転させる。 …
問題 N頂点からなる木A, Bがそれぞれ与えられる。 A, Bを次のようにしてつなぐ。 長さNの順列を等確率にランダムで一つ取り、これをP[i]とする。 Aのi番目の頂点とBのP[i]番目の頂点を辺で結ぶ。 こうしてできたグラフに、長さがちょうどkの単純閉路がいくつ…
問題 長さnの部屋が一直線上に並んでいる。 containers[i]はi番目の部屋にコンテナが置いてあるとき'X'で、そうでないときは'-'である。 監視カメラがいくつかあり、一つの監視カメラは連続するL個の部屋を監視している。 それぞれの監視カメラに写っている…
問題 無向木Gが与えられる。 Gの部分誘導グラフの木H, Iであって、HとIは同型かつdisjointであるものについて、 H + I の最大値を求めよ。 制約条件 G ≦50 部分誘導グラフは、部分グラフのうち辺を勝手に削除してはダメなやつ （元のグラフにあった辺の両端…
問題 一列にN個のセルがある。それぞれのセルには高々1匹の狼が入る。 更に、M個の制約条件があり、 L[i]からR[i]番目（両端含む）のセルには合計で狼が2匹以下しかいないことがわかっている。 このとき、狼の入り方の場合の数をmod 10^9 + 7で求めよ。 制約…
問題 hxwのグリッドがある。各セルは、なにもない'.'か'v'鳥がいるかのどちらか。 鳥は二種類A, Bがいて、任意のセルの鳥について、そこからマンハッタン距離でd以下にいるセルの鳥は、全て同じ種類である。 また種類Aの鳥は一羽以上、かつ偶数羽いる。 グリ…
問題 nのsparce factorialを、 f(n) = n * (n - 1) * (n - 4) * (n - 9) * ……と定義する。 lo以上hi以下の整数nで、f(n)がdivisorの倍数であるものはいくつあるか、求めよ。 制約条件 lo, hi≦10^12 2≦divisor≦10^6
問題 次の性質をもつ自然数の集合Sをcoolであるとする。 全ての要素は0以上2^60未満 任意の異なるa, b∈Sについて(a & b) > 0 （bitwiseのand） 任意の異なるa, b, c∈Sについて(a & b & c) > 0 Sの部分集合subsetが与えられる。 サイズがNであって、subsetの…
問題 長さnの整数の列aがあり、最初はa[i]はすべて0 これを以下の操作を繰り返してa[i]をb[i]に一致させたい。 必要な操作の回数の最小値を求めよ。 すべての要素を2倍する 一つの要素を選んで+1する 制約条件 n≦50 0≦b[i]≦1000
問題 10^9行W列のグリッドがある。各セルには英小文字が書かれている。 このグリッドを（i0, j0）を左上として高さh, 幅wの長方形の一部を切り出したところ、 fragmentsで表される長方形が得られた。 グリッド全体は、長さx（1≦x≦W）の文字列を、繰り返し埋…
問題 n個の水滴滴下装置が直線上に並んでいる。 i番目の装置は0.5 + iメートルのところに設置されていて、毎秒intensity[i]滴の水滴を落とす。 ここに長さLメートルのスポンジをM枚おいて、スポンジに水滴をたらす。 スポンジは左端をちょうどxメートル（xは…
問題 hxwのグリッドがある。Xのマスは床で、そこを歩くことができる。 .のマスは床がなくて歩くことができない。 グリッドのh-1行目は全てXで、ここからスタートしてゴールのマスへ移動する。 Xの上ならば左右には自由に動けて、同じ列にあるXには、はしごを…
問題 hxwのグリッドがある。 最初全てのセルは白で、指定されたセルを全て黒に塗りたい。 一度の操作で、縦または横に一列に連続して並んだ白いセルを選び、 全てを黒に変えることができる。（間に黒が入っていてはだめ） 必要な操作の回数の最小値を求めよ…
問題 8x8のグリッドがある。はじめは全て白。指定されたマスを黒に塗りたい。 マスを黒く塗るためのコストは、最初は0. 二個目からは、今まで塗ったマスの中で一番マンハッタン距離が遠いマスとの距離がコスト。 全ての指定されたマスを黒に塗るためのコスト…
問題 n人が参加するプログラミングコンテストで、部屋の割り当てがある。 部屋の数はR = n / 20（小数点以下切り上げ）で、 次のように割り当てられる。 n人をレート順にソートする。 大きい順にR人ずつ取り、各人をR個の部屋にランダムに割り当てる。 （二…
問題 根付き木が与えられる。 この木に対して次の操作をK回行う。 K番目の操作を行ったとき、K番目の鳥がどこかの頂点に入れる確率を求めよ。操作： 根に鳥が来る。 鳥が今いる頂点に、他の鳥がまだいなければその頂点に入って終了。 そうでない場合、子を等…
問題 hxwのグリッドがあり、それぞれ'W'（狼）または'S'（羊）か'.'（何もいない）のいずれか。 ここに仕切りを入れて、わかれた区画それぞれについて、狼と羊が同時にいることがないようにしたい。 仕切りは、好きな二列の間、または好きな二行の間に入れる…
問題 'o'または'x'からなる文字列が与えられる。 i文字目がoだった場合goodのスコアを得て、xだった場合は-badのスコアを得る。 スコアを得た時点で、今までのスコアの合計が負になった文字があれば、 その文字列全体はSPAMであり、そうでないならNOT SPAMで…
問題 n個のランプとn個のスイッチがあり、それぞれ一列に並んでいる。 i番目のスイッチを押すと、i番目のランプのオンオフが入れ替わる他、 i-1番目のランプのオンオフが入れ替わる可能性があり、 i+1番目のランプのオンオフが入れ替わる可能性がある。 どの…
問題 文字列Sが与えられる。 文字を並べ替えて文字列Tを作る。 Tのそれぞれの文字は、Sの元の場所から距離i以内の場所になければならない。 できる文字列のうち辞書順で最小のものを求めよ。 制約条件 Sの長さ≦50
問題 文字列に対して次の操作が行える。 好きなiを決める。 先頭のi文字はそのままにして、次からのL文字を、アルファベットの小さい順にソートする。 残りの文字は捨てる。 与えられた文字列Sおよび整数Lについて、 この操作を好きなだけSに適用してできる…
問題 長さnの文字列tが与えられる。 長さnの文字列で、tとの編集距離がちょうどiであるような文字列を 1≦i≦nなるiについて出力せよ。 制約条件 n≦25 tおよび出力する文字は英小文字からなる
問題 50人の人がいて、n日間二人ずつプレゼントが渡される。 i日目にプレゼントを渡される人はchoice1[i]およびchoice2[i]である。 プレゼントはPieまたはDolphinで、どちらが渡されるかは決まってない。 全てのプレゼントを渡し終えた後、 各人が持っている…
問題 長いケーキがある。 nの約数のうちn以外の人数の友達が来る可能性がある。 どの人数の友達が来ても、ケーキを連続する区間で同じ長さだけ配れるようにするため、 切れ目を入れておく、切れ目の数の最小値を求めよ。 制約条件 n≦100000
問題 n個の都市が双方向に通行可能な道でつながれていて、木をなしている。 ここにどの都市にいるかを検知するシステムを作る。 発信機を好きな都市に置くことができて、 受信機ではそれぞれの発信機からの距離（木における距離）を知ることが出来る。 全て…
