競技プログラマのための DP 入門 - J * A * P * L * Jこの記事は Competitive Programming Advent Calendar 2014 - PARTAKE の 13 日目の記事です。 まとめ Q. この記事を読めば動的計画法が分かるようになりますか？ A. なりません。 はじめに プログラミングコンテストの問題の題材として DDR (DanceDanceRevolution) が出題されることは少なくありません *1。しかし、活動時間の全てをオンラインジャッジにつぎ込む生活では、DDR を想像することができず、問題の理解に困ってしまうこともあるでしょう。一分一秒を争うこの世界では、致命傷となりかねません。本記事は、そのような状況への対策として執筆されています。*2 問題 あるゲームには図 1 のような 8 つの矢印パネルがついた台があり、図 2 のような譜面が流れてきます。このゲームの遊び方は単純で、矢印が判定ｴｧﾘｱに重
