1957年,Bellmanによって提案された多変数最適化問題を解くための手法. 目的関数に再帰性 (可分性) と単調性があり,制約式が逐次的であるとき,原問題をある部分問題群に埋め込んで,各部分問題の最適値を定義し,相隣る問題の最適値間の関係式 (再帰式) を導く.これを逐次解いて,最後に与問題の最適解を求める方法である.解法の効率化のためには,決定変数,状態変数,評価関数などの選択・設定に個々の創意工夫を要する.
(「OR用語辞典」より)
*リスト::数学関連
はじめに 今回は、39から45の7問解きました! ちゃんとcopilotなしでやりました(当たり前) 39 JOI 2011 予選 4 - 1 年生 問題はこちらです! 問題文↓ 数列が与えられ、その間に+か-を入れていく 途中、「0未満になる」または「20を超える」ことのない式は何通りか これは、縦N-1(数列の間の個数)、横21(0を含む)のDPを作成しました もし、0未満、20を超えることがでたらDPに書き込まないようにすれば終わりです コードはこんな感じです #include <bits/stdc++.h> using namespace std; #define rep(i, n) …
はじめに 問題設定 再帰式の導出 動的計画法による最適解の導出 まとめ 参考文献 はじめに 新NISAをきっかけに投資を始めようと思い立ったのですが、「どの金融商品にどれくらいの比率で投資すればよいのか」が分からないので、投資を最適化問題として定式化し、その最適解を求めることでこの比率を決めます。 問題設定 投資比率の決定を最適化問題として表すには、まず「何を最大化するのか」を決める必要があります。これを目的関数と呼びます。投資なので「最終的な資産の期待値」を目的関数とするのが自然に感じますが、これは破産リスクの高い投資に繋がります。例えば、以下のギャンブルを考えます。 所持金10万円 コイン…
atcoder.jp・参考 Editorial - THIRD PROGRAMMING CONTEST 2023 ALGO(AtCoder Beginner Contest 318) 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】 - Qiita bitDP(集合を用いたDP)について - D言語で競プロ ・説明 参考記事の1つ目をPythonで実装した。この問題はbitDPを使って解く。bitDPについては参考記事2,3を参考にした。 集合bに含まれていない頂点を追加してDPを更新していく。コードの説明は下の実装でコメントアウトしている。 …
atcoder.jp・参考: DPのやり方はDistribution [AtCoder Beginner Contest 214 C] - はまやんはまやんはまやん ダイスクラ法はEditorial - AtCoder Beginner Contest 214を参考にした。・説明: この問題は2つやり方があり、DPとダイスクラ法でできる。 注意点として、DPでは円上なので例えばN=4のとき4,3,2,1が最適解の場合もあるので2周する必要がある。 詳しい説明はコメントアウトしている。・DP n=int(input()) s=list(map(int,input().split())) t=li…
atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考にも書いてあるが、ナップサック問題のDPと同じように解ける。dp[n]はn議席獲得するために必要な鞍替えさせる最低限の人の数である。 今回は鞍替えさせる人数をコストwと見てこれを最小にすることを考える。コストwはX[i]>Y[i]のとき鞍替えさせる必要がないので0、X[i] #入力。 n=int(input()) X=[] Y=[] Z=[] s=0 for _ in range(n): x,y,z=m…
まだ、初歩的な部分に触れただけなので追記したい。 動的計画法とは 自分の理解 例題 例題の解答コード 参考サイト 動的計画法とは 動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 1、帰納的な関係の利用:より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 2…
atcoder.jp・参考 AtCoder Beginner Contest 314 - YouTube・説明 参考動画の実装をPythonで行った。プログラムの説明は下でコメントアウトしている。 ・実装 n,m=map(int,input().split()) c=[] p=[] s=[] for _ in range(n): l=list(map(int,input().split())) c.append(l[0]) p.append(l[1]) s.append(l[2:]) dp=[10**18 for _ in range(m+1)] dp[0]=0 for i in range(…
<最適化問題の概要> <最短経路問題の解説> <動的計画法の解説> |まとめ(最適化問題、最短経路問題、動的計画法) 数値計算は、コンピュータを利用して数値的な方法で数式やデータを解析し、問題の解決や最適化を行う手法です。 ここでは、数値計算の中で重要な要素となる「最適化問題」、「最短経路問題」、「動的計画法」の3つをそれぞれ解説していきます。 【令和5年度】 いちばんやさしい 基本情報技術者 絶対合格の教科書+出る順問題集 作者:高橋 京介 SBクリエイティブ Amazon <最適化問題の概要> 最適化問題とは、特定の目的を達成する際に、与えられた制約条件の下で最適な解を見つける問題のことで…
atcoder.jp・参考 AtCoder ABC 311 E - Defect-free Squares (水色, 475 点) - けんちょんの競プロ精進記録・説明 dp[i+1][j+1]のi+1,j+1はSのi,jマスの最大辺である。また参考記事の場合、indexを合わせるなら,for (i=1;iアルゴリズム入門講座: 最大正方形問題の動的計画法による解法と考え方の図を参照。 集計は例えば穴の無いマスが2*2あるとき、dp[1][1](1行目、1列)=1, dp[1][2]=1, dp[2][1]=1, dp[2][2]=2となり、穴のないマスは5となる。 h,w,n=map(int…
atcoder.jp・解説: Editorial - Toyota Programming Contest 2023#3(AtCoder Beginner Contest 306) ・反省点:食べたときと食べなかったときの遷移は別々にやるとWA。食べたときの遷移をして、食べたとき(dp[i+1][0],dp[i+1][1])と食べなかったとき(dp[i][0],dp[i][1])どちらが大きいか、見る必要がある。・間違ったコード n=int(input()) xy=[list(map(int,input().split())) for _ in range(n)] dp=[[0 for _ i…
レーベンシュタイン距離とは? 例:「rise」と「kid」の編集距離を計算 プログラム的な求め方 DP法のテーブルを用意 セルの初期化 セルの更新 最終結果 C++で実装 参考 レーベンシュタイン距離とは? 文字列s1とs2がどれだけ異なっているかを示す指標。 1文字の置き換え、削除、追加をコスト1としたとき、s1からs2に変換するための最小コストがレーベンシュタイン距離です。 編集距離とも呼ばれるので、以降はそう呼びます(「レーベンシュタイン距離」は長ったらしいため)。 s1⇒s2とs2⇒s1の変換にかかるコストは等しい。 参考(wikipedia):レーベンシュタイン距離 - Wikipe…
[PPC] About half [PPC] Compound Word [Crypto] Substitution [Web] Typing game [Shell] netcat [PPC] Balanced Choice [PPC] CPC To F [Web] Let's buy some array [Crypto] RSA Trial [Web] Read Novels [Shell] veeeeeeery long text [PPC] Power! or +1 [PPC] About half https://yukicoder.me/submissions/975797 書か…
概要 N本の花が一列に並んでいて、各花には高さhと美しさaがあります。花の高さはすべて異なります。ここから花を抜き去って残った花の高さが単調増加になるようにしたとき、残った花の美しさの総和の最大値を求めてください。 考え方 1.SegmentTree解法 ・美しさaがすべて1である場合 →高さが単調増加するようになるべく多く花を取る問題になる。これはLISにほかならない これは、次のようなDPを保持した動的計画法で求められる DP[i]=残った花の高さのMAXがiであるときの、残った花の数 遷移:i=1...nについて、以下を行う。DP[0],DP[1]...DP[h[i]-1]の区間maxを…
書籍「ゼロから作るDeep Learning ❹ 強化学習編」を読んで強化学習について理解した内容を書いています。1章 バンディット問題 強化学習が他の学習と大きく異なる特徴は、エージェント(ロボットなど)が環境との相互作用の中で学習すること。 2章 マルコフ決定過程 3章 ベルマン方程式 4章 動的計画法 5章 モンテカルロ法 6章 TD法 7章 ニューラルネットワークとQ学習 8章 DQN 9章 方策勾配法 10章 さらに先へ ※強化学習について自分なりの解釈 強化学習は、人間が試行錯誤で色々な行動を試しながら、結果が良かった(成功した)行動は継続して、結果が悪かった(失敗した)行動は繰り…
atcoder.jp 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 784 問題概要 の番号が付いた 個のステージがあり、現在はステージ1のみが遊べる。各ステージ が遊べるとき、ステージ では次の2つの行動のどちらかを行うことができる。各ステージをクリアするためにかかる時間以外は無視できるとき、ステージ を遊べるようになるのは最短で何秒後か。 行動 : 秒かけてステージ をクリアする。結果、ステージ が遊べるようになる。 秒かけてステージ をクリアする。結果、ステージ が遊べるようになる。 制約 入力はすべて整数。 考察 頂点をステージ、辺の重みをス…
世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム- 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム-」内容紹介 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム-」目次 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム-」Amazonでの購入はこちら 「世界標準MIT教科…
ゴルフを始めた後輩の3回目のラウンドは、JGM 霞丘ゴルフクラブにて。河川敷にてデビュー、次は平坦な林間コース、そして今回はなだらかな丘陵コースと、幹事がしっかり考えて、徐々に難易度を上げていっている。 距離は 5,281 ヤードと短い。僕のホームコースの入間カントリーも丘陵コースだが、それよりも傾斜はなだらかである。ホームコースのシニアティーと同程度か、それより易しいくらいのゴルフ場だろう。そう考え、85 を目標スコアとした。掲示板に貼ってある競技結果をみると、ハンディキャップ 15 のゴルファーが 85 で上位に入っているので、目標としてもちょうどよいくらいだろう。 今年はパーオン率の低さ…
AtCoder Beginner Contest 341 D - Only one of two AtCoder Beginner Contest 344 D - String Bags 最近のABCからD問題を解く AtCoder Beginner Contest 341 D - Only one of two リンク:D - Only one of two (atcoder.jp) 概要:正整数のうち一方のみで割り切れる正整数の小さいほうから番目を出力してね この問題では以下の3つの考え方を使用します。ひとつひとつはそれほど難しくない概念ですが組み合わさることで緑diffの問題になるのすき…
3/29 日に yukicoder にて hirayuu_yc さんと共同 writer のコンテストを開催したので、当日までの流れや各問題の感想を詳しく書こうと思います。 準備 最初、hirayuu_yc さんに共同 writer をしないかと持ち掛けられたので、共同 writer をすることにしました。最初は X の DM 上で原案を出し合う形でしたが、それでは不便なところがあるので、原案がある程度形になってきたあたりから Discord で Writer 作業をすることにしました。 実は原案は10月頃から作っていたのですが、私の方が緑以下コンテストのwriter作業やパ研合宿一日目「Sp…
初めに 開発環境 ライブラリのインストール minineedleで使用できるアルゴリズムについて 複数の文章で実行 初めに 文章の類似度に minineedleを教えていただいたので触ってみます。ライブラリの内容を見る感じ タンパク質配列間などを記載があるので、生物系で使われているもの?なのかもしれません github.com (雑に書いたコードは)以下で試したコードを置いていますので、ご参考までに github.com 開発環境 Ubuntu 22.02 Python 3.10 ライブラリのインストール pip install minineedle pip install miniseq m…
フィボナッチ数は高校でも数列の基本として習いますし、機械学習だと動的計画法の導入で少し使ったりします。というわけで身近な題材ですが、これもタイトルにつられて研究費の余りで購入した本です。 話は思っていたより多岐にわたり、数論における未解決問題なども載っています。そもそも未解決問題というのが設定できるのが数学のよい点の一つで、統計学とか機械学習で未解決問題というのはどう定義されるのかがいまいち想像つきません。多端子情報理論とかあるとは思いますが、あれもいわゆる数学的な未解決問題なのかどうかはよくわかりません。ただ、甘利先生とかを見ていると、どんな分野の問題点でも未解決問題を設定する力にすごく秀で…
与えられた整数に対し、以下の素数の数を数えるアルゴリズムを理解します。 Library Checkerで高速な実装を調べてみると、提出107115が最速ですが、このソースコードは未定義動作を含んでいます(ランキング上位を見てみると、62015, 107115, 147826, 150290,150294, 150330, 160040 はすべて同じバグを含んでいます。つまり、62015で埋め込まれたバグのようです)。 上位陣の他の提出もほとんど同じアルゴリズムとなっています(Library Checkerへの最古の提出6832もsmallsへの最適化がされていないことを除いて実質的に同じアルゴ…
問題文 https://atcoder.jp/contests/abc344/tasks/abc344_d 問題概要 文字列の列が $n$ 個与えられる.$i$ ($1 \leq i \leq n$) 番目の列は $S_i = \langle S_{ i, 1 }, S_{ i, 2 }, \dots, S_{ i, A_i } \rangle$ である. ここで,次の処理を行う. 変数 $S$ を用意し,$S \leftarrow \epsilon$ とする*1. $i = 1, 2, \dots, n$ について,順に次の処理を行う. 次の 2 つの内,いずれかを行う. 次の処理を行う. …
DP 解説集 どれ見ても超分かりやすいです algo式: 動的計画法ってなに? https://algo-method.com/descriptions/44 Qiita: 動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 https://qiita.com/drken/items/dc53c683d6de8aeacf5a Qiita: 典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ https://qiita.com/drken/items/a5e6fe22863b7992efdb Slide…