118. AtCoder参加記録（AtCoder Beginner Contest 255）

23回参加でレート 1231 です。

今回はパフォーマンス 1280 です。

ABCDを通して、FGExは未解答です。EはTLE、Cで1ペナ。
今日全体的に難しかった（というより実装が大変だった）ですね。

各問題の感想など。

A

1分50秒。

特に言うことなし。

B

9分47秒。

Bとしてはそこそこ難しいのでは…？
明かりを持っている人・持っていない人に分類して、「明かりを持っていない人」それぞれについて持っている人への最短距離を出します。これらの最大値が答え。

全探索で十分間に合います。なんかバグらせてて無駄に時間を食いました…。

C

初回提出9分13秒、そこからACまで2分0秒。

対象となる等差数列の最小値と最大値を出しておきます。これは $O(1)$ でできます。 $X$ がこの最小値以下、最大値以上なら差を出すだけです。考えるべきは間にあるときです。 $(X - \min A) / D$ とすれば、どの項とどの項の間に $X$ が位置するのか分かるので、近い方との差を出せばいいです。これも $O(1)$ で出せます。

$D \lt 0$ のパターンでバグるコードになっていて 1WA。

D

23分7秒。

$A$ の順番に意味は無いので、昇順に並べておきます。 $X$ に対して必要な操作回数は、 $A$ の各要素と $X$ の差の絶対値の総和です。これを定数～対数時間で行う、という問題と読み替えられます。

こう考えると、 $A$ の総和と $XN$ の差で求まるのでは？と思ってしまいそうですが、実際は差を取る順番が逆になるケースがあるので上手く行きません。ここは、二分探索で $X$ がどの位置にいるか判定して、自分以下の要素、自分より大きい要素で差を取る順番を変えればいいです。その範囲での総和を知りたいので、累積和配列を作って $O(1)$ で取得します。

以上、 $O(Q \log N)$ ですが、これもバグらせまくって無駄に時間が掛かりました。

E

初回提出23分0秒。

$A_i$ を 1 つ定めればすべての項が芋づる式に出てきます。最適な状態ではラッキーナンバーが何処かにあるのが必要条件なので、ラッキーナンバーのある位置とラッキーナンバーの種類で全探索すればよいのでは？と思いました。ここまで $O(NM)$ です。

あとは、上の条件でラッキーナンバーがいくつあるのか、という計算を $O(1)$ で行えばいいのですが、本当に何故か分からないのですが普通に $O(N)$ の処理を書いていて当然 TLE しました。脳がバグっていた…。

ここから、判定を定数時間で行えないか考察。いろいろ数字を変えてみると、適当に定めた $A$ と、ひとつ項を定めた場合の奇数番目・偶数番目の項の変動は、定めた項と定めた数列における該当項の差に依存して固定だと気付きました。そのため、適当に $A_1 = 0$ みたいに定めて各数が何個あるかカウントしておき、判定フェーズで足したり引いたりした数の個数を出せば $O(1)$ で出来る…と考えて、ずっとバグらせていました。