DP
水色の問題.桁DPの立て方をしっかり学べてよい. atcoder.jp
青色の問題.Atcoder版蟻本に掲載されているやつです.何重のマトリョーシカを作れるか. atcoder.jp 問題の説明 箱が個あり,それらを入れ子にします.ある箱が,それより縦・横ともに大きいサイズの箱にのみ入れられるとしたとき,最大で何重の入れ子が作成可能か…
コンテストの名前の通りDPの問題.どのようにDPテーブルを更新するかが少し特徴的なのでブログにまとめておく.新規性は1ミリもありません. atcoder.jp 問題の説明 以下の正整数であり,十進表記したときの各桁の数の和がの倍数であるものの個数を[tex: mod 1,0…
DPの問題.前日の情報をどうするか,そこがカギとなります. atcoder.jp 問題の説明 温度条件が度の下で日服を選んだ場合の派手さの差の絶対値の合計の最大値を求めよ. 条件 考えた事 派手さの差の絶対値の合計を考える.つまり前の情報を遷移させる必然性を伺わ…
DPの問題.ナップサック問題+α.スクリーンショットの重要度ってなんやねん. atcoder.jp 問題の説明 枚数が枚,幅がに収まる条件の下で画像を選ぶときの重要度の合計の最大値を求めよ. 条件 考えた事 枚数制限がない場合,これは典型的なナップサック問題と呼ば…
いよいよDP.最初は優しめの問題から. atcoder.jp 問題の説明 高橋君が回または段のジャンプを行います.回のジャンプの後ににいる可能性があるか答えなさい. 条件 入力は全て整数. 考えた事 まず,DPとは何をする手法なのか.端的に言えば値を記憶する配列を作…