問題 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のグリッドがある。 最初全てのセルは白で、指定されたセルを全て黒に塗りたい。 一度の操作で、縦または横に一列に連続して並んだ白いセルを選び、 全てを黒に変えることができる。（間に黒が入っていてはだめ） 必要な操作の回数の最小値を求めよ…

問題 8x8のグリッドがある。はじめは全て白。指定されたマスを黒に塗りたい。 マスを黒く塗るためのコストは、最初は0. 二個目からは、今まで塗ったマスの中で一番マンハッタン距離が遠いマスとの距離がコスト。 全ての指定されたマスを黒に塗るためのコスト…

問題 n人が参加するプログラミングコンテストで、部屋の割り当てがある。 部屋の数はR = n / 20（小数点以下切り上げ）で、 次のように割り当てられる。 n人をレート順にソートする。 大きい順にR人ずつ取り、各人をR個の部屋にランダムに割り当てる。 （二…