geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 255 参加記録

ABC 二分探索

コンテスト中AC:A
惨敗でした。コンテスト後ですが、自力でEまでは解けました。

2022/07/14 E問題の赤字部分が $i$ になっていたので、 $j$ に修正

B - Light It Up
C - ±1 Operation 1
D - ±1 Operation 2
E - Lucky Numbers

B - Light It Up

半径 $R$ の2乗 $R^2$ を二分探索します。
2乗しているのは、long doubleなどの実数だと誤差が怖いためです。

二分探索では、以下を判定基準にします。

全ての人が $A_1,\cdots ,A_N$ のいずれかの人が持つ明かりに照らされる

これは $O(NK)$ で全探索できますが、コンテスト中はこの判定の実装が間違っていました。

$R^2$ の上限として、 $10^{18}$ を見積もっても、十分余裕がありました(厳密には $2\times 10^{10}$ くらい？)。

最後に2乗根をとって答えとします。
https://atcoder.jp/contests/abc255/submissions/32422863

C - ±1 Operation 1

等差数列 $S=\{a_1,...,a_N\}$ とします。
$X$ は、 $S$ の最も近い要素にするのが最適です。
値の大小順に $X$ を $S$ に挿入すると以下の3通りが考えられます。

$X,\ a_1,\ \cdots ,\ a_N$
$a_1,\ \cdots ,\ a_l,\ X,\ a_r,\ \cdots ,\ a_N$
$a_1,\ \cdots ,\ a_N,\ X$

それぞれのケースの答えは、

$|X-a_1|$
$min(|X-a_l|,|X-a_r|)$
$|X-a_N|$

です。
1,3のケースは簡単に求められます。問題は2のケースですが、これは二分探索により求められます。

コンテスト中は $D\lt 0$ のケースが抜けていました。
Submission #32422643 - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

D - ±1 Operation 2

例えば、 $A$ の $X$ 未満の要素が $B_1,\ B_2,\ \cdots ,\ B_m$ であったとします。

これを $X$ にしたい時にかかる操作回数は、

$X - B_1 + X - B_2 + \cdots + X - B_m$

式変形すると、

$X+X+\cdots + X - (B_1 + B_2 + \cdots + B_m)$

となり、 $S_B = B_1 + B_2 + \cdots + B_m$ とすると、

$X\times m - S_B$

となります。

同様に、 $X$ より大きい $A$ の要素を $C_1,\ C_2,\ \cdots ,\ C_n$ とすると、必要な操作回数は、

$S_C - X \times m$

となります。

余談ですが、式は説明のために書きましたが、コンテスト中は棒グラフを書いて、 $X$ で線を引く感じをイメージしました。

解法ですが、 $X$ 未満と $X$ より大きい要素の和を効率よく得られればよいです。 $A$ の順序は無視できるため、 $A$ を昇順ソートして、累積和を計算しておくと、二分探索して和を得られます。
具体的には以下のようになります。

$A$ を昇順ソートする

$A$ の累積和 $S$ を得る

各クエリについて、以下を行う

二分探索で、ソート済みの $A$ の要素の内 $X$ 未満の最大値 $A_s$ と、 $X$ より大きい要素の最小値 $A_t$ を得る。

$X\times s - S_s + S_N - S_{t-1} - X\times (N-t)$ を出力する

なお、 $A_s,A_t$ が存在しない場合の例外処理が必要です。

コンテスト中はクエリの処理部分を以下のようにしていました。

$X$ 以上の最小値 $A_s$ を二分探索で得る(lower_bound)。
$X\times s - S_s + S_N - S_{s} - X\times (N-s)$ を出力する

$A_1,\ \cdots,\ A_s$ と $A_{s+1},\ \cdots ,\ A_N$ に分けるような方法です。

この実装は、 $A$ に $X$ が存在すれば、おそらく問題なく動作すると思うのですが、そうで無い場合、例えば以下のようなケースで答えがおかしくなります。
$A=\{1,5\},\ X=3$

1,5を3にするのにそれぞれ2回の操作が必要なので、計4回となるはずです。しかし、上記の実装だと、 $A_s=5$ となり、 $3\times 2 - (1+5)=0$ となってしまいます。

おそらく $A_s$ を大きい方の和に入れておけばよかったです。つまり、
$A_1,\ \cdots,\ A_{s-1}$ と $A_{s},\ \cdots ,\ A_N$

という風に分けておけばよかったものと思います。

Submission #32420079 - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

E - Lucky Numbers

コンテスト後に解きましたが、思わぬところでTLEになり解決に時間がかかりました。

$A_i$ は $A_1$ と $S_0,\ \cdots ,\ S_{i-1}$ で表現できます(便宜上、 $S_0 = 0$ とします)。具体例を示すと、

$A_1 = S_0 + A_1$
$A_2 = S_1 - S_0 - A_1$
$A_3 = S_2 - S_1 + S_0 + A_1$

という感じです。ここで、定数部分を $V_i$ とします。
そうすると、 $A_i$ は以下のように表現できます。

$i$ が偶数の時、 $A_i = V_i + A_1$
$i$ が奇数の時、 $A_i = V_i - A_1$

また、 $V_i$ は、以下の漸化式で計算できます。

$V_i = S_{i-1} - V_{i-1}$

ここまでで前準備が終了です。

少なくとも1つはラッキーナンバーにしないと損をするので、 $A_1,\ \cdots ,\ A_N$ がそれぞれ、 $X_1,\ \cdots ,\ X_M$ である時のラッキーナンバーの数を全探索します。

$A_j = X_i$ である時を考えます。
$A_1$ は以下のように計算できます。

$\color{red}{j}$ が偶数の時 $A_1 = X_i - V_j$
$\color{red}{j}$ が奇数の時 $A_1 = -(X_i - V_j)$

$A_1$ が求まると、 $A_m$ がラッキーナンバー $X_k$ となるための $V_m$ が満たすべき条件がわかります。すなわち、

$m$ が偶数の時 $V_m = X_k - A_1$
$m$ が奇数の時 $V_m = X_k + A_1$

従って、予め $V_1,\ \cdots ,\ V_N$ について、偶奇を分けてハッシュマップに個数をカウントしておけば、上記を満たすようなものの個数を $O(1)$ で得られます。

$A_j = X_i$ のときに、 $X_1,\ \cdots ,\ X_M$ となるものがあるかを $O(1)$ で調べられるので、時間計算量は $O(NM^2)$ となり、問題ないと思われました。

しかし、実装時C++のunoredered_mapでこれを実装するとTLEになりました。

結局、 $V_i$ とその個数をpairにしたvectorを昇順ソートし、lower_boundすることでACしました。
Submission #32478157 - Aising Programming Contest 2022（AtCoder Beginner Contest 255）