codeFlyer予選参加記録

codeFlyer （bitFlyer Programming Contest） - AtCoder

初めて参加した企業コンテスト。結果は30分台3完で159位でした。

f:id:betrue12:20180603102618p:plain

企業コンテストは変わった問題が出たり配点基準がいつもと違ったり…という話を聞いていましたが、今回は普通だったと思います。ABC/ARCでも出そうな問題。

解けたA～Cと、解こうとして解けなかったDを振り返っていきます。

A - 本選参加者数

$A$ 人以下でかつ $B$ 人の倍数となる最大の人数を求める問題。

$A$ 人から $B$ 人で割った余り（あぶれる人）を切り捨てる　と考えると、 A - A%B
$A$ 人から $B$ 人の組がいくつできるかを求めて $B$ 倍する　と考えると、 A/B * B

など何通りか書き方がありますが、最初に思い付いたものを素直に書いてしまえばいいと思います。（サンプルはもちろん通しましょう）

ACコード：Submission #2596471 - codeFlyer （bitFlyer Programming Contest）

B - 洋菓子店

問題文をよく読んで、その通りの動きをコードにすると解けます。解説書くのが難しいですね…

ACコード：Submission #2597462 - codeFlyer （bitFlyer Programming Contest）

C - 徒歩圏内

この問題からちょっと詳しく振り返ってみたいと思います。

C - 徒歩圏内

数直線上に点がたくさんあるので、以下のような位置関係になっている3点のトリオを数え上げてください、という問題。数式で書くと $i \lt j \lt k$ かつ $X_{k} - X_{j} \le D, X_{j} - X_{i} \le D, X_{k} - X_{i} \gt D$ をすべて満たすものです。

f:id:betrue12:20180603110024j:plain

愚直解は3点のトリオを全て調べる $O(N^{3})$ です。当然間に合いません。

各点は数直線上に座標順に並んでいるので、 「距離が $D$ 以下であるか」には単調性があります 。二分探索やしゃくとり法が使えそうです。全ての点それぞれに対して「右側にある距離 $D$ 以下の点の数」を求めることは、しゃくとり法を使うと $O(N)$ でできます。もちろん左側も同様です。

f:id:betrue12:20180603113609j:plain

そのため、例えば3点のうち左側の2点を固定してしまえば、前計算したしゃくとりの結果を使って条件を満たす右側の1点の範囲がすぐに計算できます。これで $O(N^{2})$ に落ちますが…入力サイズが $N \le 10^{5}$ なのでそれでも間に合いません。まだ落とす必要があります。

元の条件をそのまま考えて $O(N^{2})$ 未満に落とすのはかなり難しそうだと思い、「 いくつかの場合分けに分割して、足し算する 」や「 少し広い条件を考えて、余計なぶんを引く 」のような、条件の変形ができないか考えてみます。

ここで 3点の組を数え上げるときに、真ん中を固定すると楽 ということを思い出します。この考え方は、以下の問題からの類推でした。

C - Snuke Festival

真ん中を固定すると、左右それぞれにある「距離 $D$ 以下の点の数」は前計算したしゃくとりの結果を使えます。それらを掛け算すると、真ん中を $J$ に固定したときの $X_{k} - X_{J} \le D, X_{J} - X_{i} \le D$ を満たすトリオの数になります。全ての「真ん中の点」についてこれを足し算すれば、「答えに近いもの」が求まります。これがそのまま答えにならない理由は、もう1つの条件である $X_{k} - X_{i} \gt D$ が考慮できてないからです。

というわけで、上記のうち $X_{k} - X_{i} \gt D$ を満たさないもの、つまり3点全てが距離 $D$ に含まれているものを数えて引き算します。これは、左端を固定した時に「右側にある距離 $D$ 以内の点」から2個を選べばよくて、これもしゃくとりの前計算が使えます。

これで答えが計算できます。振り返ってみると、いくつかのテクニックの組み合わせが要求される問題だったなと思います。ABC/ARC-D 400点でも、このくらいは出そうですね。

1次元上の点がソートされている時、距離には単調性があるので、しゃくとり法を使う（二分探索でも可です）
数え上げの条件が扱いにくい場合、少し広い条件を考えて、余計なぶんを引く（これの発展が「包除」ですね）
3点のトリオを、真ん中を固定して数え上げる

ACコード：Submission #2599368 - codeFlyer （bitFlyer Programming Contest）

※余談ですが、（現時点での）公式解説の書き出しにミスがあるのでご注意ください。公式解説の書き方を真似つつ修正するなら、以下が正しいと思います。

$i \lt j \lt k$ かつ $X_{k} - X_{i} \le D$ を満たす $(i, j, k)$ の個数 $A$
$i \lt j \lt k$ かつ $X_{j} - X_{i} \le D, X_{k} - X_{j} \le D$ を満たす $(i, j, k)$ の個数 $B$