Typical DP Contest H.ナップサック
昨日ABC161がありましたが、まあ酷くやらかしました笑
最近Typical DP Contest(以下TDC)を解き続けているせいで、D問題を桁DP&決め打ち二分探索の問題と思い込んでズブズブと沼にはまっていきました。。。
こういう時に引き返すのが苦手なの、どうにかしたいです。
表題の通りTDCのH問題を解きましたが、だいぶ変なところで引っかかったのでその備忘録です。なのでH問題自体の解説はしません。
1. 多重for文の順序
H問題において、物の色は単調に出現するようソートしたとしてdpのキーは
dp[i][b][c][w] = (0からi番目の物の中からc色以下、重さw以下になるよう選んだ時の価値の最大値、ただしb=0→i番目と同じ色を詰めない、b=1→i番目と同じ色を詰めた)
と定めますが、このときdpを回すための多重forの順序の組み方で速度に２倍ほど差が出ます。
- for c → for w → for b の場合、2117ms
- for b → for c → for w の場合、1107ms
別に共通の処理をfor文の外に出したわけでもないのに、単純にfor文の順番を変えるだけで速度が変わるのは不思議です。
予想としては、前者はb=0, 1のみなので頻繁にbについてのfor文の内外の行き来が起こる一方、後者はfor w in range(W)が大体W=10^4なのでwについてのfor文の内外の行き来はそんなに起こらないから、なのですが、識者がいらっしゃればぜひ教えてください。。。
とりあえず「多重for文は回数が多いものほど内側にネストするのが良い」として覚えておきます。
2. numpyでのmaxの取り方
何を血迷ったか、H問題をnumpyで書き直しました。その時dpの遷移でmax評価を何度も取る必要があるのですが、
- np.max(-) → １つの行列内での要素の最大を返す
- np.maximum(-, -) → ２つの行列の各要素のうち大きい方を取って作った行列を返す
なことに注意です。さらに後者は引数が２つじゃないと正しい行列を返さない事を忘れないようにしましょう（エラーも返さないのでここで相当詰まった）。
引数３つ取った時帰ってくる行列が何なのかはちゃんと調べてないです、これも誰か知ってる人教えてください。。。
