AtCoder Beginners Selection 300点問題を解いた
【注意】この記事はAtCoder Beginners Selection (ABS)のネタバレを含んでいるのでまだ解いてない人は下のほうまで見ないほうが良いです！（内輪向け感のある発言）
少し前から周りの人に競プロを宣伝していて、初めての人には「とりあえず最初はABSをやると良いよ〜」とオススメしていたのですが、実は僕自身サラッと問題文を見た程度でちゃんと解いていなかった（？？？）ので後半部分の300点問題だけ解いてみました。
問題
ABC085C - Otoshidama
まず最初に一万円、五千円、千円の枚数を3重ループで回すO(N3)な方法を思いつきそうですが、N<=2000なので実行時間制限にひっかかりそうです。
この場合、一万円、五千円の枚数が定まれば、N枚持っているという情報から千円の枚数を確定させることができるので2重ループで回すO(N2)な方法で解を求めることができます。計算量を落とすことができたので、これなら実行時間制限にひっかかることもありません。
ABC049C - 白昼夢 / Daydream
（300点問題にしてはちょっと実装が面倒な印象がある）
先頭からdream / dreamer / erase / eraserと一致するかどうか見ていけば良さそうですが、そうするとdreamerとeraseやeraserで条件分岐をさせる必要があり面倒くさそうです。
もっと簡単に実装できないか？と考えると、maerd / ...のように文字列をリバースしてから調べると上記のような面倒な分岐をさせずに調べることができることに気付きます。それが分かればあとは愚直に文字列比較していけば良いです。
ABC086C - Traveling
座標の範囲や個数が105あるので、一歩ずつ動かしてある時刻にある座標にいるかどうかを調べることはできません。実行時間制限にひっかかります。
まず、2つの座標を時刻t'の間に移動できるかどうかを考えるとき、移動距離dはマンハッタン距離となり、t' == dなら移動可能、t' < dなら移動不可能なのは感覚で分かります。ではt' > dはどうなるかを考えると、ある座標にいるとき、x軸、またはy軸に対して+1して-1すれば元の位置に戻ってくることができます。つまり(t' - d) % 2 == 0なら先ほどの方法で移動可能、とすることができます。これを繰り返しチェックしてやればO(N)で解くことができます。
