あるごリズム備忘録

学んだことの記録と日記

競プロの記録 (2016_09_14)

<星1>

No.172 UFOを捕まえろ - yukicoder

今回の結界のばあい、4辺をそれぞれ直線と考えると、傾きを表す係数は、-1か1になる。
この時、直線上の任意の点はすべて、原点からのマンハッタン距離は等しくなる。
直線と円の接点の座標に関して、マンハッタンン距離をっ求めるだけの問題だった。
(補足)
四捨五入するのでなく、切り上げる場合は、double型の計算値に1を加算する。さらにここから1-e9を引いてからintでキャストする。この減算は、計算値がぴったりだった場合に、+1されることなく正しい値にするためのものである。

No.175 simpleDNA - yukicoder

瞬殺問題のハズだったが、終止コドンが途中に含まれた場合を除く処理を(必要ないのに)書こうとしていた。
例を見れば、それを除く必要が無いのはわかったはずだった。
難易度から考えて、実装が割に合わないときは、余計なケースを考えていないか、例もしっかり見て参考にするべき。

<星2>

No.7 プライムナンバーゲーム - yukicoder

エラトステネスの篩であらかじめ素数のリストを用意しておく。
(初めて使った。ライブラリにしておきたい感覚がなんとなくわかった。)
遷移先に、一つでも自分が勝てる道がある(dp[n - prim]の中に0がある)なら、勝ちである(dp[n]=1)。
dp[0]=dp[1]=1としておくのがポイント。
0と1は負け条件なのにdpが1というのが、感覚的に理解しずらかったが、こうしないとうまくいかない。(要検討)
遷移先のdpが0とは、相手が負けることなので、つまり自分の勝ちを表す。
時間はかかった(90分くらい)が、一発ACだった気持ちが良かった。競プロの楽しさを思い出させてくれる。
定着させるために、再解答リストに追加。


A予選まであと10日。