問題
の上桁がとなるような最小の正整数を求めよ。
解法
解説そのまま。
10進法でと表記されるものをとする。の上桁がとなっていることはある整数が存在しと同値。
でこの条件を満たす正整数が存在する場合、ではより範囲が広がるのでやはり正整数が存在する。またで条件を満たすが存在しないとでも存在しない。よってを大きいほうから考えていき条件が満たされない状況になるまで小さくしていけば良い。
これを整数の範囲で考えるので下限は切り上げ、上限は切り下げで考えていくと上手く範囲が取れる。
反省
1時間44分(1WA)でAC。数が大きすぎてまともに扱えないので桁DP的な感じで決定していくのかとか、桁数に対する二分探索とかいろいろ考えたけど結局わからなかった。多倍長整数を使うとできるということを考えもしなかったのがひどいが、他の人の解法を見てもなんでこれで上手く範囲が取れているのかいまいち理解ができない。
C++でやるなら#include <boost/multiprecision/cpp_int.hpp>
としてboost::multiprecision::cpp_int;
を使えば良いらしい。環境がないのでPythonで実装をした。
コード
AtCoderでコードを見るとC++の文法を前提としているからかPythonの切り捨て除算//
がコメントアウトっぽく表示されて非常に見にくい。
a = int(input()) b = a + 1 a = a * a b = b * b - 1 while (a + 99) // 100 <= b // 100: a = (a + 99) // 100 b //= 100 print(a)