問題 テトリスのL字ブロック ■ ■ ■■ ■ ■ ■■を両方少なくとも1回ずつ使って、nxmの長方形のフィールドを隙間なく埋めることができるかを判定せよ。 ブロックは回転させてもよいが、反転させたり、重ねたり、フィールドの外に出したりしてはならない。 制約条…
問題 0, 1のみからなる長さの同じ二つの文字列s, tが与えられる。 s, tに長さが等しく、sからのハミング距離がd1で、tからのハミング距離がd2であるような文字列はいくつあるか。 mod 10^9 + 7で求めよ。 制約条件 s ≦10^5
問題 A, BがいてAが数列a[i], Bが数列b[i]を持っている。 a[i]の長さはn, b[i]の長さはmである。 a[x[i]] = b[y[i]]という関係x[i], y[i]がc個与えられる。 二人が一緒に数を書いていく。 Aはk回目にa[k % n]を書いて、Bはk回目にb[k % m]を書く。 二人の数…
問題 1以上1000以下の整数の秘密の数を当てる。 質問は200回まですることができて、質問では、 好きな自然数xに対して、秘密の数がxの倍数かどうかを聞くことができる。 秘密の数を当てよ。
問題 日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_a）
問題 日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_k） 文字列s1, s2, ... snの中のうち、文字列tを連続する部分文字列として含むものの個数をkとする。k * |t|の最大値を求めよ。 制約条件 n≦10^5 Σ|si|≦10^5
問題 文字列sが与えられる。次のようなクエリq個に答えよ。sの連続する部分文字列で、文字列x, yをともに連続する部分文字列として含むような文字列のうち、長さが最小のものの長さを出力せよ。 そのような文字列が存在しない場合-1を出力せよ。 x, yはオー…
問題 n個の図形が与えられる。 それぞれの図形は半径r[i], 中心が(x[i], y[i])の円か、 それぞれの頂点が(x[i_0], y[i_0])..., (x[i_k-1], y[i_k-1])k[i]角形どちらか。 この図形の凸包の長さを求めよ。 制約条件 n≦100 k[i]≦10 答えは小数点以下6桁まで出力…
問題 n頂点からなる無向木が与えられる。 各頂点には重みwiがついている。重みの初期値が与えられる。 この木に対して次のようなクエリがq個来るので、答えよ。 t a b c t = 1のとき、木の頂点aから頂点bへのパス上にある頂点全ての重みをcに変更する。 t = …
問題 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個の部屋を監視している。 それぞれの監視カメラに写っている…
問題 a[i]が与えられる。 (i - j)^2 + (Σ[k=j,i]a[k]) ^ 2の最小値を求めよ。 制約条件 a[i]の要素≦10^5 |a[i]|≦10^4
問題 n頂点からなる木で、各頂点以下の部分木のサイズがc[i]であるような木であり、 葉以外の頂点では直接の子が二つ以上のものが存在するか、 存在するならYESを、そうでないならNOを出力せよ。 制約条件 n≦24
問題 hxwのグリッドがある。各セルには得点が定められている。 Aは(1, 1)から(h, w)へ移動し、Bは(h, 1)から(1, w)へ移動する。 Aは右または下にのみ移動できて、Bは右または上にのみ移動できる。 A, Bの軌跡で共通部分はただ１つのセルでなければならない。…
問題 n頂点からなる根付き木が与えられる。各頂点は最初0または1である。 このグラフに対して次の操作が好きなだけできる。 操作：好きな頂点vをえらび、vおよび、vの子孫uでdepth(u)-depth(v)が偶数の頂点uの0, 1を反転させる。 最終状態が与えられるとき、…
問題 無向木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のグリッドがある。 最初全てのセルは白で、指定されたセルを全て黒に塗りたい。 一度の操作で、縦または横に一列に連続して並んだ白いセルを選び、 全てを黒に変えることができる。（間に黒が入っていてはだめ） 必要な操作の回数の最小値を求めよ…
