codeFlyer

A.本選参加者数(100)

問題

https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_a

方針

Bの倍数かつA以下であることから、A/B*Bであることが容易にわかる。

雑記

本番のときは、上の方針に気づかず、Aから1ずつデクリメントしてBで割り切れた結果を求めていた。

B.洋菓子店(200)

問題

https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_b

方針

問題文に書かれている条件を素直に実装すれば良い。

雑記

特になし

C.徒歩圏内(400)

問題

https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c

数直線上にN個の点が与えられ、i番目の座標はX_iである。

以下の条件を満たす3点の選び方の個数を求めよ。

  1. i < j < k
  2. X_j - X_i <= D かつ X_k - X_j <= D
  3. X_k - X_i > D

方針

Nが105であることから、O(N2)は間に合わない。解答はO(N logN)ないしはO(N)の計算量になりそうである。また3変数なので、1点をiを固定してもなおj,kの2変数あるので、簡単には上手くいかない。少し考えてみると、X_j - X_i <= D かつ X_k - X_j <= D の条件は、jを固定すると、二分探索で1回あたりO(logN)で求められることがわかる。jの範囲は2<=j<=N-1であるから、O(N logN)で求められる。条件 X_k - X_i > D を満たさない場合を考えてみると、それは X_k - X_i <= D という場合であることがわかる。X_k - X_i <= D の選び方だけ多く数えていることに気づくと、X_j - X_i <= D かつ X_k - X_j <= Dを満たす選び方から、X_k - X_i <= Dを満たす選び方を引けばよいことがわかる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            long d = in.nextLong();
            long[] x = in.nextLongArray(n);

            long ans = 0;
            for (int j = 1; j < n-1; j++) {
                ans += (long)(j-lowerBound(x, x[j]-d)) * (long)(upperBound(x, x[j]+d)-1-j);
            }

            for (int i = 0; i < n-2; i++) {
                long idx = (long)upperBound(x, x[i]+d)-1-i;
                ans -= idx*(idx-1)/2;
            }

            out.println(ans);

        }

雑記

本番では30分程度たった後に、余分に数え上げている数を引けばよいことに気づいた。しかし、なぜかx_iを基準にして、xの中に含まれるx_i+d以下の個数の数が求められずに終わった。数列で区間における要素 x 以下の個数は upperBound でxよりも大きなindexを求めて、そこから-1をすれば良い。また基準点のindexからの個数を計算しないといけないので、lowerBound,upperBoundで求めたときに基準点のindexとの差分を取らないと正しい個数は求められない。

考察ポイント

  • 3変数(i,j,k)で中点固定
  • 余事象(ダブった数を引く)
  • 二分探索
  • 範囲の以下、以上の個数の求め方