1957年,Bellmanによって提案された多変数最適化問題を解くための手法. 目的関数に再帰性 (可分性) と単調性があり,制約式が逐次的であるとき,原問題をある部分問題群に埋め込んで,各部分問題の最適値を定義し,相隣る問題の最適値間の関係式 (再帰式) を導く.これを逐次解いて,最後に与問題の最適解を求める方法である.解法の効率化のためには,決定変数,状態変数,評価関数などの選択・設定に個々の創意工夫を要する.
(「OR用語辞典」より)
*リスト::数学関連
はじめに 問題設定 再帰式の導出 動的計画法による最適解の導出 まとめ 参考文献 はじめに 新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…
atcoder.jp・参考: drken1215.hatenablog.com ・やり方: 基本的には上の記事を参考。jは0でcapslockキーがoff,1でon。dp[i][j]はi文字でのjがON,OFFであったときにかかる時間。 capslockの遷移はdp[i][0]=min(dp[i][0],dp[i][1]+Z)、dp[i][1]=min(dp[i][1],dp[i][0]+Z)。aを入力するにはj=0のときX秒、j=1のときY秒かかるので、dp[i+1][0]=min(dp[i+1][0],dp[i][0]+X),dp[i+1][1]=min(dp[i+1][1],dp[i][…
フィボナッチ数は高校でも数列の基本として習いますし、機械学習だと動的計画法の導入で少し使ったりします。というわけで身近な題材ですが、これもタイトルにつられて研究費の余りで購入した本です。 話は思っていたより多岐にわたり、数論における未解決問題なども載っています。そもそも未解決問題というのが設定できるのが数学のよい点の一つで、統計学とか機械学習で未解決問題というのはどう定義されるのかがいまいち想像つきません。多端子情報理論とかあるとは思いますが、あれもいわゆる数学的な未解決問題なのかどうかはよくわかりません。ただ、甘利先生とかを見ていると、どんな分野の問題点でも未解決問題を設定する力にすごく秀で…
与えられた整数に対し、以下の素数の数を数えるアルゴリズムを理解します。 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/item…
A 少し問題を読みにくかったが、出来ました。「|」で分割して、一番目と三番目の要素を結合して標準出力する。 B 問題文をきちんと読めていなく、最後の行が必ず「0」であることを理解出来ていなかった。コンテスト中は空文字が読み取れたタイミングで、読み取りを打ち切るようにした。 C オーダーが106だと間に合わないと思って、工夫してしまった。コンテスト中の上限のオーダーと配列とSetでのinの速度が違うことが理解出来ておらずずいぶん手こずりました。 D 動的計画法で解くことが分かりました。一度も実装したことがなかったので手がでなかったです。 分析 ABCの3完出来て良かったですが、Cまでで30分以内…
5完6WA 各問題 A - Spoiler 与えられた文字列を前から読んで出力ですが、最初の | が出た時点で出力をやめ、次の | が出た次から出力を再開とすればよいです。 B - Delimiter 入力した整数を配列に入れていき、0 が出現したら入力をやめて、配列を逆順で出力すればよいです。 C - A+B+C N, M, L がたかだか 100 なので、A + B + C のすべての組み合わせを先に計算して set に入れておき、X がその set に含まれるかどうかを確認していけばよいです。 D - String Bags つまるところ、dp[l] = l 文字目まで一致させるために必…
みなさんこんにちは。Suzuneと申します。 ABC343で茶色コーダーになれました!この記事では茶色になるまでにやってきたことなどを通して、これから競プロを始める人に茶色ってどのくらい頑張ればなれるの?とイメージを持ってもらえればと思います。 目次 自己紹介 茶色の実力 茶色になるまでにやったこと ①ABCに参加 ②ABCのA,B埋め ③できそうなC問題を解く ④ADTに参加 これから 最後に 自己紹介 所属: 松江工業高等専門学校 情報工学科4年 使用言語:Ruby Twitter(X): @Suzune2741 レート推移はこんな感じです。 茶色の実力 Atcoderでの茶色の実力はAt…
Google アラートは便利だけど 情報収集をするのには Google アラートが便利。仕事や趣味に関係するキーワードをGoogleアラートに登録し、それをRSSフィードに出力することで、最新のニュースを見逃すことなく、リアルタイムで情報を取得することができる。 しかしながら、GoogleアラートのRSSフィードをSlackに表示させようとすると以下のような表示になって視認性が低くなってしまう。 Gooogleの転送URLを通るためSlackでカード展開されない ボールドタグが文字列として出力されている 本文が中途半端に出力される また同じようなニュースが重複することも多く、それもまたノイズに…
問題 atcoder.jp 茶色Diff 403 考察 制約 1 ≤ N ≤ 2×10^5 0 ≤ K ≤ 10^9 1 ≤ Ai ,Bi ≤ 10^9 条件 すべての i (1 ≤ i ≤ N) について、X_i = A_i または X_i = B_i すべての i (1 ≤ i ≤ N−1) について、∣X_i − X_i+1∣ ≤ K つまり与えられている Ai, Bi をもとにして以下の4パターンを 1 <= i <= 2 * 10^5 まで全部調べて 最初の数値から、最後の数値まで通過できればOK pattern 1 ai [] -> [] bi [] [] patte…
はじめに Atcoderに触れてから約3年、本格的に取り組み始めてから約8カ月で、当初目標にしていたアルゴ水になることができました ここまでやってきたことなどを振り返ってまとめたいと思います 横軸を回数に 精進量 基本は緑diffまでの問題に取り組んでいました 入茶まで 競プロを始める前は、業務改善でエクセルVBAやPythonを使って「動けばいい」程度のプログラムを書いていました そんな中、偶然AtCoderを知ってる人と話す機会があり、改めて取り組み始めました 毎週ABCに出るところから始めて、時間中に取り組んだが解けなかった問題(CかDまで)を終了後に解説ACするようにしていました 新し…
ラガブーリンの起こすターンやグレムリンボス1tなど、エナジーをアタックに全て使いたい時がありますが、出来ないこともあります。 ふと気になったので、pythonに計算させます。 攻略の役にはほとんど立ちません デッキのアタックのコストと数を最初に入力したらコンピュータがnum回(この例だとnum = 100000)5ドローしてその時のアタックに割けるコストの合計を計算させます。 以下の例はアイクラ初期デッキのものです。 〜 import random, collections """ A1:1コストアタックの数 A2:2コストアタックの数 A3:3コストアタックの数 others:アタック以外の…
ゴルフのスイングのメカニクスについては、科学として理論的・実験的な研究対象になるし、GEARS などの計測機器の発達により、かつて提唱された理論やモデルが、データに基づいて解明・証明されてきている。 一方、スイングという行為については、その内的な感覚や意識の客観的な記述は難しく、それを伝えるには、イメージ表現にならざるを得ない。当然、上達のメソッド(方法論)の説明もそうなることは頭ではわかっている。しかしできることなら、科学的根拠のあるメソッドを学びたい。「科学」とか「科学的」といったタイトルがつけられたメソッド本を、つい手に取ってしまい、時にその科学的ではない説明にがっかりさせられることもあ…
次数 1 の頂点の色 $c$ を固定した時の問題を $O(N)$ で解く方法です。 次の動的計画法を考えます。 - $\mathrm{dp}[u]:=$ 頂点 $u$ を根とする部分木の中で、次数 1 の頂点の色が全て $c$ であるものの通り数。 - $\mathrm{dp}_2[u]:=$ 頂点 $u$ を根とする部分木の中で、次数 1 の頂点の色が全て $c$ であるものの通り数。ただし頂点 $u$ が色 $c$ でなく次数 1 であったとしても、頂点 $u$ が孤立点でなければよいものとする。 頂点 $u$ の色で場合分けをします。頂点 $u$ の子の集合を $\mathrm{chil…
こんにちは、リユナです! AtCoderでやっと入青しました! 実は初めからパフォ2400ですぐ入水したので、入(何か)は今回が初めてで嬉しいです!もちろんこどふぉでは入橙の経験までありますが、基本的にこどふぉよりAtCoderのほうがレーティングを上がりにくいですので、AtCoderの青ならこどふぉの紫以上だと思います。 それで、今まで頑張って最近のARCで入青に成功しました!今までの入青のための旅を繰り返してみます! 1. 初めまして!AtCoder!と休み 2. 復帰。入青を目指せ! 3. 4連敗。やる気消失 4. 復活。5連勝で入青! 5. 入青のために勉強したこと 6. おすすめのユ…