yukicoder No.634 硬貨の枚数1

#278149 No.634 硬貨の枚数1 - yukicoder
真っ先にDPを考えるも制約から空間的にも時間的にも不可能でお手上げ.
解説を見る.

任意の自然数は高々三つの三角数の和で表すことができる. より一般には多角数定理というものがあるようです.
多角数定理 - Wikipedia
『高々3つ』であるので, 1つだけや2つだけでもいいことに注意です. 例えば三角数自体が三角数１つで表せます.
これを利用すると, 答えは一気に3か2か1に絞り込めます.
答えが1になるときは, 入力が三角数だったときです.
答えが2になるときは, 入力が2つの三角数の和だったときです.
答えが3になるときは, 入力が3つの三角数の和だったときです.
これらは排反な事象なので, 楽な1,2のときを探索してそれ以外は3を出力することにします.
あらかじめ三角数の配列を計算して持っておきます.
1のときの判別は, 入力された文字が三角数の配列内に入ってるかどうか調べればよいです. 制約から三角数は高々O(\sqrt{N})個であるので, 線形探索しても間に合います. 二分探索してもいいです.
2のときの判別は, 三角数の配列をt[]とし, 各iについて, N-t[i] = t[j]なるjが存在するかを探せばよいです. これも二分探索できます.
1,2でもないときは3を出力して終わりです.
全体の計算量はO(\sqrt{N}\log N)となります. 前処理などいろいろ考えると実質定数ですが...
#278149 No.634 硬貨の枚数1 - yukicoder