おはようございます。しほみんです。
先週復習で来てなかった、競技プログラミングについて振り返ります。手法が分かっても実装が分かってない（つまりわかってない）ので、普通に落としました....
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。最近下がり気味....（勉強不足）。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回は、ABD、60分でした。C問題焦って実装思い出せず死にました。D問題は超簡単だったので先に解くべきでした。E問題も二次元累積和だろうなと思ったのですが、累積の部分の実装ができませんでした。レートは微減でして、1000割りました。
わかっていても解けないって壁をどう打破するかが今後の課題ですかね...。
今回はA,B,C,D,E問題を解説します。
ここから問題です。問題は簡潔に書いています。
問題A
ReLU関数を表せ。
ReLU関数は0以上は入力値、それ以外は0です。
よって、入力が0未満なら0、それ以外なら入力値を出せばよいです。
問題B
ビリヤードの問題です。
（Sx,Sy)の位置から一回反射して、(Gx,Gy)の位置に当てるにはどの位置で反射すればよいでしょうか？
反射するってことは、当たる壁面を鏡面とした、(-Gx,Gy)と(Sx,Sy)の直線と鏡面の好転を求めればよいです。
答を(0,b)とすると、直線の式から、
Gy - b = (Sy - Gy)/(Sx + Gx)*x
なので、
b = Gy - (Sy - Gy)/(Sx + Gx)*x
で求めればよいです。double型で十分精度が出ます。
問題C
町1から出発して、町2からNまでを巡って町1に戻ります。
町の間の距離が与えられます。
それぞれの回り方で、距離Kとなるのは何通りですか？
町の周り方は(N-1)!通りです。
よって、すべての回り方に対して、調べれて該当する数を出します。
それで、町の回り方ですが、普通にはnext_permulationをやります。
順列の全通りを列挙するアルゴリズムです。
しかし、自分底カバーしてなくてDFSでやりました。ただ、DFSの構図を忘れていて思い出すのに苦労して解けませんでした。
ただ、DFSだと、重複を含めた全通り出てしまうので、重複が出たときは何かしらの対策でカバーしておく必要があります。今回は、とりあえず出して、そのできた順列からかぶってないか検証しました。
まあ今回はこれで間に合いましたが、明らかに計算量が無駄なので今後は、next_permulationですね....
D問題
給湯器が1つあって、毎分Wリットル供給可能です。
N人の人がいて、SiからTi(Ti秒目は除く）まで、Piリットル使おうとしてます。
これは、供給可能ですか？
まあ、すべての秒数に対して、それぞれのN人のケースをふかしていってお湯の量を毎秒調べればよいのですが、それではo(NT)が最悪になって、普通にTLEします。
なので、毎秒毎秒できないか考えます。
そこで累積和を使って考えます。
基本、T+1秒ではT秒からの変化を見ればよいのです。
すると、Si秒目でお湯を使うということで、+Piしておきます。
そして、Ti秒目では使い終わるので、-Piしておきます。
そうすると、Si+1から、Ti-1秒目までは、その1秒前を常に引き継げば、その人がお湯を使い続けていることになります。
これをN人であらかじめ記録しておいて、同じことをすればよいです。
ということで、
1. 200000秒目までの配列qを用意。
2. 各iにおいて、Si秒目で、+Pi、Ti秒目で-Piをしておく。
3.q[i+1] += q[i]を繰り返す。
4.各秒数でWを超えないか検証。
です。
E問題
タテH、横Wのぐりっとがあります。#は壁です。
左上から、右下に動くことをかんがえます。1回の移動では、右、下、斜め下のどれか1方向に好きなだけ移動できます。
すべての移動方法を100000000 + 7で割った数で求めなさい。
ぱっと見、行き方をたどればよいので、全部調べればよいです。
ですが、累積和を考えないと、いちいち前の事象を戻って考えるので、
o((HW)の2乗）というとんでもない数になります。
そこで、前の情報を保持しながら、右、下に行けないか考えます。
とりあえず、マス(i,j)に行く方法をdp[i,j]とします。
すると、dp[i,j]=dp[i-1,j]+dp[i -2,j]+...+dp[i,j -1]+dp[i, j-2]+....+dp[i-1,j-1]+dp[i-2,j-2]+....です。
ここまでくればなんとなく各方向に対して累積和を出せばよいのかなあと感じます。
よって、横、下、斜めのそれぞれの到達方法をx,y,zで保存するとすると、
x[i,j] = x[i- 1,j] +dp[i-1,j]
y[i,j] = y[i, j -1] + dp[i, j -1]
z[i,j] = z[i- 1,j -1] + dp[i -1, j-1]
です。
dp[i -1,j]で前に保存した方法すべてが保存されています。
そして、x[i-1,j]には右方向から動いてきた方法すべてを記録しています。（つまり、xにはdp[i-1,j]からdp[0,j]からの移動方法すべてを記録している）
y,zも同様なので、それぞれの方向で累積和ができます。
そして、dpはすべての方法を記録するので、
dp[i,j] = x[i,j]+y[i,j]+z[i,j]で更新しておきます。
ということで、
1.まず、#の部分は記録する。
2.二重ループ行う。初期条件はdp[0,0] = 1
この時、i== 0 && j == 0と#のときは飛ばす。
i > 0のとき、xを更新（i = 0はその前のx方向での移動ができない）
j > 0のときyを更新（j = 0はその前のy方向での移動ができない）
i > 0, j > 0のときzを更新(x,y同様）
最後にdp更新
3.答えはdp[W-1,H-1]で出力。
結構こんがらりますが、1次元でよく考えれば、3次元で繰り返しているだけです。
x方向の動きをちゃんと追って考えるとよいです（自分もですが）
最後に....
うーんわかっているのに解けない。この問題はちゃんと考えを文章化して、コードも理解することを地道に繰り返して、解決していきたいですね。
ではでは。
