3完1WA。
コンテストで600点問題通したのは(記憶が正しければ)1年8ヶ月ぶりくらいらしいです。青パフォも今年初めて。
各問題
A - Digit Sum of 2x
x + x
が繰り上がりの発生する'x'だったときと発生しない'x'だったときを考えると、前者のf(x) <= 後者のf(x)
となります。よってMを最大化するという条件下では後者を採用すべきです。
上記条件を満たす最小の'x'は先頭が(N*2)%4
で(0になるときは省く)あとに(N*2)/4
個の4が続く数値です。
このときMはもちろんN*2になります。
B - Gift Tax
伝家の宝刀二分探索をやるだけです。
候補の数Mに対して、Mより小さい数字に何回aを足さなければならないかと、Mより大きい数字から何回bを引けるかを求めて、前者が後者以下ならOKです。
ただし、a>b
のとき、Mより小さい数字にaを足した後bを引く余地ができる可能性があることにだけは注意です。
これ考慮する必要ありませんでした。制約がa <= b
でした。
C - K Derangement
なんかごにょごにょしてたら通った!!
一応実装内容ですが、Kより大きい数字を先頭から順に敷き詰めて、後の数字はリザーブしておきます。
で、(0-indexedで)K番目から入っている数をチェックして、それが後ろに持っていけてかつリザーブの中で一番小さい数がそこに置ける場合、リザーブのものをおいて、もと置かれていた数はリザーブに回します。
最後にリザーブに残ったままのものをうしろに並べます。
なんでそれで通るのかはよくわかりません!!!
まとめ
C、通ると思わず投げたら通って声出た。