アルゴ式のテスターに選ばれました（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なのが不安．．．
アルゴ式のテスターに選ばれました（2日目）
別に毎日更新しようと思っているわけではありませんが，たまたま気が向いたので今日も書きます．
進捗
今日は動的計画法のQ2-1～Q2-4までをやりました．２次元の動的計画法の前半部分です．昨日取り組んだ内容と比べるとやや時間がかかりましたが何とかＡＣできました．
感想
Q2-1，Q2-2は良いとして，Q2-3で少し悩みました．以前もやったことがあるような問題だし，DPっぽいなと思うのですがなかなか手が付きません．今回の問題を通して，配列dpの取り方（置き方？）がよく理解できていなかったということを自覚しました． Q2-3では，
dp[i]がi日目の報酬の最大値
のようにすればよいのかな？と漠然と考えていました．ただ，もしi日目に仕事0を行っていたとするとi+1日目には仕事0は行うことができません．でもi+1日目に仕事0を行った方が報酬の最大値が大きくなる可能性があるということくらいは僕でもわかります．今まではここまで考えて，うーん，うーんとうなって終わりだったような気がします．
今日はこのあともう少し考えてdp[i][j]は，i日目に仕事jをやったときの報酬の最大値とすれば良さそうであると気づくことができました．なぜ気づくことができたのかと言われれば２次元動的計画法の問題だよと教えてもらっていたからな気がします．
あと，Q2-4の解説を読んで，初めて「配るDP」と「貰うDP」の意味が分かりました．今までピンと来てませんでした．けんちょん本もよんだりQiitaの記事も読んだりしましたが，なんで今までピンと来ていなかったのでしょうか．
おわりに
毎日こんなにたくさんの文章を書くのは無理なので続けられるペースでやります（継続できる範囲で）．明日はきっと更新しません．
アルゴ式のテスターに選ばれました（１日目）
アルゴ式のテスターに応募したらなんと選ばれちゃいました．
現状
アルゴ式の取組状況はこんな感じ．
ちなみにAtCoderの色は茶色（2021/10/11）highestは847（緑）
なお，大学院まで数学専攻ですがもう10年以上経っていますし，なんなら位相幾何学専攻でしたので競プロに役立つとされる整数分野は高校では未履修です（たぶん）．でも高校数学は割とできます．
今後
TwitterのDMによるやり取りで，興味ある分野をDPと申告したので，とりあえずDPのコンテンツに取り組んでみて，進捗報告をしていくことになりました． AtCoderのEDPCも途中で挫折してしまっています．
１日目
とりあえず動的計画法を進めます．
今日はQ1-1～Q1-6までやりました．
この６問で１時間くらいかかりました． ちゃんと図を書いたりしながらやりました． 途中のタイルの問題も解くことができましたが，DPの問題だとわかっていない場合に，DPで解けると気づけるかどうかは微妙だなと感じました．
今日の感想
とりあえず初日なので無理せずにあまり悩まずにできるところまでをやりました． コツコツ続けていきたいです．
