Pの競プロ記

競技プログラミングに関することを書きます。

2012-10-10から1日間の記事一覧

AOJ 1092 Make KND So Fat

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1092 解法 動的計画法(DP)で解くことができます。この問題では2回動的計画法をします。(1回の動的計画法だけでも解を求めることはできるかもしれませんが、私は2回に分け…

AOJ 1091 KND is So Sexy

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1091 解法 軽めの幾何問題です。ヘロンの公式を覚えていれば簡単に解くことができます。 三角形ACDと三角形BCEは二等辺三角形になるときに最大の面積を持ちます。 ソー…

EvenRoute (SRM538 div2 medium)

解法・感想など 若干嘘解法っぽい気もするが通りました。とりあえず入力を与えられた順番に道をたどっていきます。 そこでwantedParityと値が合えばそこで"CAN"を返すことができる。 そうでない場合、最後に見た点からそれ以外の点まですべて距離を見て、奇…

LeftOrRight (SRM538 div2 easy)

解法・感想など 連続する?の数を1つにまとめて深さ優先探索で解きました。最悪ケースは、 R?L?R?L?R?L?R?L?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L? で2^25ありますがこれでも時間内に解くことができます。ちなみにあとから他の記事を拝見しましたが、 ?にL…