atcoder.jp・参考 Editorial - THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】 - Qiita bitDP（集合を用いたDP）について - D言語で競プ…

atcoder.jp・参考： DPのやり方はDistribution [AtCoder Beginner Contest 214 C] - はまやんはまやんはまやん ダイスクラ法はEditorial - AtCoder Beginner Contest 214を参考にした。・説明： この問題は2つやり方があり、DPとダイスクラ法でできる。 注意…

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考にも書いてあるが、ナップサック問題のDPと同じように解ける。dp[n]はn議席獲得するために必要な鞍替えさせる最低限の人の数である。 今回は鞍…

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…

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アルゴリズム入門講座: 最大正方形…

atcoder.jp・解説： Editorial - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） ・反省点：食べたときと食べなかったときの遷移は別々にやるとWA。食べたときの遷移をして、食べたとき(dp[i+1][0],dp[i+1][1])と食べなかったとき（dp[…

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]…

atcoder.jp ・内容： 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita の記事のbfsでの実装をpythonでやった。 ・説明：0から1,6,6*6,,,9,9*9,,,,の辺を取ったグラフと見ればbfsで求められる。詳しくは上の記事を参考。c++ではfor文で…