実装問題
問題 横一列にn台の駐車スペースがあり、左から順に1, ..., nと名前がついている。 ここにm個の車の到着または出発のクエリが来るので処理せよ。 車は以下のアルゴリズムで駐車場所を選ぶ。 全ての空きスペースの中で、一番近くにある他の車までの距離が最大…
問題 nxnのグリッドがあり(1, 1)から(n, n)へ、上または右に移動することを繰り返して進む。 グリッドのうちm個には障害物があり、そのマスへは入れない。 (1, 1)から(n, n)へ進むことはできるか。 制約条件 n≦10^9 m≦10^5
問題 n頂点からなる無向木が与えられる。 各頂点には重みwiがついている。重みの初期値が与えられる。 この木に対して次のようなクエリがq個来るので、答えよ。 t a b c t = 1のとき、木の頂点aから頂点bへのパス上にある頂点全ての重みをcに変更する。 t = …
問題 hxwのグリッドがある。Xのマスは床で、そこを歩くことができる。 .のマスは床がなくて歩くことができない。 グリッドのh-1行目は全てXで、ここからスタートしてゴールのマスへ移動する。 Xの上ならば左右には自由に動けて、同じ列にあるXには、はしごを…
問題 nxnのグリッドがあり、(x, y)の点がt = 0において色がついている。 1秒ごとに、色のついているマスと辺を共有している色のついてないマスに色がつく。 全体でc個以上のマスに色がつくのにかかる時間を求めよ。 制約条件 n≦10^9
問題 n行m列のグリッドが与えられる。各マスは'.'または'#'である。 #のマスが連結であるとは、「どの二つの#のマスも、辺を共有するような'#'を経由してたどり着ける」ことを言う。 #が一つだけのグリッド、#が一つもないグリッドは連結であることに注意す…
問題 2レーンのプールでn人の人が泳ぐ。 それぞれのレーンは往路、復路の一方通行であり、レーンの幅は狭いため、 途中で泳いでる人を抜かすことはできない。 i番目の人は、レーンを片道泳ぐのにt[i]の時間がかかる。c[i]往復泳ぐとプールから出る。 前に、…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp) 制約条件 n≦100
問題 n個の土地が円周上に並んでいる。 それぞれの土地の高さはheight[i]である。 この土地に対して次のような操作をT回行う。 heightが正であるような土地i全てについて、height[i]を1減らし、height[(i + 1) % n]を1増やす。 この操作は全て同時に行われる…
問題 n x mのグリッドで表される地図が与えられる。 'x'のマスは陸であり、'.'のマスは海である。 島とは、'x'のマスが上下左右斜めにつながった塊であり、 海は上下左右のマスとつながっている。 島のlevelとは、島に対して以下のように定義される量である…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp) 制約条件 クエリの数≦200000
問題 バレーボールのマッチは、3セットを先に取ったほうの勝ちである。 ゲームの結果、合計で wonMatchesのマッチで勝ち、 lostMatchesのマッチで負け、 取ったセットの数を合計すると、wonSetsになり、 取られたセットの数を合計するとlostSetsになるとき、…
問題 単語のリストが与えられる。 指定されたフォーマットの索引を作れ。 二段組で、左側に先頭の文字がA-Mのリストを、右側に先頭の文字がそれ以降のリストを書く。 左右の段組の間は2つのスペースをで区切る。(その文字で始まる単語が存在するような)各…
問題 米国式では日付は月/日と書き、英国式では日付は日/月と書く。 日付のリストが与えられるが、書式がどちらで書かれているか解らない。 日付は、早い順に並んでいるものとするとき、日付を全て米国式で記し、つなげた文字列を返せ。 候補が複数ある場合…
問題 n人がペイント球を投げる遊びをしている。 それぞれの人が所属するチームが与えられる。 また、誰が誰にボールを当てたかという情報も与えられる。 AがBにボールを当てたとき、AとBが違うチームならAに1点、Bに-1点が加わる。 AとBが同じチームなら、A…
問題 整数nが与えられる。 整数nに非負の整数を加えて、和の各桁の数字のうちどれか一つ以上がkになるようにしたい。 最小でいくつの数を加えればよいか、求めよ。 制約条件 nの桁数≦50 k≦9
問題 上空からスケートリンクを捉えた写真が与えられる。 この中から、チームの番号がkの人のリストを作成したい。 写真の連続する(上下または左右に隣接する、色が同じである)領域で、色がkであり、面積がthreshold以上の領域をチーム番号がkの人と認識す…
問題 タイプミスに対するペナルティを、キーボード上での最短距離と定義する。 与えられた文字列に対して、長さが等しく、ペナルティの和が最小になるような"日付"を求めよ。 候補が複数ある場合、もっとも早い日付を答えよ。 "日付"は、月 日の形式で表され…
問題 列車の線路がグリッドにより与えられる。 '|'のマスは縦向きの線路を表し、上下から進入して、上下に出ることができる。 '-'のマスは横向きの線路を表し、左右から進入して、左右に出ることができる。 '+'のマスは交差点の線路を表し、どの方向からも進…
問題 一辺が2^iの立方体がcubes[i]個ずつある。 これを使ってheight x width x lengthの直方体を埋めたい。 直方体は隙間なく立方体に埋められている必要があり、立方体が直方体からはみ出たり、立方体同士が重なったりしてはならない。 直方体を埋めるのに…
問題 tableの列はattributeと呼ばれる。 行はentryと呼ばれる。 attributeの部分集合で、どのentryのペアについても、そのattributeのentryのうち異なるものが少なくとも一つあるものをsuper keyと呼ぶ。 super keyのうち、他のsuper keyを部分集合として含…
問題 音階には12種類があり、それぞれの名前は、 A, A#, B, C, C#, D, D#, E, F, F#, G, G# である。 G#の一つ上の音はAである。12の倍数個だけ離れた音は同じ音階である。 今、何も抑えないとそれぞれstrings[i]の音がなるギターがある。 これを、フレット…
問題 n人の人が、m人の候補に対して投票して、一人の代表を決定する。 投票は次のルールで行われる。最初、n人はそれぞれm人に対して順位をつける。 残っている人が二人以上の間、 n人は残っている人の中でつけた順位が最も高い人に投票する。 過半数の票を…
問題 各マスが#または.からなる画像が与えられる。 画像は以下の性質を満たしている。 #のマスのそれぞれの連結成分について(ただし、二つのマスが連結しているとは辺を共有しているマスをたどって一方のマスからもう一方のマスへ移動できることをいう)、 …
問題 二つの数x,yが与えられる。 x,yをちょうど二度ずつ含み、"+","-","*"の演算子の演算子のみを含んでいて、 値がvalであるような式はいくつあるか求めよ。ただし、-を単項演算子のマイナスとして使うことはできない。 演算子に優先順位はなく、先頭から順…
問題 36進法の数がn個与えられる。 これらの数から、ちょうどk種類のアルファベットを全て'Z'に置換する。 置換後の全ての数の和の最大値を36進法で求めよ。 制約条件 n≦50 それぞれの数の桁数≦50
問題 図のような床がある。 (1x5の板が縦に5枚並べた正方形Aと、横に5枚並べた並べた正方形がBが、平面上に ABABAB BABABA ABABAB… のように無限並んでいる)この床のx1,y1,x2,y2の長方形の領域を作りたい。 1x5の板はいくつ必要か。 板は好きなように切断…
問題 0または1からなるグリッドが与えられる。 この中に2x2以上の正方形で、軸に平行または、軸から45度傾いているものはいくつあるか。 ただし、他の1と(8方向のどれかで)隣接しているようなものは正方形とはみなさない。 制約条件 ひとつのテストケース…
問題 0と1からなるグリッドが与えられる。 このなかで、coolなcycleのうち、最も長さの長いものの長さを求めよ。 coolなcycleとは以下を満たすcycleである。 '1'からなるセルの集合である。 cycleに属する全ての'1'は、(辺を共有して)cylceの別の'1'ちょう…
問題 hxwのグリッドがあり、各マスには'0'-'9'の数字が書かれている。 BP(block pointer)および、DP(direction pointer)とCP(choose pointer)という三つのポインタがある。 BPは現在のブロックを指している。 DPは現在の進む方向を指している。上下左右のい…