AOJ

AOJ 2426 Treasure Hunt

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426 個の点と 個の長方形が与えられる。各長方形の辺上または内部にある点の数を求めよ。 解法 座標圧縮・累積和の前計算といった工夫をしないとTLEする。 template<typename T> inline void compless(v</typename>…

AOJ 2428 Lost Number

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2428 穴あきの数式が与えられる。穴に適当な文字を入れて計算結果を最大化せよ。 解法 構文解析はエラーが起こったらメッセージ付きの例外を投げる実装にするのが一番実装もデバッグも楽だと…

AOJ 2431 House Moving

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2431 1 から までの整数を並び替えた列 が与えられる。 をコスト で好きな場所に移動できる。昇順にソートするのに必要なコストの最小値を求めよ。 解法 移動させるときはまとめて移動させれ…

AOJ 2429 marukaite

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429 のグリッドがある。各マスは初期状態でoが書かれているか書かれていないかのどちらか一方である。各マスに対して、空白のときに書くコストと既にあるoを消すコストが与えられる。同じ行…

AOJ 2425 A Holiday of Miss Brute Force

問題 変な六角座標上での最短路問題。移動にかかるコストが時間によって変わる。(座標, 時間, 無視した回数)を状態に持ってダイクストラ法で探索した。実装が面倒。 ソースコード ll const inf = 1<<28; double const pi = acos(-1); int sx,sy,gx,gy; int n…

AOJ 1264 Concert Hall Scheduling

追記 : タグが間違っていたのを修正 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1246 コンサートホールが2つあリ、 日から 日までの期間を料金 で使用したいという申し込みが 個来ている。期間が被らないように2つのコンサートホールに…

AOJ 1283 Most Distant Point from the Sea

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1283 多角形の内部の点で、辺との距離の最小値が最大になる点を求めよ。 解法 初めは他の人と同じように想定解の二分探索でやっていたが、謎のWAが解決できなかったから次のような山登り法?…

AOJ 1244 Molecular Formula

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1244 元素記号と原子量の対応表と化学式が与えられる.化学式が何molか求める. 未知の元素が含まれていたら "UNKNOWN" と出力する.

AOJ 1188 Hierarchical Democracy (改善版)

前回 : TLEにはなりませんでしたが,頻繁にstringをやりとりしている点など無駄が多いのでそのうちやりなおします. ということでやり直した.