AtCoder Regular Contest 094
Updated:
Source codes
Solutions
C - Same Integers
解答
最後に至る数字を $X$ とする。すると操作回数は $Y = (3X - (A+B+C)) / 2$ 回である。であるから $X \geq M = \max(A, B, C)$ であり、かつ $3X = A + B + C$ in $\mathbb{Z}/2\mathbb{Z}$ であることが必要である。これは十分条件にもなっている(後述)。この中で最小の $X$ をとりたい。最初の条件を考慮すると $X = M$ が最小値の候補であり、後者を充していればそれで終わり。そうでなければ $X = M + 1$ が最小値を与える。
十分条件であることの正当化
$A$ を適当に 2 ずつ増やしていく。帳尻があったら良い。最後に帳尻が合わなかったら 1 増やす。この時 $X$ と奇数だけ離れている $B$ or $C$ があるのでそいつも 1 増やす。場合分けはあるが、基本的にはあと同じ。
ポイント
$Y$ を見るのではなく、到達目標 $X$ を見ればよろしい。これに気づくと早い。
D - Worst Case
$X$ について二分探索する。
上に凸の 2 次関数の区間における最大値であるから、普通に求めるか、三分探索すればよろしい。せっかくなので三分探索をやろう。
参考文献
ポイント
E - Tozan and Gezan
ポイント
F - Normalization
ポイント
Others
この前まで書いたもの。
今日は GCJ 2018 Qual. と Maximum Cup 2018 と ARC094 が全部一気に重なっていたので、途中からぐったりしていました。計 12 時間くらいコーディングしているので、全部全力ではできませんでした。 GCJ は small は全部通ったし A-C は多分 large も通っているので、まぁそれで十分だったのかなと。成績は悪かったけど、成績のためにやっている訳ではなく、 1 問 1 問を丁寧に解くことを目標にしているので、疲れが取れたらまたしっかり考察したいと思います。