ARC144
まとめ
A, B が解けたけど、ペナ込みで87分程度。レート的にはマイナスでした。
これでも 1,000 程度のパフォーマンスは貰えるので慈悲を感じる。ありがたい。
A - Digit Sum of 2x
結構苦手なタイプの問題。
2倍にしたときに繰り上がりが発生するような $ x の選び方をしても答えからは遠ざかりそうな気がしたのですが、ここらが未証明というか体感でなんとなく、でしかないので10分ほど価値のない雑な検証を繰り返していました。
思い切って提出したらACだったので、迷わず出せば良かったやつ。でもアホみたいにWAを出すよりは良いのかなー。
こういう時に数学的な手順で証明が使えるとよさそうなのですが、その辺は勉強が足りていない。
B - Gift Tax
直感的に解けそうな感じがする問題。
$ a = b の場合、おそらくは全ての数値を全体の平均値に揃えられる。 $ a < b の場合、平均値よりも小さい値で落ち着きそう、ということはわかる。
数列をソートして、「平均値より小さい値の差分合計」「平均値より大きい値の差分合計」をとっておくとよさそう?
ただ、それらをとっておいてもどういう計算をすれば答えを求められるがいまいちわからなかった。
「平均値」にこだわっていたけど、これを予め決め打った答えにすれば良いのでは?と後から気づく。
そこからは二分探索の実装に上手く切り替えてACを得た。
これは15分くらいで解きたい問題だったなー。
C - C - K Derangement
サンプルの出力を見る限り簡単そうに見えるけど、そんな簡単なわけないのですシリーズ。
とりあえず K の分だけスライドした数列を出せばサンプルが通りそうなので、それだけやってみたけど当然WAでした。
その後は「使える数字」「使えない数字」をそれぞれ #平衡二分木 で管理して、なんかいい感じにできないか試行錯誤していたのだけど、時間切れだった。