PKU
DP(動的計画法)のコツが分かってきた。 より小さいサイズの場合の最適解を適切に求めて置いて、ソレをより大きいサイズの問題の解の一部として利用する。 2030 - The Secret Number DPの典型例。図上だと、右下から順にその場での最適解を求めていく。 http:…
練習量が足りない……とりあえず、高速に問題を解くためのメモ。 setは追加にinsertメソッドを利用する。集合なので、重複要素は登録されない。 要素の比較にはfindメソッドを利用する。見つからない場合、イテレータ終端が返る。 要素数はsizeメソッドで取得…
入力が嫌らしいコンテストの問題。 Judging Olympia http://acm.pku.edu.cn/JudgeOnline/problem?id=3507 Rotation Rings http://acm.pku.edu.cn/JudgeOnline/problem?id=3509 A Tale from the Dark Side of the Moon http://acm.pku.edu.cn/JudgeOnline/pro…
PKU、一日1問。勉強会の課題も出てるし、がんばらないとなぁ。
DPで解く問題Adventures in Moving - Part IV http://acm.pku.edu.cn/JudgeOnline/problem?id=2465 Atomic Car Race http://acm.pku.edu.cn/JudgeOnline/problem?id=2744 何となくDPは分かってきたけど……まだコツを掴みかねてる感じ。
PKUには、よく似た問題もあれば、なんと全く同じ問題もある。 今回教えてもらったのはこいつ。 3003 -- Spiderman’s workout http://acm.pku.edu.cn/JudgeOnline/problem?id=3003 2397 -- Spiderman http://acm.pku.edu.cn/JudgeOnline/problem?id=2397 2397…
3126 -- Prime Path http://acm.pku.edu.cn/JudgeOnline/problem?id=3126 Prime minister(日本で言う総理大臣)が、prime number(素数)なルーム番号を欲しがる問題。以下、問題の概要と意訳。 4桁の素数(例えば1033, リーディングゼロは含まない)がPrime Mini…
時間が足りなかったので、Hash集合クラスを使いたいと思った。 C++で調べて見た限り、の非標準STLがstdextネームスペース内にあると分かった。 実行すると、案の上コンパイルエラー出された。 VS2005でやってるからG++と違うのは分かるけど……何かあるのかな…
http://acm.pku.edu.cn/JudgeOnline/problem?id=2403ある単語には価値があり、文章中にその単語が何度出てくるかをカウントして文章の価値を求める問題。非常に簡単に解けました。 ソース・解法が知りたい方は以下で。
