アルゴ式のテスターに選ばれました（10日目）
今後の方針
昨日，何とか動的計画法のコンテンツを終えたので，次にやるところをどこにしようか悩んでいましたが，アルゴ式さんから
「毎日アルゴ式」の過去問を埋めながら、日々の問題を並走していくのがよいと思います。
とアドバイスをいただいたので，素直に従って，
をやることにしました．
進捗
貪欲法のQ1-1〜Q1-5をやりました．少し悩むところもありましたが，なんとか自力ACです．
それに加えて毎日アルゴ式の本日分（10/20）もやろうと思いましたが，ちょっと難しそうだったのでまたにすることにしました．
ちなみに，自力ACした問題の解説もきちんと読んでます（コードも含めて）
感想
貪欲法は実装自体はそんなに難しくないと言う印象ですが，貪欲法でやれば解を求めることができるということの証明の部分が難しいなと感じています．だから嘘解法しちゃうんだろうなあ．
今日はこれでおしまい
おまけ1
Macの変換って慣れないと難しいですね（すぐスペースで変換を押してしまう癖を抜けば便利そう）
おまけ2
統計検定2級の受験も予定しているのでそちらの勉強もせねばなりませんがサボっております．
アルゴ式のテスターに選ばれました（9日目）
進捗
数日詰まっていたQ3-6に何とかACし，勢いそのままにQ3-7もACしました！やった！！
Q3-6について
最初の実装
dp[i][j]はi番目までを使用しjを作れた場合は，j%Aの値．jを作れなかったときは-1．
N, A, B = map(int,input().split()) X = list(map(lambda x: int(x)%A ,input().split())) sumX = sum(X) dp = [ [-1]*(sumX+1) for _ in range(N) ] dp[0][0] = 0 dp[0][X[0]] = X[0]%A for i in range(N-1): for j in range(sumX+1): if dp[i][j] != -1: dp[i+1][j] = dp[i][j] if j + X[i+1] <= sumX: dp[i+1][j+X[i+1]] = (j + X[i+1])%A if B in set(dp[N-1]): print('Yes') else: print('No')
結果
1TLEで，そのほかのケースはAC．
解決
自力解決とはいきませんでしたが，アルゴ式の公式アカウントさんに，進捗報告（TLEしたこと）をTwitterのDMでお伝えしたところ，提出コードを見てくださり，
「sumXがとても大きくなる場合にTLEしている様子ですね。」
と言う絶妙なヒントを頂いた．しかも，その後に続けて
「もしヒントなど必要であれば、その旨伝えていただけるとお教えいたします。」
とのことでした（ありがたい）．
この絶妙なヒントを受けて落ち着いて考えてみました．
そもそも先の実装では，dp[i][j]においてiをNまで，jをsumXまでループさせていたので，もっとループ回数を減らすことを考えました．そこで自分のメモを見て次のことに気がつきました
なんだこれは，と言う感じかもしれませんが，これは入力サンプルのdpテーブルを書いたものです．これを書いているときに，横（jに相当）方向の値とjの値が一致していること，Aによる剰余をとっているので，表の中の値も0~A-1までしか取らないことに気づきました（最初に気づきましょうと言うのは置いておきましょう．あと，挿入した図はちょっとずれてますね）
と言うことは，jのループはsumXまでではなくて，Aまででもいいのでは？となり次の実装にしてみました．
N, A, B = map(int,input().split()) X = list(map(lambda x: int(x)%A ,input().split())) dp = [ [-1]*(A+1) for _ in range(N) ] dp[0][0] = 0 dp[0][X[0]] = X[0]%A for i in range(N-1): for j in range(A+1): if dp[i][j] != -1: dp[i+1][j] = dp[i][j] dp[i+1][(j+X[i+1])%A] = (j + X[i+1])%A if B in set(dp[N-1]): print('Yes') else: print('No')
このコードで無事ACです．
ちなみに，解説ではもっとスマートなdpテーブルの持ち方をしており，解説を読めばそりゃそうした方がいいよな，と納得感しかありませんでした．
Q3-7について
最初に手で計算しました．
注：一番下の四角で囲んである一番大事な部分「W-dp[i][j]のMax」の部分は「W-2*dp[i][j]のMax」の間違いです．
幸いにもこの考察が正しかったようで割とスムーズにACできました．
N = int(input()) W = list(map(int, input().split())) sumW = sum(W) dp = [ [False]*(sumW//2 + 1) for _ in range(N)] dp[0][0] = True if W[0] <= sumW//2: dp[0][W[0]] = True mx = 0 for i in range(N): for j in range(sumW//2 + 1): if i+1 < N: if not dp[i][j]: continue dp[i+1][j] = dp[i][j] if j+W[i+1] <= sumW//2: dp[i+1][j+W[i+1]] = True mx = max(j+W[i+1],mx) print(sumW-2*mx)
ただこれも解説の方法とは違っていました．解説の方法も勉強しておかなくちゃと言う感じですが，とりあえず解けたので嬉しいです．
感想
とりあえずアルゴ式の動的計画法の最初のコンテンツがなんとか終了しました．せっかくなのでこのまま続けて【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～をやろうかなぁと思っていますが，違うところも興味あるので悩ましです．整数論のところとかやりたいなぁ．
あと，記事の途中にアルゴ式さんとのDMのくだりを書きましたが，ヒントを与えるということに対するスタンスがとても教育的でありがたかったです．
まだまだ頑張るぞ
アルゴ式のテスターに選ばれました（8日目）
昨日からやっている問題に改めて挑戦した．
挑戦した問題はこちら
結論から言うとできていません．とりあえず愚直に実装したらTLEでした．
N, A, B = map(int,input().split()) X = list(map(lambda x: int(x)%A ,input().split())) sumX = sum(X) dp = [ [-1]*(sumX+1) for _ in range(N) ] dp[0][0] = 0 dp[0][X[0]] = X[0]%A for i in range(N-1): for j in range(sumX+1): if dp[i][j] != -1: dp[i+1][j] = dp[i][j] if j + X[i+1] <= sumX: dp[i+1][j+X[i+1]] = (j + X[i+1])%A if B in set(dp[N-1]): print('Yes') else: print('No')
アルゴ式のテスターに選ばれました（5〜７日目）
進捗
土日はあまり進捗がありませんでした． Q3-4,Q3-5の二問を解きました．
Q3-6もやりましたが，解けませんでした．．．．むむむ algo-method.com
考えていること
Q3-4,3-5は置いておいて，Q3-6で考えていることを書き留めておこうと思います．
問題設定は分かっている（つもり）
とかも知っている
和がMになるかどうか，という問題設定はQ3-2でやった
dpテーブルがうまく作れない
個人的に，dpテーブルがうまく作れれば解決するんだろうと思っている．たとえば番目までのカードを使って，重さjが作れるかどうか，としたのがQ3-2であったから，
番目までのカードを使って，
となるかどうかとすれば良いのか？
True，Falseの真偽値を保持しておいて，のときに，
かどうかを調べて
の値を決定する？
いや，Falseのときダメじゃない？Falseだったら前回の値を保持しておかないと次の値を計算できないよね． うーむ．．．
終わりに
MacbookAirが届きました．キーボードに慣れないと入力しにくいですね．
アルゴ式のテスターに選ばれました（4日目）
今日はやるだけにして書かないつもりでしたがやっぱり書きます．
進捗
動的計画法のQ3-1,Q3-2をやりました． Q3-1はスムーズに解けましたが，Q3-2は２時間くらい悩んだと思います．
感想
Q3-2の問題はタイトルの通り，本当によく見るDPの問題でした．もちろん以前どこかで（多分EDPC）解こうとしたり解説を読んだりしたことがあります．ただ，今回は調べずに（アルゴ式を信じて）この３日でやってきたことを利用できないかという観点で考えました（邪道と言えば邪道かもしれない）．
最初はdp[i][j]のようなリストを考えて，ボールiを箱に入れた時の重さを表して．．．などと考えていましたがうまくいきそうにありません（漸化式がたてれない）．いろいろ考えるうちにdp[i]は重さiが（ボールの組み合わせで）作れるかどうか，というようにすればよいのではないかと考えました．そこからもう少し考えを進めて（DPの問題なのだからそこを利用すると．．．と考えました）dp[i][j]で最初のj個のボールを使って重さ[i]が作れるかを表せばうまくいきそうだと気づきました．
ここまで考えて，最初にやったQ3-1と同じ形の遷移になっていることにも気づくことができました．そうしたらあとは実装するだけなので（といってもここも少し手間取りました）無事ＡＣを取ることができました．
N, M = map(int,input().split()) W = list(map(int,input().split())) dp = [ [False]*(M+1) for _ in range(N)] dp[0][0] = True for i in range(N): for m in range(M): if dp[i][m]: if m+W[i] < M: dp[i][m+W[i]] = True elif m+W[i] == M: print('Yes') exit() if i+1 < N: dp[i+1][m] = True if m+W[i+1] < M: dp[i+1][m+W[i+1]] = True print('No')
ポイント
自分の中で２点ポイントになったことがあると感じています．１点目は事前にQ3-1が用意されていたことです．Q3-1の構造が頭にあったので，Q3-2のdp[i][j]を思いついたときに，この方法で答えを求めることができる，という確信につながりました．
２点目は重さを連続量だと考えないことです．自分の中でQ3-2で難しいと感じている点は「重さ」と「リストの添え字部分」を対応させるというところです．おそらくその理由の一つが，重さを連続量だと思っていて（一般的にはその通りだが，この問題では離散量と考えて良い），リストの添え字として使えるという発想に至るのに時間がかかったような気がしました．
あんまりわかっていないこと
TLEするような解法ってどんなのがあるんでしたっけ？
おわりに
明日，MacbookAirが届く予定です．
アルゴ式のテスターに選ばれました（3日目）
更新しないって言ったじゃないか
進捗
今日も少し進めてQ2-5～Q2-7をやりました．まだ何とか自力ACです．
感想
Q2-7で少しつまりました．DPの部分ではなくて，loopの回し方がうまくいっていなかったり，二次元リストの初期化をミスしていたりしました． 勉強したい考え方以外の部分でミスしたりわかっていないかったりする部分があるのも，学習の妨げになるのだと感じました．
ちなみにQ2-7は解説にもあるように最初に入力で与えられるマス目に書かれている数字を逆順に保存すれば2-6と同じだなと思いましたが，それだと練習にならないなと思って，問題の意図通り実装しました．
別解はこんな感じですかね．
N = int(input()) A = [ list(reversed(list(map(int,input().split())))) for _ in range(N)] dp = [[100000] * N for _ in range(N)] dp[0][0] = A[0][0] for i in range(N): for j in range(N): if i-1 >= 0: dp[i][j] = min(dp[i-1][j]+A[i][j], dp[i][j]) if j-1 >=0: dp[i][j] = min(dp[i][j-1]+A[i][j], dp[i][j]) print(dp[N-1][N-1]) ''' #おわりに MacbookAirをポチってしまいました．M1の整備品でメモリ16GBのものが出ていたのでつい．．．ストレージが256なのが不安．．．
アルゴ式のテスターに選ばれました（3日目）
更新しないって言ったじゃないか
進捗
今日も少し進めてQ2-5～Q2-7をやりました．まだ何とか自力ACです．
感想
Q2-7で少しつまりました．DPの部分ではなくて，loopの回し方がうまくいっていなかったり，二次元リストの初期化をミスしていたりしました． 勉強したい考え方以外の部分でミスしたりわかっていないかったりする部分があるのも，学習の妨げになるのだと感じました．
ちなみにQ2-7は解説にもあるように最初に入力で与えられるマス目に書かれている数字を逆順に保存すれば2-6と同じだなと思いましたが，それだと練習にならないなと思って，問題の意図通り実装しました．
別解はこんな感じですかね．
N = int(input()) A = [ list(reversed(list(map(int,input().split())))) for _ in range(N)] dp = [[100000] * N for _ in range(N)] dp[0][0] = A[0][0] for i in range(N): for j in range(N): if i-1 >= 0: dp[i][j] = min(dp[i-1][j]+A[i][j], dp[i][j]) if j-1 >=0: dp[i][j] = min(dp[i][j-1]+A[i][j], dp[i][j]) print(dp[N-1][N-1])
おわりに
MacbookAirをポチってしまいました．M1の整備品でメモリ16GBのものが出ていたのでつい．．．ストレージが256なのが不安．．．
