実装問題

Codeforces 219(#135 Div2 only) E. Parking Lot

問題 横一列にn台の駐車スペースがあり、左から順に1, ..., nと名前がついている。 ここにm個の車の到着または出発のクエリが来るので処理せよ。 車は以下のアルゴリズムで駐車場所を選ぶ。 全ての空きスペースの中で、一番近くにある他の車までの距離が最大…

Codeforces #225(383 Div1) B. Volcanoes

問題 nxnのグリッドがあり(1, 1)から(n, n)へ、上または右に移動することを繰り返して進む。 グリッドのうちm個には障害物があり、そのマスへは入れない。 (1, 1)から(n, n)へ進むことはできるか。 制約条件 n≦10^9 m≦10^5

AOJ 2450 Do use segment tree + Heavy Light Decompositionまとめ

問題 n頂点からなる無向木が与えられる。 各頂点には重みwiがついている。重みの初期値が与えられる。 この木に対して次のようなクエリがq個来るので、答えよ。 t a b c t = 1のとき、木の頂点aから頂点bへのパス上にある頂点全ての重みをcに変更する。 t = …

TopCoder SRM 576 Div1 Easy ArcadeManao

問題 hxwのグリッドがある。Xのマスは床で、そこを歩くことができる。 .のマスは床がなくて歩くことができない。 グリッドのh-1行目は全てXで、ここからスタートしてゴールのマスへ移動する。 Xの上ならば左右には自由に動けて、同じ列にあるXには、はしごを…

Codeforces 255D Mr. Bender and Square

問題 nxnのグリッドがあり、(x, y)の点がt = 0において色がついている。 1秒ごとに、色のついているマスと辺を共有している色のついてないマスに色がつく。 全体でc個以上のマスに色がつくのにかかる時間を求めよ。 制約条件 n≦10^9

Codeforces 193A Cutting Figure

問題 n行m列のグリッドが与えられる。各マスは'.'または'#'である。 #のマスが連結であるとは、「どの二つの#のマスも、辺を共有するような'#'を経由してたどり着ける」ことを言う。 #が一つだけのグリッド、#が一つもないグリッドは連結であることに注意す…

AOJ 1297 Swimming Jam

問題 2レーンのプールでn人の人が泳ぐ。 それぞれのレーンは往路、復路の一方通行であり、レーンの幅は狭いため、 途中で泳いでる人を抜かすことはできない。 i番目の人は、レーンを片道泳ぐのにt[i]の時間がかかる。c[i]往復泳ぐとプールから出る。 前に、…

AOJ 1181 Biased Dice

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp) 制約条件 n≦100

TCO2012 Round2C Hard FlattenOut

問題 n個の土地が円周上に並んでいる。 それぞれの土地の高さはheight[i]である。 この土地に対して次のような操作をT回行う。 heightが正であるような土地i全てについて、height[i]を1減らし、height[(i + 1) % n]を1増やす。 この操作は全て同時に行われる…

TopCoder SRM 341 Div1 Medium LandAndSea

問題 n x mのグリッドで表される地図が与えられる。 'x'のマスは陸であり、'.'のマスは海である。 島とは、'x'のマスが上下左右斜めにつながった塊であり、 海は上下左右のマスとつながっている。 島のlevelとは、島に対して以下のように定義される量である…

AOJ 1070 FIMO sequence

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp) 制約条件 クエリの数≦200000

TopCoder SRM 344 Div1 Easy VolleyballTournament

問題 バレーボールのマッチは、3セットを先に取ったほうの勝ちである。 ゲームの結果、合計で wonMatchesのマッチで勝ち、 lostMatchesのマッチで負け、 取ったセットの数を合計すると、wonSetsになり、 取られたセットの数を合計するとlostSetsになるとき、…

TopCoder SRM 353 Div1 Easy Glossary

問題 単語のリストが与えられる。 指定されたフォーマットの索引を作れ。 二段組で、左側に先頭の文字がA-Mのリストを、右側に先頭の文字がそれ以降のリストを書く。 左右の段組の間は2つのスペースをで区切る。(その文字で始まる単語が存在するような)各…

TopCoder SRM 354 Div1 Easy DateFormat

問題 米国式では日付は月/日と書き、英国式では日付は日/月と書く。 日付のリストが与えられるが、書式がどちらで書かれているか解らない。 日付は、早い順に並んでいるものとするとき、日付を全て米国式で記し、つなげた文字列を返せ。 候補が複数ある場合…

TopCoder SRM 364 Div1 Easy Paintball

問題 n人がペイント球を投げる遊びをしている。 それぞれの人が所属するチームが与えられる。 また、誰が誰にボールを当てたかという情報も与えられる。 AがBにボールを当てたとき、AとBが違うチームならAに1点、Bに-1点が加わる。 AとBが同じチームなら、A…

TopCoder SRM 367 Div1 Easy ObtainingDigitK

問題 整数nが与えられる。 整数nに非負の整数を加えて、和の各桁の数字のうちどれか一つ以上がkになるようにしたい。 最小でいくつの数を加えればよいか、求めよ。 制約条件 nの桁数≦50 k≦9

TopCoder SRM 374 Div1 Medium PlayerExtraction

問題 上空からスケートリンクを捉えた写真が与えられる。 この中から、チームの番号がkの人のリストを作成したい。 写真の連続する(上下または左右に隣接する、色が同じである)領域で、色がkであり、面積がthreshold以上の領域をチーム番号がkの人と認識す…

TopCoder SRM 375 Div1 Medium DateFieldCorrection

問題 タイプミスに対するペナルティを、キーボード上での最短距離と定義する。 与えられた文字列に対して、長さが等しく、ペナルティの和が最小になるような"日付"を求めよ。 候補が複数ある場合、もっとも早い日付を答えよ。 "日付"は、月 日の形式で表され…

TopCoder SRM 376 Div1 Easy Trainyard

問題 列車の線路がグリッドにより与えられる。 '|'のマスは縦向きの線路を表し、上下から進入して、上下に出ることができる。 '-'のマスは横向きの線路を表し、左右から進入して、左右に出ることができる。 '+'のマスは交差点の線路を表し、どの方向からも進…

TopCoder SRM 379 Div1 Medium FillBox

問題 一辺が2^iの立方体がcubes[i]個ずつある。 これを使ってheight x width x lengthの直方体を埋めたい。 直方体は隙間なく立方体に埋められている必要があり、立方体が直方体からはみ出たり、立方体同士が重なったりしてはならない。 直方体を埋めるのに…

TopCoder SRM 386 DIv1 Easy CandidateKeys

問題 tableの列はattributeと呼ばれる。 行はentryと呼ばれる。 attributeの部分集合で、どのentryのペアについても、そのattributeのentryのうち異なるものが少なくとも一つあるものをsuper keyと呼ぶ。 super keyのうち、他のsuper keyを部分集合として含…

TopCoder SRM 389 Div1 Medium GuitarChords

問題 音階には12種類があり、それぞれの名前は、 A, A#, B, C, C#, D, D#, E, F, F#, G, G# である。 G#の一つ上の音はAである。12の倍数個だけ離れた音は同じ音階である。 今、何も抑えないとそれぞれstrings[i]の音がなるギターがある。 これを、フレット…

TopCoder SRM 393 Div1 Easy InstantRunoffVoting

問題 n人の人が、m人の候補に対して投票して、一人の代表を決定する。 投票は次のルールで行われる。最初、n人はそれぞれm人に対して順位をつける。 残っている人が二人以上の間、 n人は残っている人の中でつけた順位が最も高い人に投票する。 過半数の票を…

TopCoder SRM 396 Div1 Medium FixImage

問題 各マスが#または.からなる画像が与えられる。 画像は以下の性質を満たしている。 #のマスのそれぞれの連結成分について(ただし、二つのマスが連結しているとは辺を共有しているマスをたどって一方のマスからもう一方のマスへ移動できることをいう)、 …

TopCoder SRM 398 Div1 Easy CountExpressions

問題 二つの数x,yが与えられる。 x,yをちょうど二度ずつ含み、"+","-","*"の演算子の演算子のみを含んでいて、 値がvalであるような式はいくつあるか求めよ。ただし、-を単項演算子のマイナスとして使うことはできない。 演算子に優先順位はなく、先頭から順…

TopCoder SRM 434 Div1 Medium maximizeSum

問題 36進法の数がn個与えられる。 これらの数から、ちょうどk種類のアルファベットを全て'Z'に置換する。 置換後の全ての数の和の最大値を36進法で求めよ。 制約条件 n≦50 それぞれの数の桁数≦50

TopCoder SRM 442 Div1 Medium BedroomFloor

問題 図のような床がある。 (1x5の板が縦に5枚並べた正方形Aと、横に5枚並べた並べた正方形がBが、平面上に ABABAB BABABA ABABAB… のように無限並んでいる)この床のx1,y1,x2,y2の長方形の領域を作りたい。 1x5の板はいくつ必要か。 板は好きなように切断…

Codeforces 11 C. How Many Squares?

問題 0または1からなるグリッドが与えられる。 この中に2x2以上の正方形で、軸に平行または、軸から45度傾いているものはいくつあるか。 ただし、他の1と(8方向のどれかで)隣接しているようなものは正方形とはみなさない。 制約条件 ひとつのテストケース…

Codeforces 135 D. Cycle

問題 0と1からなるグリッドが与えられる。 このなかで、coolなcycleのうち、最も長さの長いものの長さを求めよ。 coolなcycleとは以下を満たすcycleである。 '1'からなるセルの集合である。 cycleに属する全ての'1'は、(辺を共有して)cylceの別の'1'ちょう…

Codeforces 132 B. Piet

問題 hxwのグリッドがあり、各マスには'0'-'9'の数字が書かれている。 BP(block pointer)および、DP(direction pointer)とCP(choose pointer)という三つのポインタがある。 BPは現在のブロックを指している。 DPは現在の進む方向を指している。上下左右のい…