122C
解法としては累積和でOK。
ただし少し工夫が必要で、ACの状態が確定した時点で累積和する。
確定した状態で累積和することで、普通の累積和と同じように扱うことができる。
今日は自分の苦手分野を伸ばしていくようにしたいので問題を解くことはあまりせず、理解度を上げていきたい分野をより詳しく学習することにする。
目に見えるだけでも不完全に理解している分野が多くある。
・累積和
・imos法
・グラフ
・dp
まだ完全ではないがサラッと思いついたのを書くだけでもこれだけある。
何となくどれも何となく問題解いたことがあり、基本中の基本問題くらいなら解けるものだが応用が問われた時や、実装の重い問題が来た時に大体バグらせて解けない。
バグらせるのは実装力のなさ、デバッグ力のなさでもあるので、その辺の部分も考えていきたい。
以下、学習したことを自分でまとめる。
累積和
まず、現状の理解
累積和自体は単に配列の一番左からi番目までの総和を記録しているに過ぎない。
だが、これを利用することで元のデータではできない便利なことが行える。
それは、L番目からR番目の総和をO(1)で取り出すことができるという点。
これを元の配列でやろうとするとO(N)かかり、クエリ処理などをする場合O(NQ)かかってしまう。
累積和の場合、一度前計算O(N)を行えばあとはR-Lで求めることができる。
累積和の難しいのがそもそもどういう仕組みなのかというのと+-1(開、閉区間)の理解。
それは、L番目からR番目の意味を考える必要がある。
L番目からR番目ということは配列の数で言えば、R-L+1個である。
なぜなら、L番目もR番目も"含まれる"から。
逆にL番目を含まず、R番目を含むような場合はR-Lで良い。
整理すると
-LならばL番目までは引かれる、つまりL番目は答えに含まれない。
-(L-1)ならばLの1個前まで引かれる、つまりL番目は答えに含まれる。
コーナーケースを考える
もしL番目からR番目の総和を求めよ
L=0,R=max
だった場合、Lを含むはずなので-1を求めたいが配列外参照になってしまう。
一つはどうせLとRは1-indexのことが多いので、0番目に0を置いてしまう。
そうすれば同じ処理で完結できる。
もう一つは、0だけ例外処理を行ってRの値を出力するという方法もある。
どちらの方が良いかは、個人的には前者でやったほうがバグらせにくいのではないかと思うのでなるべく0インデックスでやりたい。
上記のC問題も、どこで累積してどこが引かれるのかが分かっていればすぐ解けたのではないかと思う。
二次元累積和は軽く調べてみたが微妙に理解できてないので後回し。
imos法
考え方としては、累積和に近くて前処理してそれを足し引きしてO(1)で求めようみたいな部分は一緒。
簡潔に言えば累積和のパワーアップバージョンみたいなイメージで簡単な問題では、ある店に客がN時からM時まで滞在していて、L時～R時の間に何人いるかみたいな問題の時に入ってきた時間と出る時間を加味して、累積和を求めることでL時からR時に何人いるか求められる。
つまり入ってきたときに+1,出るときに-1して累積和をすればよい。
これも二次元以降はまだ理解してないので後日。