AtCoder Regular Contest 094

更新日時:

AtCoder Regular Contest 094

解説放送

ソースコード

解法のメモ

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

ポイント

その他

この前まで書いたもの。

今日は GCJ 2018 Qual. と Maximum Cup 2018 と ARC094 が全部一気に重なっていたので、途中からぐったりしていました。計 12 時間くらいコーディングしているので、全部全力ではできませんでした。 GCJ は small は全部通ったし A-C は多分 large も通っているので、まぁそれで十分だったのかなと。成績は悪かったけど、成績のためにやっている訳ではなく、 1 問 1 問を丁寧に解くことを目標にしているので、疲れが取れたらまたしっかり考察したいと思います。

コメントする