問題 n人の人がいて、それぞれの責任感r[i]および年齢a[i]が与えられる。 この人の中から、次の条件を満たすグループを作りたい。 責任感r[i]が最大の人（タイの場合はタイの中の誰でもいい）をリーダーとする。 リーダーと、他の全員の年齢の差がkである。 …

問題 n頂点m辺からなる無向二部グラフが与えられる。 このグラフの頂点をちょうどk色で、それぞれの色が3回ずつ現れるように彩色したい。 そのような彩色は可能であるか、不可能ならNOを、 可能ならYESおよび、解を具体的に一つ出力せよ。 制約条件 n, m≦10^5

問題 3次元空間に球がいくつかある。 空間を平面z = aで切ったときに、 球と平面の交点は円になるが、その円いくつの連結成分にわかれているか、 z = 0からz = 36000まで、連結成分の個数の変化を出力せよ。 制約条件 n≦100

問題 n個の文字列b1, ..., bnが与えられる。 m個のインデックスi1, ..., imが与えられる。 文字列tを、bi1 + bi2 + ... + bimとする。（ただし+は文字列の結合をあらわす） 別の文字列sが与えられる。 このとき、sとtの最長共通部分列（連続しなくともよい）…

問題 n x mのグリッドに数字が書かれている。 グリッドの数字を渦のように足す（図参照） このとき、全ての足し方のうち、和が最大になるような足し方の和を求めよ。 制約条件 n, m≦500

問題 線分をつないだ図形が与えられる。 線分の両端点が、他の線分上にある線分は道路であり、 一方の端点のみが他の線分上にある線分は、道路に対する標識である。 標識と道路となす角が90度以上のとき、その道路は角度の大きいほうから小さいほうへ通るこ…

問題 数列a[i]が与えられる。 この数列のうち、最大k個の符号を好きに変えることができる。このとき、連続するlen個の区間の和の絶対値| Σ[j = i to i + len - 1]a[j] | の最大値を求めよ。 制約条件 n≦10^5 a[i]≦10000 k≦n

問題 xy平面上の点Aから点Bまで移動したい。 レーザーが、a秒間のチャージの後でb秒間照射される、その後またa秒間のチャージの後でb秒間照射される という規則で照射される。 レーザーがチャージ中の時間は、1単位時間あたり1単位距離の移動が可能であるが…

問題 n個の整数の列がある。それぞれの数は1以上m以下である。 この列から最大k個を取り除いて、同じ整数の続く部分の長さを最大にしたい。 同じ整数の続く部分の最大の長さを求めよ。 制約条件 n≦2*10^5 m≦10^5 k≦n

問題 n個のきゅうりに水をやりたい。 きゅうりは一次元の直線上に並んでいて、それぞれの座標はx[i]である。 きゅうりには、与えられた順番で水をやる必要がある。 座標平面上にはk個、テレポーターを自由な場所に設置することができて、 テレポーターを使う…

問題 n個のランプとn個のスイッチがあり、 それぞれのランプはそれぞれ異なるスイッチただ一つにつながっている。 スイッチがOFFのとき、対応するランプもOFFである。 いま、スイッチをswitch[i]で表されるスイッチをONにしたところ、 それぞれlump[i]で表さ…

問題 A,C,G,Tからなる文字列n個が与えられる。 n個全てに出現する文字列のうち、最も長さの長い文字列の長さを求めよ。 制約条件 n≦6 それぞれの文字列の長さは100万以下

問題 直線上にN個のブイがあり、ブイとブイの間に一匹ずつ魚がいる。 魚にはそれぞれ'O', 'X', '*'の文字が割り振られている。 この魚を次のように網で囲う。 網は自己交差のない閉曲線で表される。 網は直線と、ブイの点のみで交わる。 ブイで直線と網が交…

問題 n個の箱があり、それぞれに次の条件を満たすように石をいくつか入れる。 石は無限にある i番目の箱には、石をまったく入れないか、lowerBound[i]以上upperBound[i]以下の石を入れる。 全ての箱の石の合計が9000個より多い このとき、全ての石の合計とし…

問題 hxwのグリッドがあり、(0,0)から右か下へ移動することを繰り返し、(h,w)へ移動する。 それぞれの辺には1から9までの数字が割り振られている。 どのような経路をたどっても、ゴールへ移動するまでに通った辺の数字の和が一定になるように、辺の数字を変…

問題 英小文字からなる文字列がある。 この文字列の任意の二文字を入れ替える操作を繰り返して、文字列を回文にしたい。必要な操作の回数の最小値を求めよ。 不可能な場合は-1を返せ。 制約条件 文字列の長さ≦50 同じ文字は高々2つまでしか現れない。

問題 h x wの長方形の領域に、1x1, 2x2, ... mxmの正方形のタイルを敷き詰める。 使わないタイルがあったり、タイル同士が重なったりしてはならない。 タイル同士には隙間があってもよい。 このとき、最大のmを求めよ。 制約条件 h, w≦30

問題 h x wの長方形の土地がある。 それぞれのマスの危険度grid[i][j]が与えられる。 このとき、次のようなクエリq個に答えよ。 (r1[i], c1[i]), (r2[i], c2[i])を頂点とするような長方形の中で、 最も危険度が低いマスの危険度の値を答える。 制約条件 h * …

問題 n段の階段があり、ちょうどn枚の長方形の板でできている。 長方形の板には重なりやはみだしがない。 このようにして作れる階段を全部つくり、階段を（一つの階段は一色で）それぞれk色のどれかで塗る。 このようにして出来上がるものは何通りあるか、mo…

問題 1番から順に番号のついたビリヤードの球が、下図のようにn段に並んでいる。 [ 5] [ 2][ 3] [ 4][ 1][ 6] [ 7][ 8][ 9][10] [11][12][13][14][15]1の球に対して、上下に隣接する球のいずれかと入れ替える操作を行うことができる。 [ 1] [ 2][ 3] [ 4][ 5…

問題 n個のバルブとm個のスイッチがある。 それぞれのスイッチがどのバルブにつながっているかは、switchesにより与えられる。 最初、それぞれのバルブはinitial[]の状態となっている。 スイッチを押すと、つながっているバルブの状態のONとOFFが切り替わる…

問題 木の棒がN本、環状に並んでいる。 i番目とi+1番目、0番目とN-1番目はそれぞれ隣り合っている。 0番の木の棒を(startR, startG, startB)の色に塗る。 i番目の棒を塗り終えた後、i+1番目の棒を、次のようにして塗る。 i番目の棒の色を(R', G', B')、新し…

問題 w x hのグリッドであらわされる部屋がある。 部屋の各マスは0（ふつうのマス）または1（破損したマス）のどちらかである。 今、正方形のカーペットを何枚か敷いて、0のマスは一切覆わずに1のマスを全て覆いたい。 カーペットは好きな大きさのものを何枚…

問題 n個の頂点、m本の辺からなる無向グラフが与えられる。 このグラフにおいて、頂点のペア(i, j)がdoubleであるとは、 任意のノードkについて、i-kに辺があるときはj-kに辺があり、i-kに辺がないときはj-kに辺がないようなことを言う。 （i-jには辺があっ…

問題 n人の容疑者がいて、それぞれは "x番の人が犯人である"または、 "x番の人は犯人でない"と主張している。 容疑者のうち、m人は本当のことを言っていることがわかっている。 このとき、それぞれの容疑者について、 確実に本当のことを言っている人にはTru…

問題 英小文字からなる文字列sが与えられる。sの連続する部分文字列uを任意に一つ選ぶ。 uに対して、 先頭または末尾に一字を加える。 先頭または末尾の一字を消す。 任意の一文字を、別の文字に変える。 の操作を行うことができる。 最小で何回の操作を行え…

問題 英小文字からなる文字列sが与えられる。 sの任意の連続する二文字に対して、1文字目をアルファベット順で一つ進めて、2文字目を一つ戻す、 または1文字目を一つ戻して、2文字目を一つ進める、 という操作が何度でも行える。 ただし、aの前の文字は存在…