AOJ1626 - 超高層ビル「みなとハルカス」
解法
解の候補について、フロアのうち最下層の階数を、フロアの総数をとします。すると、の階を借りることになるので、料金は次のようになります。
これがと一致するので、結局
という条件が成り立つことになります。
を1つ固定すると、は式変形によって簡単に求めることができます。
これが正の整数になるかどうかを確認して、あとはが最も大きくなるようなペアを探せばよいです。
の列挙は、で行うことができるので(からを取り出し、がで割り切れるとき、およびがの候補になります)、これを全部調べればよいです。
感想
久々にAOJをやりました。が、実装系というよりかは数学系でした。
この問題は2018の国内予選のC問題で、自分のチームはほかの2人が通したものです。
当時もし自分が解いていた場合、解けたんでしょうか…?
思考の過程としては、ひたすら式を組み立てて何か条件がないか、と探しただけです。このレベルのの変形は、まだ自分の頭にも残っていたので、割とささっと解けました。