PKUは、北京大学がストックしているプログラミングコンテストの過去問題集である。
世界中で開催されたプログラミングコンテストの過去問がのっているのでなかなか勉強になる。
しかも、PKUを問題の種類別に（探索/動的計画/貪欲法など）カテゴライズしてくれているサイトがあったり、最重要問題をピックアップしてくれていたりするサイトがあるので、自分の弱点を重点的に補強することが可能である。
問題自体は、登録なしでも見れるが、submitしてソースコードの正当性を確認するためには、PKUのサイトに登録しなければならない。。（まーでも、ちょっとした情報入れるだけなんで30秒くらいで出来ます。）
使ってみた感想は、Google Code Jamに似ている気がする。フォーマッティングされたinputを読み取り、outputを指定のフォーマットで出力する。。
とりあえず、今日は、最近勉強しているDPを解いてみた。
問題は、これ。
比較的簡単な問題だった。。
普通にコーディングすると最悪計算量がO(2^(n+m))になってしまう典型的なクラスNPの問題。。
ちょっと工夫すれば、O(n*m)で解けます。。。（ここで、n, mはそれぞれ文字列A,Bの長さとする。）
今回は、｢PKUってのがありますよ｣って紹介だったので、ソースは掲載しませんが（手抜きですいません。。）、2次元のマトリックスが頭の中に浮かんで、左下からスタートして、上に行くか、右に行くか、を逐次選びながら進んで、一番右上にゴールしたときに・・・・みたいなイメージが頭の中に浮かぶといいです。。
DP知らない人からすると、何で文字列の問題が、経路問題みたいになるんだろう？？？って感じだと思いますが。。そういう人は、是非ともDPの勉強をお勧めします。。
お勧めのサイトはこれ。
0 件のコメント:
コメントを投稿