【AtCoder】私はDP(動的計画法)が苦手だ.

AtCoder
この記事は約2分で読めます。

先日,abc178に参加しました.

【AtCoder 活動記録】ABC178に参加して.~感想と解法~【python】
久しぶりの日曜開催ということで,4大会振りに参戦した.ほぼ毎朝(たまにサボったが),Atcoderの過去問を解いてきたので,多少はレベルアップしているかなと思いつつ,21時を迎えた.ちなみにコンテスト参加は10回未満,色は...

結果から言うと,A~C問題までがAC,D問題を解答途中で終了しました.

$ S \leq 2000$ の数字を見たとき,「O($ s ^ 2 $) で押さえ込むのか.何かアルゴリズム使うのかな」とまでは考えついたのですが,結局解けなかった.

解法を見てみると,「DP(動的計画法)使えば解けますよ〜」と書いてあり,「そうか,確かに」と納得したのも束の間.

「実装どうやるんだっけ???」

大学の講義とかで習いはしたが,久しく実装なんてやってなかった(言い訳).なんか最小化問題とかナップザック問題とか解いた覚えはあるのだが,まあやり方忘れた.

D問題の解答を見ても,なんかDP使えば解けるって書いてあるだけで,詳細な解説までは載っていない.動画では解説してくれているけど,イマイチ理解できない.

これはヤバイ.DP勉強しないと

というわけで,しばらくDP(動的計画法)を勉強することにしました.

これからの勉強方法

とりあえず以下の記事を参考に進めていきます.

動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita
0. はじめに: 非常に素敵な DP の入門コンテンツ 待ちに待ったコンテストの到来です!!!!! DP (動的計画法) はアルゴリズムの登竜門というべき難所ですが、いくつか問題を解いて行くとパターンのようなものが見えて来ます...
典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita
はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ば...

まずは「緑」目指して頑張ろう.

おーよしの紹介
院卒Webエンジニアマン

「プログラミング」や「開発技術」,「大学院の苦労話」について情報発信してます.これからのIT時代を生き抜くため,自分のスキルを磨き続けます.将来は起業できたらいいなという思いがあります.

oyoshiをフォローする
スポンサーリンク
AtCoder アルゴリズム プログラミング 雑談
スポンサーリンク
にほんブログ村に参加中(^~^)
PVアクセスランキング にほんブログ村
おーよしぶろぐ

コメント

タイトルとURLをコピーしました