ABC20
Welcome to AtCoder Beginner Contest #020 - AtCoder Beginner Contest #020 | AtCoder
解説スライドは下
自分の実装（今作り始めてる幾何問題用ライブラリが入ってるけどこれは無視してね。凸包すらまだ実装できてない。）
All submissions - AtCoder Beginner Contest #020 | AtCoder
これをみてくれ、こいつをどう思う？♂
400/401(ABCとしては全完といってよい)
人が少なかったのかもしれないけど、上位5%付近に食い込めたゾ(15/276)
思ったよりもここまでたどり着くのが早かったなーというのが個人的な印象
偶然たまたま運がよくうまく行った時に限界まで調子に乗って行くスタイル。３．。３．
A やるだけ でも、解説スライドにあったような「配列をうまく使うことで複数の条件分岐を手早く実装できる」ことはかなり勉強になる。普段からvx,vyの二次元グリッド捜査にはつかってたのに。もっと汎用性がある（ダラーッと長いifelseラッシュが驚くほどスッキリする）
「実装が楽で早く保守（デバッグ）も楽」なコーディングが最強で、これは永遠の課題になると思う。
B java,C#とかのstring が実装されていれば余裕。これができなかったら普段の問題の標準入力すら処理できないことになる 制約条件が999の長さの文字列と勘違いしてBiginteger型使ってしまった(int型で十分)
C 最短経路長問題。H,Wが異様に小さい(10)ので、ベルマン-フォード法を何回でも回せそうってことがわかる。それに対してTがくっそでかいので「計算量をlogTに落とす必要がある。」「最大のxを求める」のキーワードから二分探索が使そうということが検討できる。
実装量が重かった。幅優先探索を使って、より小さいパスが見つかれば、そのマスで新たに再計算する方法でゴールまでにたどり着くコストを最小化（スタートからゴールの最短経路長）して、T秒以内に間に合うかどうかを判定し、二分探索すれば十分間に合った。
前に二分探索の考察を書いてスニペット作っててよかった。これ自体は普段のABCのD問題くらいの難易度あるような気がする
D 101点無理ゲー LCM * GCD = a * b とユークリッドの互除法を知っていれば15点までは余裕。
・K=100とNに比べて圧倒的に小さいこと（なぜKが小さいなら効率的に解けるのか）
・実際にユークリッドの互除法の計算過程を手計算するなりして、例えばGCD(12,5),GCD(7,5)を計算した場合に、次の計算時には「同じく」2、5に遷移する、この先も一緒だからGCDが共通になる
・N = 10^9の膨大な値に対して定数時間O(１)で求める方法がある
ことの3つを検討すると、スライドの解説にあるような100点解法に行きつけた。
2,5,8,11,・・・の数列和の計算をするのにものすごい時間かかった。
1+2+3+4+・・・+n = n(n+1)/2 、k+k+k+k+・・・+k = kn (nは項数)を使ったのが沼（項数の計算がすごい大変だった）
スライド解説の101点解法はムリ、読んでも完全には理解できない・・・。これがいけるひとは一体どんな勉強をしてきたんだろうか・・・典型問題（？）らしい
A、BとC、Dので問題間の難易度差がちょっとアレ
