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)

凸共役と集中不等式

 凸解析のツールの一つとして凸共役という概念があります. $I\subseteq \mathbb{R}$上で定義された実関数$f$の凸共役とは \[ f^*(a) = \sup_{x\in I}\{ax - f(x)\} \] で定義されます. 通常は$I=\mathbb{R}$...

  • ランダムグラフ入門
    0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます.  1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ...
  • 駆け足で学ぶ「グラフマイナー定理」
    0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで...
  • 高速な全点対最短経路アルゴリズム
    1. 全点対最短経路問題の計算量の外観 　グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと...