2015年4月30日木曜日

AOJ 1194:バンパイア

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1194&lang=jp

解法

二分探索。
ビルのx座標が整数値でしかも絶対値が20以下なので
H[i] = 区間[i,i+1]のビルの最大値
とおいてt秒あとの区間[a,a+1]の太陽の高さを求めてかぶってるかどうかを判定すれば良い。
時刻:
ラベル:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)

「入力」と「インスタンス」の使い分け

問題に対するアルゴリズムの計算量を議論する際に「入力」「インスタンス」という言葉が登場する。これらは、アルゴリズムが読み込む文字列という意味では、両者ともに同じ役割を果たすため、特に気にせず同じ意味で用いる人が多いと思う。しかし、実は両者は文脈によっては明確に区別されるべき概念で...

  • アルゴリズムの理論研究の最高峰とは?
    競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介し...
  • ざっくり解説: 焼きなまし法はなぜうまくいくのか？
    概要 焼きなまし法 は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられていま...
  • ランダムグラフ入門
    0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます.  1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ...