AtCoder Beginner Contest 188参加記（～D問題）

100-200-300-0(2)-0(1)-0で0ペナ3完600点。

A - Three-Point Shot

$X$ と $Y$ のうち小さい方に $3$ を足して比較すると良い。もともとどちらが小さかったかを工夫して持つ必要がある。自分は、必ず $X>Y$ となるように適切にswapしてから問題を解いた。こうすると、もともと小さかった方は必ず $Y$ である、といえる。

計算量は、 $O(1)$ 。

B - Orthogonality

ベクトルとか内積とか、その辺の言葉を知らなくても問題文に定義が書いてあるのでそれをやるだけ。ただし、判定すべき式の左辺に「 $\dots$ 」が含まれているので、その辺の処理を工夫する必要がある。総和記号を使って書くと、
$\displaystyle \sum_{i=1}^N A_i\times B_i = 0$
の真偽を調べればよい。これは、for文などで実装できる。

足し算や掛け算が出てきたときは、数値のオーバーフローに気を付ける（最大値を考える）。今回の場合、最大値は $10^9$ なので、32bitのint型でも収まる。優しい…（伏線）

計算量は、 $O(N)$ 。

C - ABC Tournament

問題文が難しいシリーズ。要するに番号の小さい順に $2$ 人ずつマッチさせて戦わせ、勝ったほうだけ残せということ（最後の $2$ 人だけは負けた方を出力しなければならないが、勝った方の逆を出力するという解釈をすればよい）。これを愚直にシミュレーションしたときの計算量を考える。

$i(1\le i\le N)$ 回戦目では、 $j(1\le j\le 2^{N-i})$ ペアが試合を行う。一方が勝ってもう一方が負けるので、 $i+1$ 回戦目に出場する人数は $i$ 回戦目の $\dfrac{1}{2}$ となる。このとき、シミュレーションするために必要なメモリへの参照回数を計算すると
$\displaystyle \sum_{i=1}^N 2^{N-i} = 2^{N-1} + 2^{N-2} + \dots + 2^0 = 2N-1$
となる。よって、シミュレーションにかかる計算量は $O(N)$ であるので、シミュレーションするだけで時間内に答えが得られる。

ちなみに、公式解説の解法2には「選手の集合を前半と後半で2つに分けたとき、一番レートが高い選手と逆の集合にいる選手のうち一番レートが高い選手が答え」と書いてあった。トーナメント表を実際に書いてみると理解できる。こちらも、計算量は $O(N)$ と変わらないが、実装はかなり楽である。

D - Snuke Prime

問題文に明記されていないが、制約より $1$ 日目から $10^9$ 日目まで考えればよい（無限ではない）。

また、それぞれの日に関して、 $N$ 個あるサービスのうちどれを使うかはすでに決められていて、選べるのは「利用するすべてのサービスの利用料を普通に支払うか」「すぬけプライムで支払うか」の2択である。この選択は日ごとに独立で、最終的な支払金額を最小化したいので、この2択のうち安い方を貪欲に選べばよい。利用するすべてのサービスの利用料を普通に支払った場合の金額は、いもす法を使って効率的に求められる。

ただし1日ずつ考えていると時間が足りない。与えられる情報は高々 $N=2\times 10^5$ 個であることから、座標圧縮を用いることで計算量を $O(N)$ に落とすことができる。ただし、オーバーフローに注意する（「日数×サービス数×利用料」の最大値が $10^{23}$ となってしまう）。どちらの支払い方法でも、支払う日数は変わらないので、1日当たりの支払い金額で比較してから日数を掛ければよい。オーバーフローに気付かず、2WA。