ABC035 C (いもす法)
いもす法
いもす法聞いたことがあるだろうか。私はこの問題で初めてであった。多次元でもできるようが今回は一次元での問題なので理解することができた。
解説こちらのAtCoderの公式解説を見るのが一番わかりやすかった。(他のサイトも探したが次元の拡張が起こっておりこの問題のレベルを越していた)
すごく簡単に説明すると配列の3から7まで要素に対して４を加える操作をする時にわざわざ3~7までの5個の要素に対して+４するのではなく最初の3に+4しておき最後の7の次の数字８番目の要素に-4しておく考えだ。
最終的には累積和をとって答えを出す。配列の５番目の要素の数字がいくつか聞かれた際には、和をとるので配列の1番目から(1index)5番目の数字の全ての和が答えとなる。
言われてみればそうだなとい感じだが実際に知らないとかけないやり方であった。
今回この問題にあえてよかったと思う。
