AtCoder Beginner Contest 119
Updated:
Source codes
Solutions
A - Still TBD
2019/04/30 で平成は終わり、現皇太子であられる徳仁親王が 2019/05/01 に新天皇に即位なさるのだが、よく考えると実は文字列として比較するだけで十分である。ライブラリを使う必要もない。
余談
私は平成元年生まれでして、進学する先々で「もう平成生まれの子が入ってきたのね」と言われた世代です。東大不合格なってからそういうこともなくなりましたが。今やコンテストのオンサイトに行くと私よりはるかに優秀な年下の方にたくさん出会えます。平成の長さは、私の年齢とほぼ同じです。 29 年って短いんだなと思います。
B - Digital Gifts
指示通り為替レートを経由して日本円に揃えて和をとる。あえていうなら小数点以下をしっかり表示することが必要になる。
ポイント
Ruby だと puts sprintf("%.12f", ans) などとする。ここ忘れやすい。
C - Synthetic Kadomatsu
全探索する。完成品を $A[0], A[1], A[2]$ とする。各竹 $l[i]$ を「 $A[0]$ を作るために使う」「 $A[1]$ を作るために使う」「 $A[2]$ を作るために使う」「使わない」のどれかにする。割り当てられた竹は全て結合して、 $A[i]$ へと伸縮するものとする。このコストの最小値を求める。
実装する際は for (auto i = 0; i < (1 << 2 * N); i++) として、 $2$ 桁で竹の状態を持つのが明快だろう。
ポイント
添字の $i$ と $j$ を間違えて結構ロスしていました。ひどいひどい。ビット演算は基本及び実装部類ですから、もっと慣れておかないと。やっぱり実装力が落ちていますね。
D - Lazy Faith
各クエリ $y = x_q$ ごとに独立に $O(\log A + \log B)$ で解答を出せば十分である。最初からソートされていることをいいことに、二分探索をするとよろしい。
番兵を置いておけば、二分探索をすることで $p _ 0 < y < p _ 1$ となる神社と $q _ 0 < y < q _ 1$ となる寺が必ず手に入る。そこでまず $\min( \max(p _ 1, q _ 1) - y, y - \min(p _ 0, q _ 0) )$ が解答の候補である。あとは、これと、以下のものを比較し、その最小値が答えである。
- 先に $p _ 1$ に向かって、折り返して $q _ 0$ に向かう： $2 (p _ 1 - y) + (y - q _ 0)$ 。
- 先に $q _ 1$ に向かって、折り返して $p _ 0$ に向かう： $2 (q _ 1 - y) + (y - p _ 0)$ 。
- 先に $p _ 0$ に向かって、折り返して $q _ 1$ に向かう： $2 (y - p _ 0) + (q _ 1 - y)$ 。
- 先に $q _ 0$ に向かって、折り返して $p _ 1$ に向かう： $2 (y - q _ 0) + (p _ 1 - y)$ 。
ポイント
実装では下にも上にも番兵を設置しておくとよろしい。つまり $A, B$ を両方とも $2$ 増やしておいて、 $s[0] = t[0] = -\infty$, $s[A - 1] = t[B - 1] = \infty$ としておくと例外がなくなってよろしい。しばらくしてから思いついた。一直線に思いつかないと。うーん。
あと二分探索も間違えた。 ub を更新するべきところで lb を更新していた。もっと落ち着け自分と言いたい。
一方で、安易に abs 関数に頼らなかったのは、デバッグの観点からよかったと思う。今回は大小関係がはっきり決まるので、あえて絶対値をつけないことにより、思わぬ間違いを防いだ。この点は結局問題はなかったものの、好判断だと思いました。
Others
このセットは私が苦手意識を持っている実装を要求してくる、結構厳しいセットだった。意識失って夕方寝て、眠かったのもあって、 WA なしだったが 112 位でした。