こんにちは。成績の事が気になりすぎて昨日はほとんど眠れなかったとーです。
成績が出て、二年への進級が確定しました。\ｴﾗｲ/
累計したところ、
優上5
優28
良12
可3
で、平均は81強くらいになりそうです なんとか理情への道をつなぎました
あとは2Sでもうちょっと頑張ってできるだけ平均を伸ばしたいです
振り返り
英語
必修は全部優、総合もタームの方は良でしたがセメスターの方は優が来ました まあそれなりに頑張ったのでよかった
チャイ語
1Aも優でした 欲を言えばもっと欲しかったんですけど
数学
1Aは全部優以上が来て自分でも驚いています それだけに1Sの失点がめちゃくちゃ惜しい
理科系必修
構造化学も電磁気も良 電磁気はしかたないとして構造化学良ってマジですか.............................................そうですか...............................................一番頑張った科目なのになあ
総合
言語応用論は優上が来ました 嬉しい アルゴは良 それはそう
とは思いませんか？（強引）
数列の部分和に関する問題って、ABCのC,DとかAGCのA,Bとか、まあまあ結構な頻度で出ているので、問題とその解き方をまとめておこうと思い立った
主に累積和やしゃくとり法などについてまとめる
AGC023A
A - Zero-Sum Ranges
問題文
長さNの整数列Aがあります。Aの空でない連続する部分列であって、その総和が0になるものの個数を求めてください。 ただし、ここで数えるのは部分列の取り出し方であることに注意してください。つまり、ある2つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
例えば、
1 3 -4 2 2 -2
の中の、総和が0になる部分列は
(1,3,-4),(-4,2,2),(2,-2)の3つですよって話
答え
累積和を計算し、その和が共通の部分に着目する
先ほどの例での累積和を計算すると、（初項は何も足さないという意味で0にする、これは「初項からの和を選ぶ」というために重要な操作）
0 1 4 0 2 4 2
である
この部分和の数列で、値が等しいところを二つもってくれば、その間の和は（なにも増えていないので）０になる だから、答えは同じ累積和となる場所の選び方に等しい（0,2,4はそれぞれ1組ずつ選べるので、計3通りになる）
以下はpython3によるコード
N = int(input()) A = list(map(int,input().split())) R = [0] #Rは累積和を格納するリストです for i in range(N): R.append(R[i]+A[i]) #累積和を入れます R.sort() R.append(10**18) #カウントを止めます（番兵） cnt = 1 ans = 0 cur = R[0] #curは今見ている累積和を表します for i in range(1,N+2): #番兵の所で止まるように、N+1まで数えます if cur == R[i]: cnt += 1 #curと新たに見たR[i]が等しければインクリメント else: ans += cnt*(cnt-1)//2 cur = R[i] #違っていたら、curをR[i]に更新 cnt = 1 #cntを1に戻す print(ans)
ABC037C
C - 総和
問題文
長さNの数列 {a_i}と1以上N以下の整数Kが与えられます。この数列には長さKの連続する部分列がN-K+1個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
例えば、N==5,K==3であれば、
1 2 4 8 16
という数列の中に、長さ3の部分列は(1,2,4),(2,4,8),(4,8,16)の3つがあり、これらの総和は7+14+28=49となる
答え
普通に和を計算してると、Kが大体N/2くらいだった時に、その部分を計算するのでO(N)、さらにそれをN/2回やることになりさらにO(N)でO(N**2)となり、N==10**5ではさすがに間に合わない
累積和を使うことで、計算をO(N)まで落とすことが可能（累積和を計算しておけば、K項間の和は一回の引き算で求まるため）
以下はpython3によるコード
N,K = map(int,input().split()) L = list(map(int,input().split())) R = [0] #累積和を格納します ans = 0 for i in range(0,N): R.append(R[i]+L[i]) for j in range(N-K+1): ans += R[j+K]-R[j] #K項離れた累積和の差が加算されます print(ans)
ABC105D
D - Candy Distribution
問題文
N個の箱が左右一列に並んでおり、左からi番目の箱にはA_i個のお菓子が入っています。あなたは、連続したいくつかの箱からお菓子を取り出してM人の子供たちに均等に配りたいと考えています。そこで、以下を満たす組(l,r)の総数を求めてください。
例えば、4 1 5という入力が与えられて、M == 2であった場合は、
(4)と(4,1,5)という二組が、2の倍数になる
答え
累積和と同じ要領で、i番目までの和をMで割った余りを保持しておく
そして、その余りが等しいものを選べば、その間にある項の総和はMでわった余りが0になる
以下はpython3によるコード
N,M = map(int,input().split()) L = list(map(int,input().split())) L.insert(0,0) #Lの先頭に0（Mで割った余りが0）をいれた for i in range(1,N+1): L[i] = (L[i-1]+L[i])%M #累積和を計算する所を、Mで割るように変更 L.sort() p = L[0] cnt = 1 ans = 0 L.append(0) for i in range(N+1): if L[i+1] == p: #あとは同じ数字の組を数える cnt += 1 else: if cnt == 1: cnt = 1 p = L[i+1] else: ans += (cnt)*(cnt-1)//2 cnt = 1 p = L[i+1] print(ans)
ABC032C
C - 列
問題文
長さNの非負整数列S=s1,s2,...,sNと整数Kがあります。 あなたの仕事は、以下の条件を満たすSの連続する部分列のうち、最も長いものの長さを求めることです。部分列の長さは1以上の列でないといけません。
もし条件を満たす部分列が一つも存在しないときは、0を出力してください。
答え
しゃくとり法を使う
注意すべきことは2/28の記事に大体書いてあります
以下はpython3によるコード
N,K = map(int,input().split()) L = [] for i in range(N): L.append(int(input())) startindex = 0 #最初はスタートとエンドの番号が0になっています endindex = 0 length = 0 #ここで尺取り虫の長さを管理します mul = 1 #積を管理します ans = 0 #最終的な答えです while startindex <= N-1: #スタートがまだ数列の終わりに無い時の話です if 0 < mul <= K: #積が0より大きくK以下であれば if endindex < N: #エンドインデックスを考慮して if mul*L[endindex] <= K: #エンドインデックスを掛けて良いなら mul = mul*L[endindex] #掛けます endindex += 1 #エンドインデックスを+1して length += 1 #尺取り虫の長さを1増やします if ans < length: ans = length #答えを更新するかの判断 else: #エンドインデックスが掛けられないなら if startindex == endindex: #スタートとエンドが同じなら startindex += 1 #スタートとエンドを1つずつずらします endindex += 1 else: #スタートとエンドが違うなら mul = mul//L[startindex] #スタートで割ります startindex += 1 #尺取り虫が後ろの方から進みます length -= 1 else: startindex = N #エンドインデックスが数列の終わりまで来たので、これ以上伸ばしません elif mul > K: if K != 0: mul = mul//L[startindex] startindex += 1 length -= 1 else: #K==0という特殊な状況を考えます L.sort() #リストの中に0があるかを探すためにソートします if L[0] != 0: startindex = N ans = 0 #Kが0であるうえ、リストの中に0がないなら用無しです else: startindex = N #0があれば任意の長さでOKなので打ち切ります ans = N else: #積が途中で0になってしまったら、Kが任意の値であっても数列は任意の長さが取れます ans = N startindex = N print(ans)
こんにちは。今日も昼過ぎに起きました。とーです。
解くに至った問題（7問）
ABC:019B/025B/038C/047B/068D/105D
ARC:022B
ABC105D
また部分数列の問題 部分和でMで割った余りが0になるようなところはいくつありますかってのを求める
結局、これも累積和を計算し、あるところとあるところの累積和を引いたものをMで割ると0になるならば（つまり、二つの累積和はMで割った余りが等しい）、その間の累積和はMで割り切れますよということを使ってやっていく
累積和と言っても、Mで割ったあまりのみが気になるので、累積和を計算する過程でMで割る操作をすれば、勝手にM以下の数字に変換される
あとは、余りが同じものの数を数え、そこから2つ選ぶ場合の数を計算して足し合わせれば答えになる
解けなかった問題
ABC:098D/106D/118D
こんばんは。昼過ぎに起きて人生が終了しがちです。とーです。
AtCoder
解くに至った問題（1問）
ABC:120D
ABC120D
島の間に橋が架かっていて、これを一本ずつ落としていったら、いくつかの橋を使って互いに行き来できなくなる島のペアの数を列挙していこうねっていう趣旨の問題
昨日の記事に思考の流れを書いた通り、UF木を扱ううえで「枝を切る」という操作はやりにくい（というか実装法を知らない）ので、逆に後ろの方から橋を架けていくというやり方を採用していく
さて、橋を架けるという操作を扱う時、この問題で考えなければならないのは「橋を架けることで新たに行き来可能になる島は何通りあるか」ということである
結論から言ってしまえば、
①橋を架けた島同士が、UF木で同じ根を持っていた場合（つまり同じグループ）、新たに行き来できるようになる島はない
②橋を架けた島同士が、UF木で違う根を持っていた場合、新たに行き来できるようになる島のペア数は、その根を持つ島（繋いだ島と同じグループに属する島）の数を掛け合わせたものになる（例として、根１に島が二つ（ア、イ）、根２に島が３つ（ウ、エ、オ）属していたら、イとウをつなぐことで、この二つの島を介してア、イ、ウ、エ、オは全て行き来できるようになり、新たに行き来できるようになった島のペア数は2*3 == 6）
この二つだけを念頭に置けばよい
問題を解くうえで、「根に島がいくつ属しているか」という情報が必要になる
今回はsizeという値で管理することにする sizeは、最初どの島も1を持っているが、UF木で言うところのuniteの操作をするたびに、吸収した側の島の値に、吸収された側の根のsizeを加えていくことで、共通の根を持つグループの要素数を管理することができる
以下にコードを書いていく
まずは入力N,Mと橋の情報を格納するリストL、そしてサイズ付きUFの実装を行う
N,M = map(int,input().split()) L = [] for i in range(M): L.append(list(map(int,input().split()))) L.reverse() #橋が0の状態から架けていくので、リストを逆順にする（この順番で橋を架けていく） par = [] rank = [0]*N size = [1]*N #サイズの情報を加えたUFを作っていく for i in range(N): par.append(i) def find(x,par): if x == par[x]: return x else: return find(par[x],par) def unite(x,y,par,rank,size): #ここもsizeを加えて改良する x = find(x,par) y = find(y,par) if x != y: if rank[x] < rank[y]: par[x] = y size[y] += size[x] #sizeの変更方法は上で説明した通り else: par[y] = x size[x] += size[y] if rank[x] == rank[y]: rank[x] += 1 def same(x,y,par): return find(x,par) == find(y,par)
ここから、「入力で与えられた島をつなげると、新たに行き来できる島の組がいくつできるか」を調べていく 数え方は上で述べた
res = [] #ここに「新しく行き来できるようになった島のペア数」を保管する for i in range(M): A = find(L[i][0]-1,par) #入力は0インデックスに注意 B = find(L[i][1]-1,par) if A == B: res.append(0) #同じ根を持っていたら新たに行き来できる島のペアは増えない resに0を入れる else: res.append(size[A]*size[B]) #違う根であれば、sizeで保管した要素数を掛け合わせる unite(A,B,par,rank,size) #ペア数をresに入れたら、島同士を結ぶ ans = 0 for i in range(M): ans += res[M-i-1] #行き来できるようになった島を数えたので、逆順に出力すれば「橋を落とすことで行き来できなくなる島の数」になる print(ans)
今回もじゅっぴーダイアリーを参考にさせていただきました はてな記法の件もこの場を借りてお礼を申し上げます ありがとうございました
juppy.hatenablog.com
テスト
N,Q = map(int,input().split()) L = [] for i in range(Q): L.append(list(map(int,input().split()))) par = [] rank = [] for i in range(N): par.append(i) rank.append(0) def find(x,par): if par[x] == x: return x else: return(par[x],par) def unite(x,y,par,rank): x = find(x,par) y = find(y,par) if x != y: if rank[x] < rank[y]: par[x] = y else: par[y] = x if rank[x] == rank[y]: rank[x] += 1 def same(x,y,par): return find(x,par) == find(y,par)
ここまではOK
A,B,C = map(int,input().split()) if B//A >= C: print(C) else: print(B//A)
こんにちは。金恋GTのグランドエンディングまで見て涙したオタクです。いやーよかった.........................................................................................................................................................................................................................................................................................................................................................。
解くに至った問題（7問）
ABC:042B/075B,C/120A,B,C
AGC:007A
ABC075B
グリッドを操作する苦手なタイプの問題。放置しまくってました。
結局、難しいところは「周囲八方向が'.'か'#'かを確認する際の例外処理」に集約されると思われる
例えばグリッドの外周であれば多くても五か所（角に至っては三か所）だけを調べればよいが、周りにほかのマスがある場合は八か所全部調べないといけない、といったことを、いちいち場合分けして処理するのが面倒くさいというところを解消したい
で、そういう時に「あらかじめ移動する方向の差分のリストを持っておく」というのが便利である
例えば、
dx = [0,0,1,1,1,-1,-1,-1]
dy = [1,-1,1,-1,0,1,-1,0]
としておけば、（dx[k],dy[k]）をそれぞれx方向、y方向の移動と捉えることで、8通りすべて賄うことができる
さらに、例外処理は面倒なので、全八通りを出したうえで、
①（調べるマスの行番号）+dy[k]が0未満、もしくはH以上であれば調べない
②（調べるマスの列番号）+dx[k]が0未満、もしくはW以上であれば調べない
とすれば、実質的に例外処理をしたことと同じになる
全方位を探索するのに、こういう工夫ができると楽
また、昨日もちらっと書いたが、例えば
L = [['A','B','C'],['D','E','F'],['G','H','I']]
というリストを
ABC
DEF
GHI
と出力したい場合は、
for i in range(3):
for j in range(3):
print(L[i][j],end = '') #行ごとに改行なしで出力
print() #一行出力しきったら改行
とすればよい
AGC007A
与えられた模様が右、下の移動のみで進んでいけるかどうかを判定する問題
右に行けば列番号が1、下に行けば行番号が1増えることから、結局(1,1)から(H,W)に移動するまでの間にH+W-2回の移動する必要がある
(1,1)にも模様'#'がついていることを考えれば、全体で'#'の数を合計するとH+W-1になるので、これが与えられた情報と合致するかを判定すればよい
ABC042B
文字列を辞書式に並べてつなげて出力する問題
文字列の比較は不等号でできて、小さいほうが辞書で先に出てくる方になる（それはそう）
解けなかった問題
ABC:120D
ABC120D
見た瞬間「UF木やんけ！」と思ったものの与えられる橋の情報が多く、それだけで逐一確認していくのは不可能だと判断
次に「あれ、逆順から島をつなげていって、行き来できる島を数えていけばよくね？」と考えたものの実装できず
サイズ付きのUF木なるものがあるらしい これはrank（木の根っこ）の情報に加えて、各要素が所属するグループの全要素数の情報を付与したもの
これがあれば、
①島同士が最初から同じグループに所属していた→島をつなぐ作業により新たに行き来できる島はないため＋０
②島同士が別グループに所属していた→島をつなぐ作業によって新たに行き来できる島は（今連結した島を含め）その島同士が所属するグループの全要素数に等しいので、答えにグループの要素数の積を足す、そして、そのグループ同士をuniteでくっつける
結局これをM回繰り返せばよくなり、時間的には間に合う
明日実装してみます サイズ付きUF木を学習する
ウニ
アリア鳥取れました うれしい
Warcry地帯は擦ったら全ピカしました 最近擦りに自信がつき始めています
この曲、とにかく巻き込みやすいから大変だし、それだけじゃなくてラストのフリックも地味に抜けやすくてなかなか手こずる奴でしたが鳥取れて感無量でした
そろそろ15.5も見えてきそうなので、上位の曲を練習していきたいです
こんにちは。一時に寝たのに起きたら十二時になっていて自分の体のポンコツさを実感しています。とーです。
解くに至った問題（10問）
CADDi 2018 for Beginners:B
全国統一プログラミング王決定戦 エキシビション:B
CODE FESTIVAL 2017 qual A:B
CODE FESTIVAL 2017 qual C:B
AGC:017A
ABC:021B/026C/104C/107B/119C
CODE FESTIVAL 2017 qual A B
N行M列のオセロみたいに、石が全部白を表にしておいてあり、白黒を反転させることができる 黒の数を与えられた数と等しくできますか？という問題
行をひっくり返すことをk回、列をひっくり返すことをl回やったとすると、黒が表を向いている石の数は
k*(M-l)+l*(N-k)
となる
なぜなら、k*(M-l)はk回分の行のひっくり返しをしたうえで（この時ひっくり返した行はすべて黒）、l回のひっくり返しをしていない列を選ぶ（ひっくり返した列を選ぶとまた白に戻ってしまう）場合の数と等しいからである（l*(N-k)も同じ）
んで、これが与えられた数と等しくなるかを全探索すればよい（N,K<=1000なので間に合う）
ABC107B
Grid Compression
列や行を圧縮できるところまで圧縮しましょうねという問題
愚直に列や行を取り除いて圧縮するアルゴリズムを考えていたけど、ちょっとそれは厳しいかなーと思い答えを見たところ、
「'#'が含まれる行、列をマークしておき、その行と列が交差する部分に存在する要素のみが残る」
とのこと
実際それはそうという感じで、マークがつかない→列or行がすべて'.'で構成されているため当然取り除かれるし、交差しているところは行で取り除く作業にも列で取り除く作業にも引っかからないから取り除かれない
考え方はこれでよいので、あとは実装を頑張る
行と列の数だけFalseで埋めたリストを持っておく
row = [False]*H
col = [False]*W
リストL[i][j]が'#'であれば、row[i] = True, col[j] = Trueとしてあげれば、その部分は交差しているのでOK（つまり、i行目とj列目は取り除かれない）
それが終わったら、今度はTrueになっている各行に対し、その行の中で列リストがTrueに代わっている成分だけをprintするようにしてあげればよい
列の改行はいらないが、行ごとの改行はいるので、そこに注意しながら出力する
（改行がいらないときはprint(なんちゃら,end = '' )とすればよいし、改行がいるときはprint()と下に添えればよい）
True/Falseで管理する便利さをまた一つ実感した
ABC021B
最短経路か否かを判定する問題
重みの無い経路における最短経路は閉路（同じところを二度以上通ること）がない（だから、現れる頂点はユニーク）ということに注意すればよい
ABC026C
木構造のようになった上司、部下の関係から、トップの人の給料を求めようという趣旨の問題
あれ？UF使えそう？とか思ったけど、木構造かつその構造が下にどんどん広がっていってよいということから、UFとはちょい違う実装をしなければいけない
やってみたがちょっと厳しそうだったので断念 解説ACをしました
肝心なところは、「自分の社員番号よりも社員番号の小さい人しか上司になれない」ということ
だから、番号を逆順に辿っていくことで、最終的にトップの人が求まればよい
考え方は以下の通り
まず、i番目に社員番号i+1番の人の給料、直属の部下を入れるリストPay_Subを作る
例えば（トップ含め）7人であれば、
Pay_Sub == [[1,],[1,],[1,],[1,],[1,],[1,],[1,]]
みたいな感じ
そして、部下の情報を入れていく
入力が
1
1
2
2
3
3
みたいな感じであれば、
Pay_Sub == 1,[1,2,[1,[3,4]],[1,[5,6]],[1,],[1,],[1,],[1,[]]]
のように入る
そして、リストの中を逆順に見ていき、
len(Pay_Sub[i][1]) != 0のとき（つまり部下がいる場合）、
新たに作ったリストに部下の給料を入れていき、そのmax,minを調べてPay_Sub[i][0]（社員番号i+1番の人の給料）を更新、というのを、iがN-1から0までやればよい
そして、最終的にPay_Sub[0][0]が答えとなる
ABC119C
本番中にACできなかった問題
竹がN本あれば、一本の竹につき、Aに使う、Bに使う、Cに使う、使わないの4パターンがあり、それを全探索すればよい N<=8なので多くても65536通りになり間に合う
また、竹をつなげてから伸ばしたり縮めたりすることと、一本一本の竹を伸ばしたり縮めたりしてからそれらの竹をつなげる作業は等価なので、今回は簡単な「全部繋げてから差分を伸ばす、縮める」でやるのがよさそう
竹をどこに使うかの全探索のやり方が分からず（解説には再帰を使ってやる手法が書いてあったけどこれが思いつくほど精進を積んでない）、0から4**Nを4進法で表し、それぞれの桁を竹一本一本に割り当て、（無から有を生やすことは出来ないので、最低一つの竹をA,B,Cに使うことに注意）0だったら使わない、1だったら竹Aに使う......みたいな感じでやり、このやり方でも一応ACできたが、4進法に直すところで明らかに時間を食っており、改善が必要
誰か教えてください
一応10進法をn進法に変換する簡単なやり方があったのでそれを載せておく
①10進法をn進法に直し、文字列として出力
X = int(input())
def Base_10_to_n(X, n):
if (int(X/n)):
return Base_10_to_n(int(X/n), n)+str(X%n)
return str(X%n)
②10進法をn進法に直し、左から規定の桁まで0埋めしたのを出力
X = int(input())
def Base_10_to_n(X, n):
if (int(X/n)):
return Base_10_to_n(int(X/n), n)+str(X%n)
return str(X%n)
print(Base_10_to_n(X, n).zfill(P)) #P桁埋める zfillは文字列のみ有効
参考にさせていただいたのはこちらのページです。ありがとうございます。
Python Tips：Python でゼロパディングしたい - Life with Python
ABC104C
これも実質的に全探索の問題 工夫が必要で、問題を①全部解く②ちょっと解く③一問も解かない、の三つに分類して、そのうえで「ちょっと解く」は0か1種類でよい（二種類以上を解くのであれば、点の高い方を解いた方が得だから）ということを念頭に置いて解く 全探索は上で紹介した二進法表記でイケるらしい（想定解がそれだから全探索するときN進法に置き換えるのはあながち間違いではないか......？）
こんにちは。minori解散の一報を受け悲しみに暮れています。とーです。
悲しみのあまり金恋をぶっ通しでやり続けてしまいました。明日からはちゃんとした生活習慣に戻ります。
解くに至った問題（1問）
DPまとめコン:C
DPまとめコンC
解説がないので一応覚書として
DPを使うのは（題名からして）明らかなので、とりあえずどういうDPを作ればよいかなと考えたところ、i日目に活動aをやった時の幸福度の最大値は、i-1日目に活動b、活動cのいずれかをやった時の幸福度の最大値にi日目の活動aの幸福度を足したものになると考えれば
dp_a = [i番目には、i+1日目にaをやった時の幸福度の最大値]
というリストをdp_b,dp_cと作ってあげて（漸化式から簡単に作れる）、それぞれのN番目の要素を比較し、最大をとればよい
計算はO(N)だけかかるので、N<=10**5なら十分間に合う
こんにちは。昼過ぎに起きて洗濯や自炊をしていたらもう7時になって愕然としていました。とーです。
ABC:032B,C/054B/060D/112C
ABC060D
ナップザック問題やんけ！できるかも！と思ってやってみたところ、重さdpしか知らないため制限重量W <= 10**9ではとてもじゃないけど扱えないということで答えを見ました
この問題のキモは、与えられた品物の重量の最大値と最小値の差が高々3しかないということ つまり、最初に重さごとに分類しておいて、それから「重さxの品物をいくつ取るか」ということを全探索で求めていけば十分間に合う（最悪の計算量は、100個の品物が25個ずつに均等に分かれて、品物をいくつ取るかの選択が25**4となるときだが、これは10**6よりは小さいのでなんとか間に合う）
pythonは実行時間がやや遅いので、ここでは工夫して、まず品物を重さごとに分類した後で価値の高い順にソート→前から累積和をとっていく（つまりリストのi番目が、そのリストの中からi+1個選んだことに相当する）ようにした これによって、品物をいくつ取るかを決めた時点で、その個数選ぶ際の最大価値が一目で分かるようになった
しかし、初めから特定の重さの品物がないときは、例外処理の全探索のコードを書くのが難しくなるので、品物を0個選ぶのと、価値0の品物を一つ選ぶことは等価と考え、ソートして累積和をとった後でリストのケツに0を突っ込む作業をした こうすることで、例外処理をする必要がなくなる
ABC032C
数列の中にある部分列の項の積を、与えられた数字Kよりも小さくなるようにしながら、できるだけ長く伸ばすと長さはどんなもんよ？っていう内容
しゃくとり法というやり方が使えます（蟻本にはp.137あたりに、部分列の項の和を求めるところでこの手法を使っていますが、今回は積で使っています）
イメージとしては、
①スタートとゴールを持っておく
②スタートからゴールまでの積がK以下であればゴールを延ばす（そのうえでゴールの数字を掛ける）
③スタートからゴールまでの積がKより大きくなったらスタートを縮める（そのうえでスタートの数字で割る）
というのを繰り返しやっていく
結構簡単そうに見えるが実装の際に気を付けなければならないことも多く、メジャーなものとしては
①スタートがゴールを追い越さないようにする
②ゴールが数列のケツにたどり着いた時点でゴールを延ばすのをやめる
みたいなのがある
また、足し算の実装は比較的簡単だが、掛け算になるとこれまた気を付けるべき点増えて、この問題に限って言えば、
①数列の中に0が入っていたら、Kがどんな数字であれ条件は満たされる
②K == 0である場合、数列の中に0があればオッケーだけど、逆に0がない場合は条件を満たすような部分列はない（これはコーナーケースでひっかかりがち）
③例えば数列が 2 2 2 2 でK == 16なら、掛け算が一度も止まることなく（始点と終点を動かすことなく）最後まで行ってしまうのでちゃんとカウントを最後でとめる
といった点に注意すべきである
とりあえずpython3でのコードを書いたが、これもっと改善できると思うので、次回解くときには簡潔に書く工夫ができたらいいな
解けなかった問題
ABC:059D
ABC059D
grundy数というのを使う
grundy数というのは
①その状態からどの状態へも遷移できない場合を0
②遷移できる先があれば、その遷移先のgrundy数以外の最小の非負整数をとる
という数
簡単な例で言えば、爆弾ゲームというのがある
小学校で、「0から始め、交互に1または2を足して、最終的に11を言った人の勝ち」というゲームをしたことがある
結論から言うと、これは先手必勝のゲームである これをgrundy数を使って考えてみる
これにgrundy数を当てはめてみると、まず11は0である（このゲームの終わりなので）
そして、10は11に遷移できるので、grundy数は1
9は、10,11のどちらにも遷移できるので、0,1以外の最小の非負整数2をとる
8は、9,10に遷移するので、9,10のgrundy数2,1以外の最小の非負整数の0をとる
......とやっていくと、0~11とgrundy数の対応表は以下の通り
数字 0 1 2 3 4 5 6 7 8 9 10 11
grundy数 2 1 0 2 1 0 2 1 0 2 1 0
これを見ると、
①grundy数が0でなければ、必ず一手でgrundy数を0にできる
②grundy数が0であれば、遷移先のgrundy数は0ではない
となる
必勝法を考える上ではこの言い回しはやや分かり辛いが、結局のところ、先手が自分であるならば、もし自分のターンでgrundy数でを0にした状態で相手に回したら、次の相手のターンでは、相手はgrundy数を0でない状態にしてこちらに回すことになるので、こちらが最適な行動をとれば、相手に負け確定の9,10（9,10はgrundy数が2,1）を押し付けることができる、ということになる
先手は0から始めて2,5,8,11の順で必ず言うことができるので、こうすれば必ず勝つことができる
ニムもこれと本質的には同じで、最後にgrundy数（もしくはXOR）を0にした方が勝ちというゲームの場合、
初期条件のgrundy数（XOR）が0ではない→先手必勝
初期条件のgrundy数（XOR）が0→後手必勝
という風になる
0にした方が負け、という場合は、先手と後手が逆転する
さて長々書いてきたわけだが、このゲームでも同じように考えるとどうやら山の石の数が(0,0),(0,1),(1,0),(1,1)がgrundy数=0の状況になるので、最終的にこの状況に自ら持っていくことができれば勝てるということになる つまり最初のgrundy数が0でなければ先手必勝、そうでなければ後手必勝
逆算して石を増やしていくと、grundy数==0となる場合は、二つの山の石の個数の差が1以下であるときになるそうです（これはちょっと実装できてないので確かめられない）
例えば石の数が(2,1)なら、初期条件のgrundy数は0で、Alice(先手)が山を(0,2)にしてBrown(後手)に回さなければならず（この時点でgrundy数!=0）、Brown(後手)は(1,0)でAliceに回すことになり、この時点でgrundy数は0になったことになり、初期条件のgrundy数==0→後手必勝が分かります
これはまたあとで実装力をつけたらやりたいと思います トホホ
こんにちは。競プロ合宿二日目のとーです。
解くに至った問題（8問）
ABC:001C/005C/006C/015C/017C/028C/030C/057B
ABC001C
四捨五入をうまく扱えますか？的な問題
まず、調べて普通に出てきた組み込み関数round()を使ったところうまく動いてくれない
python3のround()の特徴として、
①0.5は、丸めた結果が偶数になる方に動く
[例]
round(1.5)→2
round(2.5)→2
round(3.5)→4
round(4.5)→4
②0.05......と小数点以下第二位よりも小さいところをround()で丸めると、①に当てはまらない場合が出てくる
[例]
round(0.35,1)→0.4
round(0.45,1)→0.5
これは、少数を浮動小数点で正確に表せないために起こってしまう
さて、四捨五入の他のやり方として
f =（何らかの与えられた数）を小数点以下第二位で四捨五入したいときは
P = Decimal(str(f)).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP)
とするといけなくもない（0.1の部分を0.01と返れば、第三位で四捨五入ができる）
ただ、これも扱いに注意が必要で、例えば
f = 32.65
という値は、上式に代入すれば、
P = 32.7
と返ってきて、一見よさそうだが、
P < 32.7
はTrueになる これはDecimalうんたらで表示桁を小数点以下下一桁にしてあるだけで、（見た眼的には四捨五入がうまく行ってるように見える）実のところ32.7より細かい情報は保持したままになっているからである
だから、本質的には32.65 < 32.7の比較を行っていることと同じになってしまう
これを解消する（つまり四捨五入した後のPを32.7として扱いたい）場合には、Pをfloatに変換すればよい そうすれば、Pが実は32.7より小さいんだという細かい情報が落ちて、P = 32.7として扱えるようになる
P = Decimal(str(f)).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP)
P = float(P)
とすればよい
さて、長々書いてきたが、こういった微妙な扱いを避けるために、四捨五入を自分で定義してしまうのが一番手っ取り早い
fを「四捨五入したい数」、digitを「少数第何位で四捨五入したいか」として
f,digit = map(float,input().split())
def my_round(f, digit):
p = 10**digit
return (f*p*2+1)//2/p
とすれば、これでうまく四捨五入ができたことになる
[例] f, digitを入力として、
my_round(32.65,0) → 33.0
my_round(32.65,1) → 32.7 # これはmy_round(32.65) < 32.7でFalseを返す
my_round(32.655,2) → 32.66
ABC015C
L = [[1,2],[4,5]]
というリストがあり、
L[0],L[1]から要素を一つずつ選んでくる（直積を求める）ようなコードを書きたい
itertoolsのproductというのを使うとよいらしい
文頭にimport itertoolsとつけてから使う
import itertools
M = list(itertools.product(*L)) #*LはL内の要素を表し、こうすればLに内包されたリスト
の数が増えても問題ない
とすれば、M = [[1,4],[1,5],[2,4],[2,5]]となる
ABC017C
長さがMの区間がある その中のいくつかの区間にポイントが与えられており、長さMの区間をすべて被覆しないように区間を一つずつ選んで（区間同士がかぶってもよい）、その合計ポイントを最大化する問題
いもす法を使う
実は以前に触れたことのある手法だったのだけれど、ここでも使えるのかと驚きました
具体例
温泉にi人の人が入りました p番目の人が入った時刻はH_j、温泉から上がった時刻はD_jです（時刻D_jまで温泉に入っていたことにする） この温泉には同時に最大何人入っていたでしょう？
例えば、H_j、D_jの入力が
1 4
2 6
3 5
4 7
4 6
みたいに与えられていたら、リストLを
L = [0,0,0,0,0,0,0,0]
と作っておく これは、L[t]が時刻t-1に何人が温泉に入っていたかを表すリストになる
ここでは、上から入力を受け取った順に、
L[H_j-1] += 1 （温泉に人が入った）
L[D_j] -= 1 （温泉から人が上がった）
とすると、
L = [1,1,1,2,-1,-1,-2,-1]
となる
これを前から順に足していったら、
L = [1,2,3,5,4,3,1,0]
となり、時刻4で最も多く人が温泉に入っていたと分かる、というような手法
（今上で挙げたコードでは最後が0になっている ここに注意する）
さて、上の例では「最も多く被覆している部分はどこですか」というのを求めるためにいもす法を用いたわけだが、今回は「被覆しないところを残しつつポイントを高くしたい」というのが目的である
結論から言うと、一か所でも被覆していないところがあればよいので、まず全部被覆したとして、合計ポイントを加算する そこからいもす法と同じやり方で、区間の各点におけるポイントを計算し、リストに保持しておく
このリストは、その点を被覆する区間が持つポイントを表している（このポイントは、複数の区間の合計ポイントであることもあり得る なぜなら各点を被覆する区間は単一とは限らないので）
そして、それが求め終わったら、リストをソートして、最も小さい（上の例で言えば、ソート後の一番最初に0がくるのはわかりきっているので、二番目に小さい）ものを選ぶ それが、除くべき最小のポイント区間であり、逆にここを除くことで、その点上の区間は被覆されていないようにすることができる
という流れで答えを求めることができる
解けなかった問題
ABC:029D
こんにちは。競プロ合宿1日目のとーです。
解くに至った問題（3問）
ARC:081D/100D
Tenka 1 Programmer Beginner Contest:C
ARC100D
x_i,y_i,z_iがN個の要素として与えられて、（x_iの絶対値のM個の合計）＋（y_iの絶対値のM個の合計）＋（z_iの絶対値のM個の合計）を最大化する問題
要素がプラス、マイナスどちらの形式でも与えられているのが厄介
単純化して考えると、例えばx_i+y_i+z_iのM個の合計を最大化したいのであれば、これは簡単でx_i+y_i+z_iの合計をソートしてM個上から採用すればよい
これを応用して、結局絶対値を外す作業はプラスマイナスを逆にする作業なので、絶対値の合計として求めるならば、opt = ['+','-']として、例えば+x_i+y_i-z_iを値の大きい順にソートし、上からM個の合計をとれば、z_iが負の値ならばそれを正の形に変換したことになる（もちろんz_iが負になるとは限らないので、これが正だったら答えから外れる（マイナスすれば和が小さくなるので））。これを、optについて全探索（8通り）して、最も大きいものが答えとなる
解けなかった問題
ABC:087D/092C/097D
こんにちは。金恋GTが届いてウキウキのとーです。「とー」と申します。はじめましての人は初めまして。
解くに至った問題（9問）
ARC:042A/054B/074C
ABC:036C/037C/079C/118A,B,D
Typical DP Contest:A
ここ二週間でたまった直しを消化していく
ABC037C
数列の部分和の問題再び 以前の問題では「部分和が0になる区間の選び方はいくつあるか」という話で、第i項までの和をリストに保持しておいて一致する部分の二個の選び方を求めればよいというものだった
今回は、数列のK項の和をどんどんずらして足していくとなんぼになるんじゃいという問題
愚直に足すと、最悪O(N**2)かかって間に合わないが、今回も和をリストに保持しておくやり方が使える
第i項までのリストはO(N)で計算でき、それから区間Kの和は、和のリストLの要素から、L[i+K]-L[i]とO(1)で計算される これなら間に合う
数列の和の問題は総和のリストを作ることを頭に入れておく
Typical DP Contest A
与えられた数字を足し合わせて作ることができる数字は何通りありますかという問題
制約は「与えられる数字は100以下、100個以下」
これをDPを使って解くときは、
①0が10001個あるリストdpを作る
②dp[0] = 1にする（1は「その数字が作れる」ことを意味する）
③与えられた数字kに対し、dp[10000]から下っていくように見ていき、dp[i] == 1であればdp[i+k] = 1（つまり和が作れる）とする
（ここでdp[0]からではなくdp[10000]から見ていくことに注意。もし下から見ていくと、例えばdp[0] == 1だからdp[k] = 1となり、今度はdp[k] = 1だからdp[2*k] = 1となり......と実際には作れない数字も作れることになってしまう）
④リストdpには作れる数字の所のみ1が立っているので、総和を計算すれば作れる数字の個数が分かる
という流れ
ABC118D
数直線上にある寺と神社を、スタート地点からどちらも一件だけ訪れるのに必要な最短経路を求める問題
コンテスト中にACできなかったのは悔しい 二分探索や、神社→寺or寺→神社で場合分けすることを思いついたものの根本的なところが間違えていた模様
まず第一の失敗として、二分探索で自分の居場所を特定する際に、普通に与えられた入力だと、例えば自分が一番西にある神社より西にいる場合、訪れる神社が一つしか候補にあがらず、場合分けが非常にめんどくさくなるというものだった
これを回避するために、両サイドに一番西/東にある座標よりとてつもなく大きいものを座標として仕込んでおく方法がある これを番兵（ばんぺい）という
こうすれば、どこに始点があっても自分の両側に神社/寺が存在し、余計な場合分けを考えなくてすむようになる
さらに第二の失敗として、最短経路の出し方を、「まず自分がいるところから最も近い神社に向かう→そこから最も近い寺に向かう、この距離を求める、これを神社と寺を入れ替えてもう一度やる」というものだったが、これには普通に例外があり（サンプルケースでは通ってしまう）
例えば
寺 x 寺 神社 寺
0 1 3 5 6
というケースを考えたとき、（xは初期位置、下の数字は座標）
上の考え方では
寺(0)→神社(5)と神社(5)→寺(6)という経路が採用され、経路の長さ自体は各々6,6である
しかし、右に進めば寺(3)→神社(5)となり、経路の長さは4でより短く、これは上のやり方からは漏れてしまうような場合である
結局、一意に最小を決定するのは難しいので、自分より右、もしくは左にある最も近い神社と寺(どちらも2つある）を見て、
「神社と寺、どちらを先に訪れるか」*2
「神社と寺、自分より右にあるものを訪れるのか、それとも左を訪れるのか」*2*2
の計8通りをすべて試し、その中で最短のものを答えとして採用すればよいということになる
自分でもとめたやり方は案外間違っていることが多いので、複数候補がある（どれが答えになるか決めがたい）ときは、一回候補を全部挙げてみて、その中で比較するというやり方をちゃんと使えるようになりたい
ウニ
Sqluppを解禁 鳥取りました わいわい
楽しいしガンガン腕を動かせてうおお俺今チュナイズムやってるな～～～～～～空間を切り裂いている新音ゲーやな～～～～～～～～となれる曲ですがなかなか難しいです
鳥取るのに15回くらいかかりました 以下攻略というと仰々しいですが、自分が気をつけたところを書いていきます
画像は全てCHUNITHM譜面保管所様よりお借りしました ありがとうございましたhttp://www.sdvx.in/chunithm/04/04069mst.htm
アヘ顔おじさん
7,8小節目、難所とも言い難い所なんですけど1/5くらいの確率で失敗しました
画像より前の部分のホールド＋タップを人差し指薬指で処理するイメージを持って、そのままの流れで拘束スライドを薬指、タップを人差し指で処理すると安定します
37~43小節目 ホールド＋タップ＋エアーの認識難地帯です ここは気合いで行くしかありません 意識したことは両端のホールドとタップは薬指、真ん中のホールドとタップは人差し指で押さえました これは人差し指じゃなくて親指でやった方が良い人もいると思うので個人差かも
45~56小節目 楽しいところ ただ巻き込みアタックが出やすいです 叩くところをちゃんと意識するのと、気持ち指を浮かせると巻き込みにくくなります
48,49小節目のここ、終点の判定が厳しいです 特に最後はフリックを早めに擦り始めると普通にAttackが出るので要注意
61,62小節目 何故かアタが出やすいです 最後は右利きの人も左手から入った方が良さそう
ここまでは前半戦です 鳥狙う時はここまででアタ換算2~3くらいに抑えとくと後が楽
後半は大きな難所が二ヶ所来ます
67~69小節目 後半の難所の一つ目 トランペットの音に合わせて叩くのですがここめちゃムズいね
構造は見ればわかる通り全部右始動の階段＋トリルです
僕は餡蜜が全くできないので素直に目押しするしかなかったのですが、どうしようもないのでとりあえず右手の方をガン見してました これだけでもアタが2,3くらいに抑えられます
77~79小節目 難所その二です
まずは親の顔より見たWarcry地帯 ここは3鍵が4つ、4鍵1つ、3鍵が3つになっててパワーアップしてます やめろ
ここも餡蜜できればいいんですけど、しょうがないから前半4つは目押し、後半4つにかけて餡蜜っぽく交互押しで無理やり通しました
そのあと78小節目からは交互なんですが、だんだん右にずれていくので巻き込みアタックが非常に出やすいです 注意したいところ
ここまでアタ9で来れたら後をAJ通過すれば勝ちです
......と言いたいところですが最後にラッシュがやってきます
この部分、単純な交互トリルですが切れ目(緑のところ)がいやらしいところについていて抜けが出やすいです ここをちゃんと意識してシバくようにしましょう
あとは回数を積めばなんとかなります 金が全てを解決する
解くに至った問題（6問）
ABC:035B/036B/037B/038B/039B
AGC:015B
解けなかった問題
ABC:067D
DPまとめコン:D
ABC067D
木（どのマスも経路を介せば辿っていけるグラフ）をぬりぬりしていく問題
スタートのマスは決まっていて、二人が交互に色塗りしていく
相手が塗れなくなったらこっちの勝ちという趣旨のゲーム
最適な戦略は、相手をなるべく塗らせないようにすればよいのだから、相手のスタートのマスに向けてできるだけ遠くまで塗った方がよい（遠くまで塗っておけば、それより近くのマスは塗ることができるので）ということ これでどっちが勝つのかを判定する
先手はマス1から始め、隣り合うマスを黒く塗り、後手はマスNから始め、隣り合うマスを白く塗っていく
ゲーム自体は、「最適戦略をとったときに、お互いが塗ることが可能なマス目の数を比較して、多い方が勝ち」、「マス目の数が同数になる場合は、後手が塗って同数になり、マス目をすべて塗り終えたことになるので、先手が塗れない→後手の勝ち」とルールを変えても全く同じである
ここまでわかれば、あとはマス1とマスNからすべてのマス目の距離を比較して、近い方の色にぬればよいことが分かる
具体的には、マスiとマスjの距離をd(i,j)としたとき、マスiを黒に塗るときは
d(1,i) <= d(N,i) （1からの距離の方が近い、同じなら先手が塗る）
となる場合である
このようなマス目を計算するのは深さ優先探索を用いることでできる
以前書いたDFSの記事では「経路が一筆書きできるか（木かどうか）」を判定するものだったが、今回もそれに似たものが使えて、距離のデータを保持しておく必要はない
さて、DFSでは最初に、隣接する島のデータを格納するリストを作る必要がある
以下にコードを書いていく（0インデックスで数字が一つ前にずれていることに注意）
G = [ for _ in range(N)] #i番目の空のリストには島iに隣接する島の番号が入る
for i in range(N-1):
a,b = map(int,input().split())
G[a-1].append(b-1)
G[b-1].append(a-1) #隣接する島のデータを入れる
これで島の隣接についてはよい あとは、
visited = [0]*N
visited[0] = 1
visited[N-1] = 1
visited_all = [1]*N
として、「i番目の島が訪れられたかどうか」を格納するリストを作っておく（島0と島N-1はスタート地点なので、すでに訪れられたものとした）
そして、
nextA = G[0]
nextB = G[N-1]
とする これはA（先手）が次に訪れるのはG[0]、つまり0番目の島に隣接した島である、というような考え方で理解できる Bについても同様
さらに、
black = 1
white = 1
とし、ここで黒、白で塗れるマス目の数を保持しておく
ここから塗る作業に入っていく
while visited != visited_all:
l = [ ]
for a in nextA: #先手が次に塗る島を考える
if visited[a] == 0:
visited[a] = 1
black += 1
for x in G[a]: #塗り終えた島について、その島と隣り合う島を見る
l.append(G[a]) #lに今黒く塗った島と隣り合う島のデータを入れ、
nextA = l #nextAの情報を更新 ここから下は後手の話になる
l = [ ]
for b in nextB:
if visited[b] == 0:
visited[b] = 1
white += 1
for y in G[b]:
l.append(G[b])
nextB = l
これをvisited == visited_allとなるまで繰り返す
ここまでくれば、あとはblackとwhiteを比較したうえで、black > whiteならば先手の勝ち、それ以外ならば後手の勝ちとすればよい
ゲームの必勝法問題はほかにもいっぱいある（はず）
石取りゲーム（ニム）を例にとって挙げてみる（蟻本のp.277に載ってる）
[問題]
石の山がn個あり、i番目の山にはa_i個の石がある。AとBは交互に空でない山を一つ選んで、そこから一つ以上の石をとる。最後の石を取った方を勝ちとする。Aから始めた場合、両者が最善を尽くせばどちらが勝つか。
石の山全部の石の個数のXOR（二進法の各桁を比較して異なっていれば1、同じなら0）を考える XOR = 00....0も0と扱う
XORを計算する際、計算して各桁を1,0のみにするのは面倒なので、二進法で表したときにそれをそのまま累積していって、各桁の偶奇を見る方法を利用する
（例）
2 XOR 5 XOR 7
は2,5,7を二進法に直すと10,101,111でそのまま足すと222になり、これは各桁が偶数なのでXORを二進数で直した結果は0が並ぶ（000）
2 XOR 3 XOR 3
は2,3を二進法に直すと10,11でそのまま足すと32になり、XORは10
最終的に自分が石をとって終わりにしたいので、自分が勝つときの最後の局面でのXORは0（0+0+......+0 = 0なのでそれはそう）
ということは、ここから逆算して、自分の手番が終了したときに常にXORを0にできれば必ず勝てる（逆に、相手の手番が終了したときXOR != 0であればよい）
さて、これが通用する理由は二つあり、
①XOR != 0で回ってきたらXOR == 0にして返せる
②XOR == 0で回ってきたらどうやってもXOR != 0にしかできない
からである
②は、0が並んだ状態からはどこをとってもXORが0でなくなってしまう（0を0のままで返せるのは0の足し算のみ）のでわかる
①は、例えば2,4,5を考えたとき、2,4,5は二進法に直すと10,100,101でXORは011、これを000にする（XORを0にする）ためには、011のうち下二つの1を0にする（反転させる）必要がある
やり方は、
ア、XOR結果を二進数で見たときの一番上の1のビットが経っている山を選ぶ。つまり、今回の場合は011で、1のビットが経っているのは上から二番目。2,4,5(010,100,101)の中で上から二番目の1のビットが立っている山は2(010)なのでこれを選ぶ。
イ、選んだあと、011の下二つを反転させたいので、2(010)の下二つを反転させるように石を除く（つまり、1個除いて山を1(001)にする）。これでXORを0にして返せる
これにより、XOR != 0の状態からXOR == 0にして返せることが分かる
これによって、開始時のXOR結果が0であれば、Aは必ずXORを0でない形で返さねばならず、Bが最善策をとれば必ずXORを0にして返すので、Bが最後にXORを0にして勝ち。一方で、開始時のXOR結果が0でなければAの勝ちとなる
つまり石を動かしてアレコレやる必要もなく、最初の石の山の状態でどちらが勝つか決まっている これを考えてプログラムを書いてやればよいことになる
python3で数字を二進法表記した結果を用いて演算してくれる演算子（ビット演算子）は、&、|、^がある
a&bはa,bを二進数に直してどちらも1なら1,異なっていれば0を返す
例えば11&14 == 10である
11,14は二進法に直すと1011,1110なので、両方1を持つ桁を1、そうでない桁は0とすると、1010となり、これを十進法に直せば10だからである
a|bは、二進法に直したとき少なくとも1つが1なら1を返してくれる
11|14 == 15 (1011と1110なので1110と返ってくる）
a^bが今回使うXORで、異なっていれば1、同じなら0を返す
11^14 == 5 (1011と1110なので0101が返ってくる）
紹介が終わったところで答えのコードを書く
n = int(input())
L = list(map(int,input().split()))
S = 0
for i in range(n):
S ^= L[i]
if S != 0:
print('A')
else:
print('B')
これだけ 単純だね かんたん わいわい
DPまとめコンD
たぶん一番基本的な問題 いろいろ言う前にもう答えを覚えちゃった方がよさそう
重さについてのDPを使って解くのが素直
与えられた品物の個数をN、重さの制限をWとする (N+1)*(W+1)のリストdpを作ってあげる（品物の番号は0インデックスなので0~N-1)
dp =
for i in range(N+1):
dp.append([0 for _ in range(W+1)])
縦の番号には0~Nが入り、横には0~Wが入る
それから、i番目以降の品物から重さの総和がj以下になるように選んだ時の価値の最大値をリストの中に順次入れていく
（重さと価値のデータはwvというリストに入れることにする）
リストの下の方から埋めていく
まず、リストの一番下は、N番目以降の品物を選ぶことになるので、品物がN-1番目までしかない以上は選べないので0で埋めていくしかない（すでに0で埋まっているので放置）
それから、(N-1)~0番目について、i番目以降の品物を選ぶ際のアルゴリズムは
for i in range(N-1,-1,-1): #N-1から0まで逆順に見ていく
for j in range(0,W+1):
if j < wv[i][0]: #wv[i][0]が制限重量をオーバーしていたら
dp[i][j] = dp[i+1][j] #その品物は入らないのでdp[i+1][j]がそのまま入る
else:
dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1]) #w[i]を入れるかどうかを判定する
ために、それを入れた場合と入
れなかった場合とを比較する
print(dp[0][W])
これでいける
いけませんでした 言語的な問題がありそう 計算量が10**7で、ここまでくるとpython3は厳しいのかもしれない numpyをお勉強する必要があるかもしれない
