あるごリズム備忘録

学んだことの記録と日記

競プロの記録 (2016_09_06)

しばらく旅行に行っていたため、問題に触れていなかったが今日から再開する。
今日は4問解いた。

1問目:ARC051_A

A: 塗り絵 - AtCoder Regular Contest 051 | AtCoder

長方形が円に内包されていることの判定に苦労した。
始めは、長方形が正方形の場合のみを考えていて、「4辺がそれぞ円の中心からX,Yの正と負の方向に半径のcos(45度)倍離れているか」で判定していた。
これだと平べったい長方形の時に判定を誤る。
結論としては、単純に、長方形の4点がすべて円の中心から半径分だけ離れているか判定すればよいだけだった。
また、普段の2次元配列で使う軸の方向と違い、普通のユークリッド平面だったので少しハマった。

2問目:ARC055_A

A: 数え上げ - AtCoder Regular Contest 055 | AtCoder

普通に数値として計算するとlonglongにも収まらないため文字列で処理した。

3問目:ARC057_A

A: 2兆円 - AtCoder Regular Contest 057 | AtCoder

倍率Kが0でなければ(1以上)、毎回少なくとも2倍にはなるのでO(log)。Kが0だとシミュレーションだと間に合わないが、毎回1ずつ増加するので、単純に差をとるだけでよい。

4問目:ABC042_C

C: こだわり者いろはちゃん / Iroha's Obsession - AtCoder Beginner Contest 042 | AtCoder

支払い料金は品物の料金そのものからスタート。
指定の数字が含まれているか、各桁について大きいほうから調べていく。
もしどれかの桁に含まれていれば支払い料金を1円加算し、また繰り返す。
どの桁にも指定された数字がなければループを抜ける。
桁を大きいほうから調べると、その桁を調べた後10で割れば、次の一つ小さい桁も、また同じMOD10の処理で判定できるのでラク。


ペース上げる。考える暇があったら手を動かしたい。
A予選まであと18日。