htkb-proconの日記

初心者がPythonで問題解いた記録

DP

Educational DP Contest S - Digit Sum 桁DP

めんどくさすぎるイメージを持っていた桁DP、久しぶりに遭遇して解いたら割とソラで書けたのはいいけどTLEで、考察したらそもそも無駄に配列の次元を深くしたりしなくていいんじゃないの??と思ったので書き残してみる。 桁DPの状態遷移はこのように上の桁…

CODE THANKS FESTIVAL 2018 E - Union

E - Union 解説見てもDPの回し方にしばらく悩んだのでメモ。 dp[i][j] := 整数i-1まで余りなく処理したとき、iにj個持ち越した場合の数 って感じの流れは思いつけたんだけど、なーーーーんでか各iを1個残した場合と全部使い切って次に回す場合の場合分けって…

ABC054-D DP

D - Mixing Experiment DPやるだけの400点問題なんだけど今更こんなのでハマってしまったので忘れないように記す。 2種類の物質がa:bで混じっているc円の薬がN個あるので、これを好きなように混ぜてなるべく安く指定の比率を実現したいという問題で、制約も…