はてなブックマーク

はじめに 最近、実生活で競技プログラミングが役に立ちました。 趣味の一環で長方形のQRコードであるrMQRコードを生成するPythonパッケージを作成しています。その中で「ビット列が最も短くなるようにデータをエンコードする」という処理に動的計画法を用いました。大学時代に競技プログラミングをやっていた身としては「競プロが役に立った！」と嬉しかったので、実例として共有したくてこの記事を書いています。動的計画法のDPテーブルの定義から遷移のしかた、解の復元までを図や実装とともに説明しています。動的計画法自体は説明していません。実装の全体はこちらでご覧いただけます。 この記事に出てくるrMQRコードの仕様に関する記述はISO規格1に基づいています。最適なエンコードを求めるアルゴリズム自体は仕様に含まれるものではなく、オリジナルのものになります。 ※QRコードは(株)デンソーウェーブの登録商標です。