動的計画法
問題 カードをN枚買いたい。 最初0円もっていて、毎日のはじめにP円もらえる。 カードは一日M枚まで買えて、i枚買うのにx[i]円かかる。 カードを合計N枚買うのにかかる日数の最小値を求めよ。 制約条件 N≦100 M≦20 P≦10万 x[1]≦P
問題 二次元平面上にn匹きつねがいて、 位置が(x[i], y[i]), パワーがd[i]. （何度でも）i番目のきつねにコスト1を支払うとそのきつねのパワーを1上げることができる。 きつねi, jは(iのパワー)+(jのパワー)がi, jのユークリッド距離以上ならば通信できる。 …
問題 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頂点からなる木で、各頂点以下の部分木のサイズがc[i]であるような木であり、 葉以外の頂点では直接の子が二つ以上のものが存在するか、 存在するならYESを、そうでないならNOを出力せよ。 制約条件 n≦24
問題 hxwのグリッドがある。各セルには得点が定められている。 Aは(1, 1)から(h, w)へ移動し、Bは(h, 1)から(1, w)へ移動する。 Aは右または下にのみ移動できて、Bは右または上にのみ移動できる。 A, Bの軌跡で共通部分はただ１つのセルでなければならない。…
問題 無向木Gが与えられる。 Gの部分誘導グラフの木H, Iであって、HとIは同型かつdisjointであるものについて、 H + I の最大値を求めよ。 制約条件 G ≦50 部分誘導グラフは、部分グラフのうち辺を勝手に削除してはダメなやつ （元のグラフにあった辺の両端…
問題 一列にN個のセルがある。それぞれのセルには高々1匹の狼が入る。 更に、M個の制約条件があり、 L[i]からR[i]番目（両端含む）のセルには合計で狼が2匹以下しかいないことがわかっている。 このとき、狼の入り方の場合の数をmod 10^9 + 7で求めよ。 制約…
問題 n個の水滴滴下装置が直線上に並んでいる。 i番目の装置は0.5 + iメートルのところに設置されていて、毎秒intensity[i]滴の水滴を落とす。 ここに長さLメートルのスポンジをM枚おいて、スポンジに水滴をたらす。 スポンジは左端をちょうどxメートル（xは…
問題 8x8のグリッドがある。はじめは全て白。指定されたマスを黒に塗りたい。 マスを黒く塗るためのコストは、最初は0. 二個目からは、今まで塗ったマスの中で一番マンハッタン距離が遠いマスとの距離がコスト。 全ての指定されたマスを黒に塗るためのコスト…
問題 根付き木が与えられる。 この木に対して次の操作をK回行う。 K番目の操作を行ったとき、K番目の鳥がどこかの頂点に入れる確率を求めよ。操作： 根に鳥が来る。 鳥が今いる頂点に、他の鳥がまだいなければその頂点に入って終了。 そうでない場合、子を等…
問題 hxwのグリッドがあり、それぞれ'W'（狼）または'S'（羊）か'.'（何もいない）のいずれか。 ここに仕切りを入れて、わかれた区画それぞれについて、狼と羊が同時にいることがないようにしたい。 仕切りは、好きな二列の間、または好きな二行の間に入れる…
問題 n個のランプとn個のスイッチがあり、それぞれ一列に並んでいる。 i番目のスイッチを押すと、i番目のランプのオンオフが入れ替わる他、 i-1番目のランプのオンオフが入れ替わる可能性があり、 i+1番目のランプのオンオフが入れ替わる可能性がある。 どの…
問題 長さnの文字列tが与えられる。 長さnの文字列で、tとの編集距離がちょうどiであるような文字列を 1≦i≦nなるiについて出力せよ。 制約条件 n≦25 tおよび出力する文字は英小文字からなる
問題 n個の店があって、i番目の店はfirst[i]日目に開店する。 i番目の店はred[i]個の赤い玉、green[i]個の緑の玉、blue[i]個の青い玉を持っていて、 first[i]日目から連続して、一日に一つずつを売り、全ての玉を売ったら閉店する。 同じ日に３つ以上の店が…
問題 一列にカードが並んでいて、i番目のカードの色はC[i]で与えられ、R, G, B, Wのどれか。 整数Mが与えられるとき、Wのカードに以下の条件を満たすようにR, G, Bの色を塗る塗り方は何通りあるか、mod 10^9+7で求めよ。 条件： 適当な整数Dをきめたとき、R,…
問題 h行w列の行列があって、(i, j)にはp[i][j]の数字が書かれている。 この行列の一つのセルを、p[i][j]に比例する確率で選ぶことを繰り返す。 全ての行と列について、その行、列に属するセルが一度以上選ばれる状態になったら、 操作を終了する。 操作が終…
問題 n頂点からなる無向木が与えられる。 各辺には重要か重要でないかと、初期状態でオンかオフかが与えられる。 木の二頂点を選び、その頂点を結ぶ最短パス上にある辺全てのオンオフを入れ替えるという操作を繰り返し、 重要な辺全てをオンであるようにした…
問題 n個の遺跡があって、i番目の遺跡は種類kind[i]のものであり深さdepth[i]に埋まっている。 掘削機で遺跡を発掘することができる。 掘削機は掘る深さが一番最初にだけ自由に設定できて（途中で変更はできない）、 Dの深さでi掘ったとき、D≧depth[i]ならそ…
問題 n本のビルがあって、i番目のビルは色がC[i], 高さがiである。 このビルを一列に並べたとき、前から見て色の境界がL-1個であるような並べ方の総数を求めよ。 制約条件 n≦2500 L≦2500
問題 二つの長さnの順列A, Bに対してmagic(A, B)を、 max(A[0], B[0]) + max(A[1], B[1]) + … + max(A[n-1], B[n-1])と定義する。 magic(A, B)がk以上になるような長さnの順列A, Bは何通りあるか、求めよ。 制約条件 n≦50 k≦2500
問題 要約不能なので元の問題文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp14Day3&pid=F） 数直線上にn個の点が左から順に並んでいて、 1番の点からn番の点まで、D回以下の移動で移動したい。 一回の移動ではi->jの好きな点…
問題 n人がいて、それぞれ番号が1〜n番である。 全員がピストルとk発の弾をもっていて、k回つぎのことを行う。 自分以外の生存者のうち、番号がもっとも小さい人に向けて同時に銃を撃つ。 i番目の人が撃った銃は、p[i]%の確率で当たる。弾が当たった人は死ぬ…
問題 座標平面上にn個の滑車と2本の釘がある。 i番目の滑車は((i+1) * d, 0)の位置にあり、釘は(0, 0)および((n + 1) * d, 0)にある。 滑車の半径はrで、どの二つの滑車も接触しないことが保証されている。 原点の釘からもう一方の釘へ、ロープをたるまない…
問題 ダイアル式のロックがある。 現在表示されている数字はsで、これをtにしたい。 一回の操作では、それぞれの数字を+1または-1することができて、9を+1すると0, 0を-1すると9になる。 また、連続している位置にある数字は同じ回転ならいくつでも同時に操…
問題 数直線上y = 0の線を、x = lからx = rまで移動したい。 n個のライトがあって、それぞれの座標は(x[i], y[i])で、 a[i]度の角度の範囲だけを照らすことができる。 移動できる部分は、線分に一つ以上のライトがかかっているところだけ。 最大でどれだけ移…
問題 n個の数aiが与えられる。 m = a1 * a2 * ... * anとする。 mをn個の数の積b1 * b2 * ... * bnとしてあらわす方法は何通りあるかmod 10^9 + 7で答えよ。 制約条件 n≦500 ai≦10^9
問題 集合Sがperfectであるとは、任意の（同一でもよい）a, b∈Sについて、 (a xor b)∈Sとなることを言うものとする。 全ての要素がk以下であるようなSの選び方は何通りあるか、 mod 10^9 + 7で求めよ。 制約条件 k≦10^9
evima先生作問。 問題 n人の人がいて、それぞれの名前が与えられる。 i番目の人の名前はj番目の人のprefixであるというグラフを作る。 このグラフの頂点に以下の制約を満たすように0〜n-1の番号を振りたい。 m個のinfoが与えられて、info1[i]番の頂点はinfo2…
問題 長さnの順列Pが与えられる。（整数1〜nの順番を並べ替えたもの） これに対して、次のような操作を高々K回行うことができる。 二つの数(i, j)を選ぶ。i≦k≦jなる全てのkについて、P[k]をmax{P[k]|i≦k≦j}で置き換える。 P = {1, 7, 2, 3, 6, 4, 5} に対し…
