Y箱

数の各桁の数を二乗した和を並べた数が89でループする場合を数える問題です。

操作からすると、345と435と543などの同じ構成の数は同じ結果になるので、それをうまく使えばメモ化で速くなりそうなので、やってみた。

数を数列にしてソートする。0はなくても同じなので除外する。そうしてできた数列で判定する関数を作ってメモ化する。

解けたんだけど、遅い。

ふと、元の数をつくるのにどれくらいかかるか計算してみたら、それだけで2分近くかかってる。こりゃだめだ。 どうしよう。