AtCoder Regular Contest 057 C - 2乗根

問題

　 $\sqrt{N}$ の上 $k$ 桁が $a_1 a_2 \dots a_k$ となるような最小の正整数 $N$ を求めよ。

解法

　解説そのまま。

　10進法で $a_1 a_2 \dots a_k$ と表記されるものを $A$ とする。 $\sqrt{N}$ の上 $k$ 桁が $A$ となっていることはある整数 $t$ が存在し $A^2 \times 10^{2t} \le N \lt (A + 1)^2 \times 10^{2t}$ と同値。

　 $t = n$ でこの条件を満たす正整数 $N$ が存在する場合、 $t = n + 1$ ではより範囲が広がるのでやはり正整数 $N$ が存在する。また $t = n$ で条件を満たす $N$ が存在しないと $t = n - 1$ でも存在しない。よって $t$ を大きいほうから考えていき条件が満たされない状況になるまで小さくしていけば良い。

　これを整数の範囲で考えるので下限は切り上げ、上限は切り下げで考えていくと上手く範囲が取れる。

反省

　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)