ABC128_D – equeue
問題
提出
感想
1回目
考えるのに時間はかかったが解けた。
dfsやdpを考えていたが、うまくいきそうになく、全探索をするとうまくいった。
dfsの場合は全通り試すと$4^K$乗になる。$4^{100}$は$10^{60}$ほどあるので全然間に合わない。
操作を行えないパターンは枝刈りできるが、これでも計算量はまだ膨大になる。
例えば、操作が$A,B$のみだとしても$2^{100}$程度ある。
なので、dfsではTLEする。
dpの場合はそもそもdpの遷移式がわからなかった。
問題文をよくみると、$N,K$が小さい。
なので、全探索を考えてみる。
例えば、$A,C$の操作のみを考える時、$A,C$の個数にのみ答えに作用し、順番は関係ない。
例えば、10個取って5個詰める場合、明らかに10個取った後に5個詰める方が価値を最大化できる。
これは$A,B,C,D$の操作があった時も同じで、先に$A,B$の操作を行った後、価値の低いものを詰めた方が価値を最大化できる。
そこで、$A,B$の操作回数を$i$とする。$i \in { 0 \le i \le K}$である。
$A$の操作回数を$j$とすると、$B$の操作回数は$i-j$回になる。
操作回数が$i$の時、$j$のパターンは$j \in { 0 \le j \le i}$になる。
よって、宝石を取るパターンは$O(K^2)$になる。
$A,B$の操作回数が$i$回の時、宝石を詰める操作mは$m=K-i$回までになる。
$A,B$の$i$回の操作で得た宝石の中で、小さい順に$m$回詰めれば良い。
ただし、価値がプラスの宝石は詰めない。
詰める操作は、$i$個の宝石をソートして、小さい順に$m$回見れば良い。
ソートの計算量も合わせると、$O(K^3 \log K)$となる。
コメント