ナップサック問題

はじめに 動的計画法 ナップサック問題 例題 考え方 実装例 おわりに 参考 はじめに こんにちは．talosです．今回はナップサック問題を例題に，動的計画法を説明します．競技プログラミングとかでもよく使われるので，これから挑戦しようという人は必見です． 動的計画法 動的計画法（DP：Dynamic Programming）は問題を部分問題に分割し，それらを解くことで最終的な解を求める方法です．似たような方法に分割統治法がありますが，これとの違いは部分問題を解いた結果を保存しておくことです．これによって，分割統治法でよくある同じ部分問題を何度も解いてしまうということを避けることができます．言葉…

基本情報技術者試験を受けて多分（？）受かりました。僕は過去問を周回したりする、いわゆる試験勉強みたいなのが苦手です。 なので僕みたいな怠惰な人が日頃からダラダラ本を読むことで過去問をあまり解かずに受かる方法を残しておこうと思います。どちらかというと、普段ダラダラ読んでる本の中から試験に役立つ本をリストアップするというのが正しいかもしれません。目次 自己紹介 基本情報技術者試験 試験範囲について 勉強方法について 受験 おわり！ 自己紹介 都内某所でプログラマとして働いています。 数年前までAtCoderをやっていました。 会社ではAWSのインフラ色々いじったり、PHPの異常レガシーコードをしば…

MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）に参加したので、問題を解いた過程を記録してみた。 問題 サンプルをベタ移植 すべての予約を縦割りで割り当てる しばらくコスト算出の実装に精を出す コストについて考えた イベントスペースを長方形のセクションに分割する セクションの分け方を実験した 複数ナップサック問題？ 余裕のあるところに詰めてもらう（雑実装の解消） システムテスト やりたかったこと 問題 atcoder.jp W x W のグリッドで表現されるイベントホールがある D 日分の予約群があり、日毎に N 件の予約があ…

問題 想定配点 コメント Simple Math(Returned) 300 簡単な算数枠で作っていたら思っていたよりもペナ率が高かったり、難しかったりしたらしいです ARC-A にありそう Mean Median Construction 300 序盤のボス問(?)枠 かなり難しそうな見た目をしてたので、飛ばす人が大量に出るだろうと思ったが、意外にもあまり出ない... 衝突予測 300 ★1想定でしたが、場合分けが面倒ということでこの位置に来ました とても簡潔な別解があるらしいです A cans -> B cans 400 典型枠です 個数制無しナップサック問題とほぼ同じ 列辞書順列列 50…

久しぶりの「勝手に回答」シリーズ。今回はTeratailの 複数の制約があるなかでの価値最大化。(ナップサック問題応用) です。 質問では「Pythonで」ということでしたがPythonはよく分からないので， 自分のためのJuliaのJuMPの勉強としてJulia言語で実装してみます。 幸いにしてJuMPのサイトにはナップサック問題の例があるので， これに対してうんうん悩みながら条件を追加していきます。 実装例は次のような感じです。 もうちょっと簡単にできるのかもしれないですけど， あまりコーディング能力がない自分が初めて書いたにしては上出来かなと思います。 using JuMP, HiGHS…

問題文 https://atcoder.jp/contests/abc341/tasks/abc341_f 問題概要 $n$ 頂点 $m $ 辺からなるグラフ $G = ( V, E )$ がある．ここで，$\forall u, ( u, u ) \not \in E$ かつ $( u, v ) \in E \Leftrightarrow ( v, u ) \in E$ である（i.e., $G$ は単純無向グラフである）．頂点 $u \in V$ には正整数 $W_u$ が紐付けられており，また，$A_u$ 個の駒が置かれている． $G$ の頂点 $u \in V$ に対し，open nei…

FastDOCTOR Technologies のブログ編集部です。そろそろ、一年が終わろうとしていますね。みなさんは、IT 企業各社の Advent Calendar はご覧になられたでしょうか。さまざまな企業が有益な事例やノウハウを書かれており、エンジニアにとって非常に楽しいイベントでした。 私たち FastDOCTOR Technologies は、「各社のAdvent Calendarが終わった後に、ひっそりと実施するAdvent Calendar"後夜祭"のような催しがあると面白いかも」と考え、After Advent Calendar という取り組みを行うことにしました。この催しで…

※攻略情報ではなくただの日記です。 10月某日 千葉県某所 某フォロワー「4thぶりですAtPOPさん。なんと今、評価値育成がアツいんですよ！」 ぼく「え？！今、評価値育成がアツいんですか？！？！」 ◆この記事は #シャニマスアドベントカレンダー2023 企画に参加しています ジャンル不問、執筆者募集中！ シャニマス Advent Calendar 2023 - Adventar こんにちは、AtPOPです。 皆さんは評価値ってご存知ですか？ そう、プロフィールやグレフェス画面に表示される"アレ"のことです。 ※アレ F→E→D→...とランクアップしていき、最高でSS☆3になります。 これ、…

先日、下記の記事でナップサック問題の DP を愚直に眺めました。 rsk0315.hatenablog.com 今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○（何らかの集合）の最大値」のように計算せず、○○の部分について考えていきます。 もちろん DP をする際に○○をそのまま持つと空間計算量がめちゃくちゃになる（ことに伴って時間計算量もめちゃくちゃになる）のですが、典型 DP で暗に構築されている集合を考えておくことで、そうした構造を持つ DP を考える際に理解がスムーズになる気がします。 「何々を全パターン考慮したい」となったときに「こういう漸化式を考えればよ…

次回 >> はじめに この記事でやること ZDD(Zero-suppressed Binary Decision Diagram, ゼロサプレス型二分決定グラフ) ZDDとは？ どうやって表現するの？ ZDDのプログラム上での表現方法と実装準備 ZDDクラスのコンストラクタ Diagramクラスのコンストラクタ、ハッシュ関数 ZDDを図示する関数 Diagram.show(self, filename) インスタンスごとに関数をメモ化するデコレーター Diagramインスタンスの生成に用いる関数 ZDD._get_node(self, v, zero, one) アルゴリズムの説明用の記号・記…

はじめに ABC317のA,B,C,D問題をPython3で解きます。 はじめに A問題: Potions 問題の概要 問題の考察 コード B問題: MissingNo. 問題の概要 問題の考察 コード C問題: Remembering the Days 問題の概要 問題の考察 DFSで解く場合のコード bitDPで解く場合のコード D問題: President 問題の概要 問題の考察 コード A問題: Potions atcoder.jp 問題の概要 個の効き目順に並んだ傷薬があり、番目の傷薬を使うと体力がだけ増加する。現体力がで傷薬を1つ使って体力を以上するとき、その条件を満たす最も効き目…

典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP を集める DP と呼ぶ派閥もあった気がしますが、ここでは名称についての議論はしません。 導入 主張 例 ナップサック問題 Eratosthenes の篩 回数の期待値・ゲームなど、操作を伴うもの 最短距離 所感 おわり 導入 初心者向けの解説の多くでは、ナップサック問題の DP などを例に出して、 for i in 0..n { for j in 0..=cap { dp[i + 1][j] = dp[i + 1][j].max(dp[i][j]); } for j in 0..=…