SRM624Div1Easy
問題
サイズN()の数列が与えられる。任意の要素に数字を足していくことで同じ値の要素を増やしていく。同じ値の要素数をiとし、その要素数を作るのに必要な最小な値を
とする。
の全要素でのXORの値を求めよ。
解法
愚直に全探索を行うととなる。
はある要素に注目した際にi個(
)の同じ要素を作るための値を探索するのにかかる計算量である。これを全要素に対して行うので
となる。時間計算量ではこれで問題はないが、メモ化をする必要があるため空間計算量で制限を超えてしまう。
全ての要素を保存しつづける必要はないが、計算量を削るために前回の値は記憶しておかなければならない。必要なのは一つ前の情報だけなのでに削減することができる。
計算量
時間計算量: O(N^2)
空間計算量: O(N)
