問題
要素数20の数列が与えられる。各要素は1か0である。すべての要素を0にする。ただし、注目点と隣接する要素は同時に反転される。
解法
反転される一番左の要素に注目する。各要素を見ていき1なら反転させる。ひとつめの要素に関してはそのままでは決定できないので、左にひとつ余分な要素を追加することで2パターン探索する。
計算量
N:与えられる数列の要素数。
要素数20の数列が与えられる。各要素は1か0である。すべての要素を0にする。ただし、注目点と隣接する要素は同時に反転される。
反転される一番左の要素に注目する。各要素を見ていき1なら反転させる。ひとつめの要素に関してはそのままでは決定できないので、左にひとつ余分な要素を追加することで2パターン探索する。
N:与えられる数列の要素数。