codeFlyer(オープンコンテスト) 参加記録

codeFlyer （bitFlyer Programming Contest）オープンコンテスト - AtCoder

「codeFlyer 本選」のほうは、予選突破した参加者のみで行われるオンサイトコンテスト。オープンコンテストは、それと同じタイミングで同じ問題を解けるオンラインコンテストです。

オンサイトはやっぱり狭き門なので、オンラインで開催してくれるのはとてもありがたいです。

そして結果はABCFの4完、オープンコンテスト3位でした！

f:id:betrue12:20180630214549p:plain

これがratedだったらなーと少しだけ思いますが、それでも嬉しいです。Fを通せたのがとても大きい。

というわけで解けた4問を振り返っていきます。

A - 値札

10で何回割れるかを全部数えて、その最小値が答えです。整数を10で割る代わりに、文字列として処理して末尾の0の数を数えてもいいです。

ACコード：Submission #2758182 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト

B - 交通費

データに対して大量のクエリを処理する問題は、前計算 → クエリを効率的に処理 が王道パターンです。全クエリを毎回真面目に計算すると $O(NQ)$ で $10^{10}$ くらいになりTLEします。

とはいえ、何を前計算すればよいかの見当を付けるため、まずはクエリの処理方法を考えてみます。

クエリ $C$ と $D$ が与えられた時、参加者の家の位置 $X$ を横軸に取ると、交通費（縦軸）は以下のようなグラフになります。

f:id:betrue12:20180630220207p:plain

このため、 $X_{i}$ たちを次の4つにグループ分けできます*1。

$X_{i} \lt C - D$ である $X_{i}$ に対しては、交通費は $D$ 。個数が分かれば(個数) × $D$ でまとめて計算できる。
$C - D \le X_{i} \lt C$ である $X_{i}$ に対しては、交通費は $C - X_{i}$ 。
$C \le X_{i} \lt C + D$ である $X_{i}$ に対しては、交通費は $X_{i} - C$ 。
$C + D \le X_{i}$ である $X_{i}$ に対しては、交通費は $D$ 。個数が分かれば(個数) × $D$ でまとめて計算できる。

というわけで、以下の2つのことができれば交通費の総和が効率的に求められます。

1～4それぞれの範囲の境界となる $X_{i}$ を効率的に求める。境界が分かれば、範囲内の要素の個数も求められる。
範囲2, 3の交通費の総和を効率的に求める。

境界を求めることは二分探索で効率的にできます。1回あたり $O(\log N)$ なのでクエリごとに行っても大丈夫でしょう。

次に2, 3の交通費総和です。3の式で考えてみます*2。

交通費の総和は $\sum (X_{i} - C) = \sum X_{i} - nC$ です。ここで $\sum$ は範囲内の $X_{i}$ それぞれについて加算することを示し、 $n$ はその要素数です。要素数の計算は、二分探索で解決済みです。

$\sum X_{i}$ は、ある範囲内の連続する要素の和になっています。これは累積和を事前に求めておくことで高速に計算できます。具体的には $S_{i} = X_{1} + ... + X_{i}$ を事前に求めておけば、 $X_{x} + ... + X_{y} = S_{y} - S_{x-1}$ で計算可能です。