解説
巨大な整数を 進数で表し、 でない桁のみを連想配列で管理します。
加算に伴う繰り上げでは途中の桁が になるため、繰り上げを含めた桁の更新回数は償却 回です。一方、減算では繰り下がりが非常に多く発生する可能性があります。
そこで、減算を加算に置き換えることを考えます。
閾値 に加えて、 を管理します。実際のキャットフードの個数を として、
- のとき、 に を加える。
- のとき、 と の両方に を加える。
とします。
このように管理すると、各クエリの直後に なら byebye, neko!、 なら byebye, world! となります。
巨大整数の比較は上位の桁から順に行うことで、 時間で実行できます。
よって、全体の時間計算量は となり、十分高速です。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。