おはようございます。しほみんです。
まじでB問題でさえやらかした回です。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは900程度になりました。緑維持、水色を目指します。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在51回参加、ほぼ1年。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はAB、20分(4WA)でした。C問題解きたかったですね....こういう累積和は理解できなかったわけだったので....パフォーマンスは474で久々の茶色です。レートも 935→894で下がりました。B問題もあほみたいな勘違いしていたのでやらかしました。
今回はC問題まで振り返ります。
A問題
彼の名前はS（3文字以上20文字以下）です。
ニックネームとしてどこか連続する3文字にしたいです。
ニックネームを出力しなさい。
普通に頭から3文字出せばよいです。C#ではSubString(0,3)で出力できます。
どこかといいつつ、実はどの条件でも頭3文字出せばよいってことに気が付くのがコツです。
B問題
鬼役の子供は座標Aにいて、1秒当たりV移動します。
逃げているの子供は座標Bにいて、1秒当たりW移動します。
両方の子供が最適な動きをしたとき、T秒以下で捕まえられるか判定してください。
まず、絶対的な座標差は|A-B|です。
そして、1秒間でV-Wだけ距離を縮められます。
よって、(V-W)Tの座標差を最大縮められます。
なので、|A-B|>(V-W)Tなら逃げ切れるし、そうじゃないならつかまります。
普通に単純ですね.....
自分は何を勘違いしたのか。座標0をまたぐと+1するとかよくわからんこと考えてました....普通に要らないです....（こういう自分では絶対にあっていると思って勘違いしているとWAも増えるし時間も食う絶望です....今後はもうしたくない...）
C問題
電球がN個あります。
始めの電球の強さはそれぞれAiです。
電球の強さがdのとき、座標iにある電球はi-d-0.5からi+d+0.5の範囲を照らします。
そして以下の操作をK回やります。
それぞれの座標iを照らしている電球の数を電球の強さとしてBiで置き換える。
このとき、K回やった後のそれぞれの光の強さを求めなさい。
うーんまあ言っていることがまず理解しにくいですよね...
ただ、この光の強さは実際に電球の状況を考えないとわからないという点から、
・簡単に照らされている電球の数を把握する必要がある
・ただ、K回もやってしまうと多分だめだ
ということは考えるところです。
前者の電球の数の把握は普通にやるとo(Nの2乗)になって間に合いません。
よって、o(N)になるよ宇にしないとなりません。
つまり、頭から電球の照らす位置を記録して考えていくことをかんがえます。
このときは累積和を使えばよいです。
ある電球の照らす範囲をL～Rまでとして、
電球が照らしているときを1、そうでないときを0としてBの配列に格納するとき、
B[L] = 1, B[R+1] = -1として、
B[i + 1] += B[i]をしてやるとできます。
つまり、電球範囲内のうちは全部1を出して、その範囲外になるとき-1してやれば、0になるので、無事o(N)で把握できます。
これを先にすべての電球で1とか-1とかやっておいて、最後に足せば、1回の操作でのBiは出てきます。
ただ、これはo(N)で、K回やってしまうとo(NK)でアウトです。
そこで、これを何回やればよいか考える必要があります。
なんとも、言葉で表現しづらいのですが、一回やると必ずどの光の強さも1以上になります。
すると、必ず隣同士の電球は必ず影響を受けることになります。
そう考えると2回目はどんなに考えても2か3です。
3回目も影響範囲がさらに増えていくので、3-7とかまで拡大します。
つまり、回数を重ねていくと、倍々ゲームのように増えていきそうだなあって感じです。そうすると、どの位置でもNになるには、（2のx乗）程度最大やればよくなります。そして、それ以降変化しないので、ここに達したらおしまいとします。今回、Nは10の5乗程度なので、50回もやれば十分ってことになります。（ただイメージなので厳密な証明ではないことに注意です。）
ということで結局、o(50×N)が最大計算量で、十分間に合います。（もちろん、毎回事、全部満たしているか確認しても十分間に合います）
実際に実装では、1回の動作を累積和で求めて、基本はk回やるようにしてますが、kが50回になったら打ち止めとしています。
最後に....
やっぱりARC相当のC問題は考えることが多いですね...ただ、いくつかの基本的なことに組み合わせなので早く思いつくようにしたいですね
ではでは。
