TopCoder
問題 n個の直方体の箱があり、それぞれの高さ、幅、奥行きがわかっている。 この箱のうち、好きなものを選び積み上げて塔を作る。 塔は、それぞれの箱を軸に平行に置かねばならず、 箱の底面は、一つ前の箱の底面からはみでてはならない。 箱は自由な向きで…
問題 n個の土地が円周上に並んでいる。 それぞれの土地の高さはheight[i]である。 この土地に対して次のような操作をT回行う。 heightが正であるような土地i全てについて、height[i]を1減らし、height[(i + 1) % n]を1増やす。 この操作は全て同時に行われる…
問題 座標平面上にx座標, y座標がそれぞれ全て互いに異なるN個の点がある。この点のうち、三つを取りそれらをr, g, bとする。 x[r] 制約条件 N≦300000 0≦座標の値<10^9
問題 b + a * i(i = 1, 2, .., n)で表される数列を、二進数で表現し、 初項から隙間をあけずに全部並べて書いた文字列をsとする。 この文字列に含まれる、"01"と、"10"の個数を求めよ。 制約条件 1≦a≦40000 1≦b≦10^18 1≦n≦10^12
ちょうどSRM初参加から3年、ようやくレッドコーダーになれました。 1年半くらい前から、実力的には赤になっていると言い続けていましたが、 どうしてもレートが伸び悩んで、Mediumを全部解いたりしました。 それでも1年以上赤になれなくて、本当に苦しかった…
問題 一人がn桁の数字を思い浮かべ、もう一人がその数字を当てるゲームをする。 (leading zeroがあってもよい) 当てるほうは、n桁の数字をm個言う。 それぞれに対して、自分の数字と言われた数字で、一致している桁数を答える。 言った数字と、そのときに…
問題 文字列の集合がある。 この中の一つの文字列を取り(これをSとする) Sの先頭2*i(2*i≦|S|)文字を逆順にする操作を好きなだけ行うことができる。 操作を行った後で、二つの文字列が一致したら、 その文字列を消去することができる。 残る文字列の数の最…
問題 座標平面上にn個の点がある。 このn個の点を以下の条件を満たす辺でつなぎたい。 辺はy[i] > y[j]であるときに限りiからjに張ることができる 全ての点は連結である 全ての点の入次数は1以下、出次数は2以下 辺の長さの和が最小になる このとき、辺の長…
問題 'a', 'b', 'c'からなる同じ長さの文字列word1, word2が与えられる。 word1の文字一つ選び、 aならbに bならcに cならaに変えるという操作を行う。 aをbに変える操作はcosts[0]が、 bをcに変える操作はcosts[1]が、 cをaに変える操作はcosts[2]がかかる…
問題 hxwマスのグリッドがある。 一番上の列と下の列はループしてつながっていて、 右端と左端もループしてつながっている。 それぞれのマスには上下左右いずれかの向きの矢印が書かれている。 一点からスタートした人は、その矢印に従って移動することを繰…
問題 n個の都市があり、そのうち0番からm - 1番のm個の都市は特別な都市である。 これらの都市をk本の道で以下の条件を満たすように接続したい。 条件を満たす接続方法をmod 10^9 + 7で求めよ。 一つの道路は異なる二つの都市を結ぶ ひとつの二つの都市のペ…
問題 n頂点からなる無向グラフが与えられる。 頂点には重みa[i]がついている。 このグラフの大きさ2*n/3以上のクリークで、 重みの和が最大になるものにおける、重みの和を求めよ。 クリークが存在しないとき、-1を返せ。 制約条件 n≦50 a[i]≦100000
問題 nxnの行列がniceであるということを以下のように定義する。 行列のそれぞれの行に対して、列を重複なく一つずつ選ぶ。 このとき、列をどのように選んだとしても、選んだ成分の和が一定であるときその行列はniceである。 行列が与えられる。 いくつかの…
問題 座標平面上の点の集合pに対して、次のようにして点の集合qをつくる。 (x, y), (x+1, y), (x, y+1), (x+1, y+1)に点があるとき、 (x+0.5, y+0.5)をqに加える。 p := qとする。 座標平面上にn個の点(x[i], y[i])がある。 この点の集合は、ある集合に対し…
問題 無限に広いチェス盤がある。最初どのマスにも駒は置かれていない。 左上を(0, 0)とする。以下t回以下の操作を繰り返す。 1回目は(0, 0)にAを置く 次からはB, Aと交互に置く (x - 2, y)と(x - 1, y - 1)の2マスのうち、どちらか一方のみに今置こうとして…
問題 有向グラフが与えられる。 0番の頂点から出発して、 枝の出ている頂点のうち、もっとも番号の小さい頂点に移動することを繰り返す。 この移動で、n-1番の頂点にいけるように、 枝を好きに削除することができる。 削除しなければならない枝の本数の最小…
問題 HxWマスのグリッドがあり、それぞれのマスは'L'または'P'または'.'である。 このグリッドに、二つの互いに交わらない長方形を書き、 その中に入っている(Lの数) + (Pの数)を最大化したい。ただし、(Lの数) と (Pの数)の差の絶対値はmaxDiff以下でなくて…
問題 HxWのグリッドを'B'または'W'の色で塗る。 既に色が塗られているところはB, Wの文字が書かれていて、 そうでないマスには'?'が書かれている。 このグリッドの?のマスを全てBまたはWの色で塗り、以下の条件を満たすようにしたい。 全ての同色のマスは、…
問題 n個の建物があり、それぞれの高さはheights[i]である。 この建物を一列に並べるが、隣合う建物同士の距離は、隣合う建物のうち大きいほうの高さでなくてはならない。 列の端から端までの距離が最小になるような並べ方のうち、 辞書順で最小のものを求め…
問題 HxWのグリッドがあり、はじめ全てのグリッドは0である。 1行を自由に選んでその0, 1を反転する操作を合計Rcount回行い、 1列を自由に選んでその0, 1を反転する操作を合計Ccount回行う。 操作を行った後で、1の個数がS個になっているような、 操作の選び…
問題 少女がn人いて、i番目の少女がj番目の少女を愛しているかのグラフが与えられる。 グラフは対称ではない。 このグラフに対して以下の操作を好きなだけ行うことができる。 初期状態で、全ての少女は魔法少女ではなく、護られている少女ではない。 魔法少…
問題 座標平面の第一象限に青い点がいくつかあり、 x軸の正の部分に赤い点がいくつかある。 これらの点から青い点P, Qおよび、赤い点A, B, C, Dを選び、 三角形PADが三角形QBCを厳密に含み 角PAD, 角PDA, 角QBC, 角QCBが全て90度より厳密に小さい とき、これ…
問題 木が与えられる。 この木のそれぞれのノードを、1/2の確率で赤、1/2の確率で白に塗る。 塗り終えた後で、同じ色のノードを全て連結にするために、自由に辺を足す。 ただし、それぞれのノードに新たに追加できる辺は、 1本目は無料で、2本目以降は1ずつ…
問題 n階立ての建物があって、i階目にはstudents[i]人の人がいる。 Jediは一人でK人の人を倒すことができる。 x人の人が一つの階にいるとき、x/K(切り上げ)人のJediが必要である。 それぞれのstudentsを、動かさないか、上下の隣り合う階に移すことができる…
問題 文字列の集合Sが与えられる。 先手はこのうちひとつの文字列を選ぶ。これをxとする。 また、先手はアルファベットに好きな順に優先順位をつける。 後手は、Sのうちx以外の文字列を好きに並べ替える。 並べ替えたあと、xがSのなかで、他のどの文字列より…
問題 n個の都市が円上0, 1, 2, ..., n - 1, 0という順に並んでいる。 最初0の都市にいて、 1日目には1個隣の都市のどちらかに、 2日目には2個隣の都市のどちらかに、 ... とm日間移動を繰り返す。 m日の移動が終わった後に都市0にいるような移動ルートは何通…
問題 滑り台とは、座標平面上のn個の支点と、m本のパスであって、 パスは、異なる二つの支点をつないだ線分である。 滑り台のパスは交差していてはならない。 今、支点の数nと、支点と支点をつなぐパスm本が与えられる。 このパスのうち、いくつかを取り除い…
問題 座標平面上に白い点がn個、黒い点がm個与えられる。 これらの点から異なる4点を選び、checkerな四角形を作ることができるならば、NOを、 作ることができないならばYESを答えよ。 ただし、checkerな四角形とは、白い点、黒い点、白い点、黒い点を順に結…
問題 それぞれに1つの数字が書かれたn枚のカードがあり、i番目のカードの数字はdigits[i]で表される。 1枚目のカードをまずテーブルに置き、2枚目以降のカードを次のようにおく。 今までに置いたカード全部よりも右側に置く。 今までに置いたカード全部より…
問題 n枚のカードが一列に並んでいる。 カードにはlevel, damageが設定されており、i番目のカードのlevelはlevel[i], ダメージはdamage[i]である。 このカードに対して次の操作のどちらかを行う。 1. 先頭のカードを末尾へ移動する。 2. 先頭のカードの右に…