mayoko’s diary

プロコンとかいろいろ。

2016-05-09から1日間の記事一覧

AOJ 1132 Circle and Points

AOJ

問題 Circle and Points | Aizu Online Judge 解法 ある円が答えだったとします。この円を少し動かしても, この円が最適であることに変わりはありません。この円を適当に動かして, 初めてある点とぶつかったとき, 円をこの点からはみ出さないように動かすと,…

AOJ VolumeACPC2015Day1 D : Checkered Pattern

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2015Day1&pid=D 解法 適当に実験すると答えがわかります。自明っぽいところから攻めて行きます。 まず, g = gcd(h, w) とすると, (h/g, w/g) の長方形を g 回同じように繰り返している…

AOJ 2200: Mr. Rito Post Office

AOJ

問題 Mr. Rito Post Office | Aizu Online Judge 解法 普通に dp しようとすると dp[次目指す場所][今いる位置][船の位置] みたいになりそうですがこれだと状態数多すぎで間に合いません(というか dfs だとループになりそう)。そこで, dp の遷移を限定するこ…