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…
競プロ典型90問の★4以下を解く その1(001、002、003) 精進(2024/5/2) - あるぱかのブログ (hatenablog.com) 004 - Cross Sum(★2) 007 - CP Classes(★3) 008 - AtCounter(★4) 結果 004 - Cross Sum(★2) リンク:004 - Cross Sum(★2) (atcoder.jp) 概要:二次元グリッドのが与えられます。について自身含む上下左右すべてのマスを足した数をとした配列を出力してね について、横方向の和をとった配列と縦方向の和をとった配列を準備します。 これによってで計算できるよ…
最短経路問題について 動的計画法の導入 動的計画法による最短距離の求め方 プログラム実装上の注意 C++での実装例 最短経路問題について 以下の0~6のノードがある経路があります。矢印と数値はノード間の距離を示します(例:ノード0と1の距離は4)。 0から6までの最短距離と求めるといくつになるでしょう? 真っ先に思いつく方法は全経路の距離を求めて、その距離を求めればよいです。この図の場合、 0 ⇒ 1 ⇒ 4 ⇒ 6 0 ⇒ 1 ⇒ 2 ⇒ 5 ⇒ 6 0 ⇒ 1 ⇒ 2 ⇒ 3 ⇒ 5 ⇒ 6 0 ⇒ 3 ⇒ 5 ⇒ 6 の4通りが存在するので、これでも求められます。 しかし、ノードが増える…
はじめに 以前、とあるエンジニアの方とお話していた時のお話です。 唐突に「好きなアルゴリズムなに〜?」って聞かれました。 私は意気揚々として、「DP(動的計画法)」と「ダイクストラ」が好きです!って答えました。 結果返ってきたのが、「みんなそう言うよね〜w」という。 いやまぁ、分かる エンジニアとして生計を立てている私としては、正直このような会話が出来る時点で面白い。とても面白かった。 そして「みんなそう言うよね〜w」という意見もすごく分かります。 ゆえに、本記事は相手の反応にイラッとしたとかの話ではなく、エンジニアはこういう世界線で生きたいよね、という話になります。 DPって何?ダイクストラ…
記事の内容 この記事では、人工知能や認知科学に関するおすすめ本を紹介します。 読み物的な入門書から理論系の本まで、できるだけ幅広く紹介したいです。 色々なテーマの本を読んでいますが、人工知能は理論的にも、実社会的にも、とても面白い話題ですよね。今後も目が離せません。 それでは、目次をどうぞ。 記事の内容 人工知能と認知科学について 認知科学 心と脳 認知科学入門 安西祐一郎 教養としての認知科学 鈴木宏昭 類似と思考 鈴木宏昭 人間の解剖はサルの解剖のための鍵である 認知科学への招待 大津由紀夫 コミュニケーションの認知科学1 言語と身体性 認知科学への招待 苫米地英人 知能の物語 中島秀之 …
基本情報技術者試験を受けて多分(?)受かりました。僕は過去問を周回したりする、いわゆる試験勉強みたいなのが苦手です。 なので僕みたいな怠惰な人が日頃からダラダラ本を読むことで過去問をあまり解かずに受かる方法を残しておこうと思います。どちらかというと、普段ダラダラ読んでる本の中から試験に役立つ本をリストアップするというのが正しいかもしれません。目次 自己紹介 基本情報技術者試験 試験範囲について 勉強方法について 受験 おわり! 自己紹介 都内某所でプログラマとして働いています。 数年前までAtCoderをやっていました。 会社ではAWSのインフラ色々いじったり、PHPの異常レガシーコードをしば…
レーベンシュタイン距離とは? 例:「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…