484.1

250

整数xの各桁の数字を足したときの和をs(x)とするとき、s(x)*s(x)=s(x*x)なるxはいくつあるか求めよ、という問題。

キャリーが出るとおかしくなるらしいので、各桁の数字が3以下のものについて全探索するだけらしい。x*xの上限が10^18程度なので、xの各桁の総和が13程度ということから全探索するのも可。

550

見てない。

950

N個の整数をM個と残り、という風に分ける。何回行えば、N個の整数それぞれが異なる分かれ方をするか答えよ、という問題。

情報量の問題。半分ずつ分けるのであれば1回で1ビットの情報量があるのでNのビット数だけ分ける。そうでない場合は...、という感じ。logを使えば近似解は得られそう。