2011-01-01から1年間の記事一覧
問題 'W','B'または'?'からなるhxwのグリッドが与えられる。 '?'には'W'または'B'を任意に入れることが出来る。 以下の条件を満たすグリッドは何通りあるか、求めよ。 グリッドからどのように長方形(x1,y1),(x1,y2),(x2,y1),(x2,y2)を選んでもこの頂点が同じ…
問題 Johnは文字列Jの看板を、Brusは文字列Bの看板を持っている。 Johnは看板から連続する部分文字列を、空でないかつ重ならないように二つ切り出す。 これらをA,Bとする。 Brusも同様に自分の看板から二つの連続する部分文字列を二つ切り出す。 これらをC,D…
問題 N個の都市がいくつかの道でつながっている。 それぞれの道がどの都市をつなぎ、どれくらいの長さであるかが与えられる。 Gogoはcities[i]で表される都市を全て訪問したい。 cities[i]の都市はこの順に訪問する必要がある。(ただし、別の都市の通り道と…
問題 NxMの方眼紙がある(縦線がN+1本、横線がM+1本) ここに、全ての頂点が方眼紙の交点であるようなひし形は何通り書くことができるか求めよ。 制約条件 N,M≦100
問題 文字列Tがmagic wordであるとは、 Tをi(0≦i<|T|)文字シフトした文字列がTに等しくなるようなiがちょうどK個あることを言う。 n個の文字列が与えられる。 0からn-1の数の順列p[i]について、この順に これらの文字列を結合した文字列をSとする。 Sがmagi…
問題 n個のボールの座標が与えられる。 ボールはそれぞれ、数直線上を左または右に、同じ速さで動いている。 ここにいくつかボールを足し、時間が経った後でのボールの座標が与えられる。 最初と最後のボールの対応の組み合わせとしてありうるものは何通りあ…
問題 以下のような自殺チェスを考える。 最初、白は盤上にn個のポーンをもち、それぞれの座標が与えられる 黒は1つのクイーンを持ち、その座標が与えられる 最初は白の手番 プレイヤーは取れる駒があったら必ず駒を取らなければならない。複数の駒を取れると…
問題 整数を要素とする二つの集合S1,S2があったとき、 S2がS1の倍数であるとは、S1のどんな要素xに対しても、 ある整数kおよびS2の要素yが存在して、y=x*kが成り立つことを言う。 Sを、A<=x<=BまたはC<=x<=Dを満たす整数の集合とする。 Sの倍数であるような…
問題 m個の点が与えられる。 これらの点の空でない部分集合Pで、Pに属する点を全て含み、Pに属さない点は全く含まないような、軸に平行なnxnの正方形が存在するようなPをn-squaredと呼ぶ。 nlow以上nhigh以下なsquaredな部分集合の数を求めよ。 制約条件 点…
問題 0または1からなるグリッドが与えられる。 この中に2x2以上の正方形で、軸に平行または、軸から45度傾いているものはいくつあるか。 ただし、他の1と(8方向のどれかで)隣接しているようなものは正方形とはみなさない。 制約条件 ひとつのテストケース…
問題 白、黒、赤、黄色の旗を一直線にL個以上R個以下並べる。 次の条件を満たす並べ方はいくつあるか、mod 10^9+7で求めよ。 同じ色が連続しない 白と黄色が並ばない 黒と赤が並ばない 黒白赤がこの順または、この逆順に並ばない ただし、左右反転させて重な…
問題 nxmのグリッドがある。 グリッドの一部のマスは障害物'#'で埋められている。それ以外のマスを、ブロック2個〜ブロック5個の塊(縦または横につながったもの。形は自由)で埋めることができるか。 できるなら埋め方の一例を出力し、そうでない場合は-1を…
問題 0と1からなるグリッドが与えられる。 このなかで、coolなcycleのうち、最も長さの長いものの長さを求めよ。 coolなcycleとは以下を満たすcycleである。 '1'からなるセルの集合である。 cycleに属する全ての'1'は、(辺を共有して)cylceの別の'1'ちょう…
問題 n個の部屋がm本の通路により結ばれている。 二人が次のように移動する。 最初それぞれa,bの部屋にいる。 部屋ごとに定められている確率p[i]で、その場にとどまり、1-p[i]の確率で、通路を等確率で一つ選び、隣の部屋に移動する 二人の移動先が同じ部屋…
問題 0と1からなる文字列に対して二人が次のようなゲームをする。 手番を交互にもつ 手番のプレイヤーは1つ文字を消す 残りが2文字になったら終了 先手は、残る文字列を最小化し、後手は残る文字列を最大化する ただし、与えられる文字列には'?'があり、 そ…
問題 8つの点が与えられる。 それらを4つの点からなる共通しない集合2つに分ける。 そのうち一方が正方形の4頂点になっていて、もう一方が長方形の4頂点になっている(正方形でもよい)ような分け方は存在するか。 存在するならYESおよびその分け方を一通り…
問題 数列が与えられる。この数列の項を一つだけ(必ず)変更して、ソートする。 変更前と変更後の数列の各項はすべて1以上10^9以下の整数である。 変更後にそれぞれの位置に来る項の最小値を求めよ。 制約条件 n≦10^5 数列の各項は1以上10^9以下
Result 444(1WA) / 936 / 1200 / (4WA) / - 36位 2036 -> 2140
問題 n個の三角形が与えられる。 それらの和集合からなる図形の周長を求めよ。 制約条件 n≦100 0<座標<10^5
問題 凸多角形および、点Pが与えられる。 凸多角形の頂点からなる三角形で、点Pを含むものはいくつあるか求めよ。 制約条件 多角形の角≦100000
問題 n個の惑星があり、それぞれの座標は(x[i],y[i],z[i])である。 最も遠い惑星への距離が最小になるような点の座標を求めよ。 制約条件 n≦100 座標の絶対値≦10^4
問題 3つの円が与えられる。それぞれの円に対して引いた2本の接線のなす角度が等しくなるような点の座標を求めよ。 複数ある場合は、角度が最大になる点を求め、存在しない場合は何も出力してはならない。 制約条件 座標の絶対値≦1000
問題 1x1,1x2,...,1xkのブロックが無限にある。 これらのブロックを、1xwのブロックの上に積み上げる。ただし、 座標が整数でなくてはならない 上のブロックは、下のブロックからはみ出てはならない 高さは最大でh(土台は高さに含めない) の条件を満たす必…
問題 lucky numberを、全ての桁が4か7であるような数とする。 n個の区間[ l[i],r[i] ]が与えられる。 一つの区間を、一回の操作で[l[i]+1,r[i]+1]または[l[i]-1,r[i]-1]に移動させることができる。 全体でk回の操作ができるとき、 全ての区間に含まれていて…
問題 hxwのグリッドがあり、各マスには'0'-'9'の数字が書かれている。 BP(block pointer)および、DP(direction pointer)とCP(choose pointer)という三つのポインタがある。 BPは現在のブロックを指している。 DPは現在の進む方向を指している。上下左右のい…
問題 n個の穴があり、穴はそれぞれa[i]のエネルギーがを持つ。 i番目の穴にボールを入れると、i+a[i]番目の穴へボールが飛ぶ。 飛んだ先の穴からまた連鎖的に同じことがおこる。 a[i]がnを超えると、その時点で連鎖は終了する。 このとき、次のm個のクエリに…
問題 9:00amに開き5:00pmに閉まる床屋がある。 客の来る時間のリストが与えられる。 床屋は、客が来たときに誰もいなければ、その客の髪を切り、 誰かがいれば、先に来た客全員の髪を切り終えてからその客の髪を切る。 一人の客の散髪には最低5分の時間がか…
問題 100x100のスライドパズルがある。 最初(emptyRow,emptyCol)のマスが空白である。 (carRow,carCol)のマスを(0,0)に移動させるのに最小で何手かかるか求めよ。 スライドパズルは、ピースと空白を入れ替える操作のみが出来て、 ピースを外に出したり、重ね…
問題 二人がN個の石の山を使って次のようなゲームをする。 二人は交互に手番をまわす。操作のできなくなったプレイヤーの負けである。 手番のプレイヤーは1以上K個以下の石を取る 石を取り終えた後、先手は山の石の数が素数でなくてはならず、後手は石の数が…
ゴミすぎるー Result 220.07 / Opened / Unopened 0チャレンジ 117位 2034 -> 2036