AtCoder Beginner Contest 084

C.Special Trains(300)

問題

https://beta.atcoder.jp/contests/abc084/tasks/abc084_c

n個の駅がある。1<=i<=n-1を満たすすべての整数iに対して、駅iから駅i+1にC_i秒で向かう列車が運行される。駅iから駅i+1に移動する列車は開通式開始S_i秒後に駅iを発車し、その後はF_i秒後おきに駅iを発車する。すべての駅iに対して、開通式開始時に駅iにいる場合、駅nに最短で到着時間は開通式開始から何秒後か求めよ。

方針

駅の数nが小さいことから、すべてのnに対して貪欲にもとめても間に合いそうである。駅iをS_i後に発車し、駅i-1、駅i、駅i+1の遷移を考えてみる。駅iに到着した時刻をtとすると、駅i-1には時刻t-C_(i-1)に発車したことになる。ここで駅iから駅i+1への列車が発車する時刻は、t<=S_i+nF_iを満たす最小のnの時刻である。(t-F_i)/S_i<=nであるからceil((t-F_i)/S_i)である。ただし、nは0以上である。nが求められたので、駅iを発車する時刻がS_i+nF_iで求められた。このことを駅nに到着するまで続ければよい。

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

            int n = in.nextInt();
            int[] c = new int[n-1], s = new int[n-1], f = new int[n-1];
            for (int i = 0; i < n-1; i++) {
                c[i] = in.nextInt();
                s[i] = in.nextInt();
                f[i] = in.nextInt();
            }

            for (int i = 0; i < n-1; i++) {
                int now = s[i];
                for (int j = i; j < n-1; j++) {
                    now += c[j];

                    if (j >= n-2) {
                        break;
                    }
                    now = s[j+1] + f[j+1] * Math.max((now - s[j+1] + f[j+1] -1)/f[j+1], 0);
                }
                out.println(now);
            }
            out.println(0);
        }

雑記

問題文を読んだときに貪欲に求められるが、面倒という感覚を持った。そのとおりであった。上位の実装を見ると、もう少しシンプルに実装できそうであった。結局駅iを発車する時刻は駅iの発車時刻はときに意味をもたず、次の駅i+1の条件で決まるためである。これ、Dよりも難しいという印象を受けた。

D.2017-like Number(400)

問題

https://beta.atcoder.jp/contests/abc084/tasks/abc084_d

Q個のクエリが与えられる。区間[L_i,R_i]に以下の条件を満たす奇数xの個数はいくつあるか求めよ。

  • xと(x+1)/2が素数である

方針

区間における数え上げであることから累積和を使えばよさそうである。つまりr_i<=105であるから、[1,105]に条件を満たすいくつ存在するか事前にO(N)で求めておけば、各クエリはO(1)で求められる。ある数xが素数かどうかの判定が必要なので、あらかじめエラトステネスの篩で素数を列挙できるライブラリを持っておくと楽である。

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

            boolean[] isPrimes = new boolean[n];
            getPrimes(isPrimes, n);

            int[] sum = new int[n];
            for (int i = 0; i < n; i++) {
                sum[i] = calc(i, isPrimes);
            }
            for (int i = 0; i < n-1; i++) {
                sum[i+1] += sum[i];
            }

            int q = in.nextInt();
            int[] l = new int[q], r = new int[q];
            for (int i = 0; i < q; i++) {
                l[i] = in.nextInt();
                r[i] = in.nextInt();
            }

            for (int i = 0; i < q; i++) {
                out.println(sum[r[i]] - sum[l[i]-1]);
            }

        }

        int calc (int n ,boolean[] isPrimes) {

            if (n % 2 == 1 && isPrimes[n] && isPrimes[(n+1)/2]) {
                return 1;
            } else {
                return 0;
            }
        }

        public static void getPrimes(boolean[] isPrime, int n) {
            Arrays.fill(isPrime, true);
            isPrime[0] = isPrime[1] = false;
            for (int i = 2; i <= Math.sqrt(isPrime.length); i++) {
                if (!isPrime[i])
                    continue;
                for (int j = i + i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }

雑記

はじめてAtCoderの本番に参戦した思い出深い回。当時は計算量の概念があまりわからずナイーブな実装をしてひらすらTLEしていた。累積和はAtCoderのABCで頻出なので、十分に熟達しておくと良さそう。