課題が終わってなかったので早起きした。今夜もあまり眠れなさそう。

---

荒れてた肌がようやくほぼほぼ完治した。まだちょっと治りたてでかさついている部分もあるが、許容範囲だ。

---

今日解いた競プロの問題。

ARC139-B: 解説AC。頭の中に全くなかった発想だった。解説読んだうえで理解するのに数十分要した。

以下、簡便のために1増やす操作を操作S, A増やす操作を操作T, B増やす操作を操作Uとする。操作TとUは対等なので、適宜入れ替えてTの方がコスパが良いもしくは同じものと仮定できる。(Y/A≦Z/B)

まず、Sが最もコスパが良いならば全部Sで済ませるのが一番良い。また、T>S>Uの順でコスパが良いなら、出来る限りTをしてあとはSで済ませるのが一番良い。ここまではさすがに自力で分かった。問題は、TもUもSよりコスパが良い場合。

操作Sの回数をs、操作Tの回数をt、操作Uの回数をuとする。$N=s+tA+uB$となる。

$tA\leq N$なので$t\leq \lfloor N/A \rfloor$である。また、$u\geq A$ならばA回やる分の操作Uを操作TをB回やるようにした方がコスパが良い(もしくは同じ)はずなので、$u\leq A-1$とできる。これは自力では気づけなかったが、言われればまあ分かる。この問題の肝はここから。

tとuそれぞれを上から押さえることができたが、どちらに注目するにせよ最大で$10^9$オーダーになってしまう。しかし、$\min(t, u)$を見るとなんと$O(\sqrt{N})$で押さえることができるのだ。

$\min(t,u)\leq \min(\lfloor N/A \rfloor, A-1) \leq \sqrt{N}$となる。$N/A$と$A$のどちらかは$\sqrt{N}$以下でしかない。そこで、tとuどちらか都合のいい方を見ることにすれば$O(\sqrt{N})$で解けるのだ。頭良すぎる。$\lfloor N/A \rfloor \leq A-1$ならばtを$\lfloor N/A \rfloor$まで見れば良いし、$\lfloor N/A \rfloor \geq A-1$ならばuを$A-1$まで見れば良い。どちらか都合の良い方が押さえられていればよいという発想はなかった。正直この知識を使いこなせるか不安だが、かなり勉強になった。

ちなみに、どちらの場合にせよ$p=0$と$q=0$を明示的に探索しておかないとWAになる。なんでだか良く分からない。