ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ1626 - 超高層ビル「みなとハルカス」

問題
提出コード

解法

解の候補について、フロアのうち最下層の階数をa、フロアの総数をcとします。すると、[a,a + c - 1]の階を借りることになるので、料金は次のようになります。
\displaystyle \sum_{k=a}^{a+c-1}k = \frac{(2a+c-1)c}{2}
これがbと一致するので、結局
(2a+c-1)c = 2b
という条件が成り立つことになります。
cを1つ固定すると、aは式変形によって簡単に求めることができます。
a  = \frac{\frac{2b}{c} - c + 1}{2}
これが正の整数になるかどうかを確認して、あとはcが最も大きくなるようなペアを探せばよいです。
cの列挙は、O(\sqrt{b})で行うことができるので([1,\sqrt{2b}]からiを取り出し、2biで割り切れるとき、iおよび2b/icの候補になります)、これを全部調べればよいです。

感想

久々にAOJをやりました。が、実装系というよりかは数学系でした。
この問題は2018の国内予選のC問題で、自分のチームはほかの2人が通したものです。
当時もし自分が解いていた場合、解けたんでしょうか…?
思考の過程としては、ひたすら式を組み立てて何か条件がないか、と探しただけです。このレベルの\sumの変形は、まだ自分の頭にも残っていたので、割とささっと解けました。