先日，abc178に参加しました．
【AtCoder 活動記録】ABC178に参加して．~感想と解法~【python】
久しぶりの日曜開催ということで，4大会振りに参戦した．ほぼ毎朝(たまにサボったが)，Atcoderの過去問を解いてきたので，多少はレベルアップしているかなと思いつつ，21時を迎えた．ちなみにコンテスト参加は10回未満，色は灰です(馬鹿にして...続きはコチラ
www.oyoshi-devlog.com
2020.09.13
結果から言うと，A~C問題までがAC，D問題を解答途中で終了しました．
$ S \leq 2000$ の数字を見たとき，「O($ s ^ 2 $) で押さえ込むのか．何かアルゴリズム使うのかな」とまでは考えついたのですが，結局解けなかった．
解法を見てみると，「DP(動的計画法)使えば解けますよ〜」と書いてあり，「そうか，確かに」と納得したのも束の間．
「実装どうやるんだっけ？？？」
大学の講義とかで習いはしたが，久しく実装なんてやってなかった(言い訳)．なんか最小化問題とかナップザック問題とか解いた覚えはあるのだが，まあやり方忘れた．
D問題の解答を見ても，なんかDP使えば解けるって書いてあるだけで，詳細な解説までは載っていない．動画では解説してくれているけど，イマイチ理解できない．
これはヤバイ．DP勉強しないと
というわけで，しばらくDP(動的計画法)を勉強することにしました．
これからの勉強方法
とりあえず以下の記事を参考に進めていきます．
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita
0. はじめに: 非常に素敵な DP の入門コンテンツ待ちに待ったコンテストの到来です！！！！！DP (動的計画法) はアルゴリズムの登竜門というべき難所ですが、いくつか問題を解いて行くとパターンのようなものが見えて来ます...
qiita.com
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
はじめに --- DP は役に立つはじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれて...
qiita.com
まずは「緑」目指して頑張ろう．
コメント