Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 144

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

なんかごにょごにょしてたら通った!!

atcoder.jp

一応実装内容ですが、Kより大きい数字を先頭から順に敷き詰めて、後の数字はリザーブしておきます。

で、(0-indexedで)K番目から入っている数をチェックして、それが後ろに持っていけてかつリザーブの中で一番小さい数がそこに置ける場合、リザーブのものをおいて、もと置かれていた数はリザーブに回します。

最後にリザーブに残ったままのものをうしろに並べます。

なんでそれで通るのかはよくわかりません!!!

まとめ

C、通ると思わず投げたら通って声出た。