おはようございます。しほみんです。
先週は参加しませんでしたが、一応復習で書きました。というか発想自体はできてもちゃんと書けないなって感じで反省ですね...（答えとか見てたのに結構WAを出してた）
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。緑中堅へ。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はE>C>D>B>Aの難易度かなあと思います。というか全体的に発想が単純だったので、きちんとやるのが楽かどうかって感じでした．Cは場合分けが面倒ですね...
今回はA,B,C,D,E問題を解説します。
ここから問題です。問題は簡潔に書いています。
問題A
twiblrでは2×（フォロワー数）＋100を超えない範囲でフォロー数を増やせます。
あと何人フォロー数を増やせますか？
フォロー数をA,フォロワー数をBとすると、
2*B+100-A人まで増やせます。よって、これを出力します。
問題B
数列A（A1,A2,A3,....,Ａn)があります。
Aの中で、kで割り切れるものの数をgcd度とします。
この時のgcd度が最大になるモノを求めなさい。
まあ、普通にkの候補は2から1000までなので全部、実際にAの中で割り切れる数を数えて最大値を出せばよいです。
今回は、Nは最大でも100で、kとして考える範囲も1000です。
よって、o(Nk)でも十分に間に合います。
判定は、Ni % k ==0で判定できます。間違えて、最大の数を出さないように注意しましょう。
問題C
数が与えられます。桁の文字を消して3の倍数にしたいです。
幾つ消せばよいか出しなさい。ただし、全部消えてしまう場合は-1を出力しなさい。
まず考えるのは3の倍数である条件です。
これは有名で、各桁の和が3の倍数になることです。
よって、3の倍数になるように消せばよいのです。
消す数が3で割って余りが1か2になるので、把握する必要があります。
ただし、例外的に、11や22といった、2桁以下の数で、桁の余りが1か２のときしかないときは-1です。それを省きます。
なので、
1.各桁で3で割ったあまりを求めて、それぞれの数を数えます。この時、例外条件は-1をだします。
2.各桁の総和を求める
3.これを3で割ったとき、あまりが0なら、0を出力します。あまりが1なら、あまりが1の数があれば、1を出力。それ以外なら2を出力します。あまりが2も同様です。
3のところをうまく組み立てるのが結構厄介です。この場合が一番いいです。
余りの数をそれぞれ場合分けしてしまうと、つらいことになります（というか自分がここでツボにはまった）
D問題
あるロボットは、
・正の方向にA1に進む。
・正の方向にA1に進み、その後正方向にA2に進む。
・正の方向にA1に進み、その後正方向にA2に進み、その後正方向にA3に進む。
というように、N回繰り返します。
この時、ロボットの最大位置を求めなさい。
もんだいは、Aiはマイナスもあることです。
ということでどこに最大があるかわかりません。
なので、1回ごとの動作で、取りうる最大値を把握する必要があります。
このとき、いちいち足し算して求めていたら、o(Nの2乗)で時間が足りません。
よって、累積和を使って工夫します。
累積和を1からiまでの進み方の和とするとo(1)の時間で、n回目までの動作が取れます。
そして、一番肝心なのですが、
n回目の動作中で最大値になるのは、1からn-1回目までの和に、1からn-1回目までのときの最大値を足したものになります。
（n回目の動作中で、1からn回の移動は行うから各自の検討は必要。）
しかし、前もって、その移動は計算されているので、その最大値だけを保持しておけばよいです。
つまり、
1. 1回目からN回目までそれぞれ動作したときの和を累積和で残す。
2. 最初に、1回目の動作を足しておく（sum)。また、移動の最大値を求める（maxは0にする）。答えはansで、ans =Max(0, sum)で求める。
3. 1からi回目までの最大値を求める(max)。sum+maxとansで比較して、最大値を保存。
sumに累積和を足す。
4. 3をN回繰り返して、出力になります。
問題をパッと見て、これは累積和だと思えたら結構な実力だと思います。そのあと、いかに素早く組み立てられるかがカギです。
問題E
H列W行の迷路があります。
N個の明かりと、M個のブロックがあります。
明かりは、4方向にブロックが当たるまで照らされます。
この時、この迷路が照らされる数を求めなさい。
よく見る明かりの問題です。
今回は、結構単純に解けます。
まずは、迷路とブロックの位置を記録します。
そこから明かりを投入していって、どんどん必要な範囲を照らしていくだけでよいです。
ただし、一つ工夫があって、それを縦方向か、横方向に絞って行います。そうすることで、もしすでに照らされていたところに明かりが入れば、それはすでにダブっているので数える必要がなくなるからです。
そのため、検索自体はo(HW)の時間で済み、ほかのNやMの読み込みも併せて、
o(HW+N+M)となります。
まあ実装では、とりあえず全部の光源で光る部分を求めて、最後に出力するとよいです。
E問題としてはかなり素直なのできちんと解きたいところです。
最後に....
このセット当日解いたらぜひ取りたい感じでしたね....来週はどうなるやら...
ではでは。
