AtCoder Grand Contest 025

A.Digits Sum

問題

https://beta.atcoder.jp/contests/agc025/tasks/agc025_a

非負整数A,Bの和がNであるとき、A,Bの各位の和の合計の最小値を求めよ

方針

Nが105であることからO(N)で求められそうである。Aを固定すればB=N-Aであるから、そのときの各位の和を全探索すればよい。各位の和の求め方だが、ある数Aを10で割ったあまりが1の位であるから、A>0の間、10で割り続け、余りを足していけば良い。

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

            int n = in.nextInt();
            long ans = INF;
            for (int i = 1; i < n; i++) {

                long wa = 0;
                int a = i;
                int b = n-a;
                while (a > 0) {
                    wa += a%10;
                    a /= 10;
                }
                while (b > 0) {
                    wa += b%10;
                    b /= 10;
                }
                ans = Math.min(ans, wa);
            }
            out.println(ans);
        }
    }

雑記

本番中は各位の和を求めるときに、一旦A,Bをchar[]に変換して、char[i]-'0'を足していく。といった方法で求めていた。また、早解きしないといけない。というプレッシャーがあったので一発AC取れるかどうかドキドキしていた。

B.RGB Coloring

問題

https://beta.atcoder.jp/contests/agc025/tasks/agc025_b

N個のマスがある列が与えられる。マスに書かれている数の合計がKになるように、各マスにAまたはBまたはA+Bを書く。書き方は何通りか。

方針

マスの書き方はAをiマス、Bをjマス、(A+B)をkマス書いたとすると、Ai+Bj+(A+B)k=Kを満たすような(i,j,k)の組み合わせを求めることになる。しかしこのように考えるとO(N2)となり間に合わない。実は(A+B)の書き方は、AとBで2回書けばよいことがわかる。つまりAでxマス、Bでyマス書くような数と同じである。このように考えてもよいことに気づくと、Ax+B*y=Kとなるような(x,y)の組み合わせの数を数え上げればよいことがわかる。これはxを固定すればyはO(1)で求められる。(x,y)の組み合わせを全列挙できれば、あとはN個のマスからx個、y個のマスを選ぶ選び方であるから、nCx * nCyで求められる。

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

            int n = in.nextInt();
            long a = in.nextLong(), b = in.nextLong();
            long k = in.nextLong();

            long ans = 0;
            for (int i = 0; i <= n; i++) {
                long j = -1;
                if ((k-a*i) % b == 0) {
                    j = (k-a*i) / b;
                }
                if (j > n || j < 0) {
                    continue;
                }
                ans += comb(n, i) % MOD * comb(n, (int)j) % MOD;
            }
            out.println(ans % MOD);
        }

雑記

本番中は、サンプル1の計算でk=5だと勘違いし、答えが100になっていてずっと悩んでいた。時間と知能を使い果たし、本質的な考察ができなかったのは悔しい。また、3変数の不定方程式の解き方・・・を考えていたが、結局意味のないことだった。一般解を求めたところで結局全列挙しないといけないので。放送解説でもあったが、不定方程式で数論チックに解くのは1つの解であれば高速に求められるが、組み合わせを全列挙しないといけない場合はあまり意味がないという学びを得た。

C.Interval Game

問題

https://beta.atcoder.jp/contests/agc025/tasks/agc025_c

高橋くんは数直線上に立っており、最初は座標0にいる。青木くんはN個の区間をもっており、i個目の区間は「L_i,R_i」である。このゲームはN回のステップがあり、iステップ目では以下の手順を踏む。

  • 青木君は、N 個の区間の内、まだ選んでいない区間を一つ選び、その区間を高橋君に伝える。
  • 次に高橋君は、青木君が今回選んだ区間に入るように、数直線上を移動する。

N回のステップを終えた後、高橋くんは座標0まで戻ることでゲームは終了する。高橋君がゲーム全体を通して移動する距離の合計をKとしたとき、青木君は Kができるだけ大きくなるように区間を選び、 高橋君はK ができるだけ小さくなるように移動する。 このとき、最終的に高橋君の移動距離の合計Kはいくつになるか。

方針

　高橋くんは与えられた区間に対して、移動距離が最短になるように区間へ移動するので、地点xに対して右に区間を与えた場合は|x-L_i|の距離を移動し、左に区間を与えた場合は|x-R_i|の距離を移動する。青木くんは高橋くんの移動距離ができるだけ大きくなるように区間を与えるという条件を考えると、高橋くんがある地点にいるとき、区間を右→左→右→・・・と与えるか左→右→左→・・・とジグザグになるように与えるのが最適とわかる。ここまでわかると右→左→右→・・・と区間を与える場合の区間の選択方法は、|L_i-x|+|x-R_i|+|L_(i+1)-x|+...が最大となるような選択方法であることがわかる。つまり、与えられた区間をソートし、ひとつはL_iの降順、ひとつはR_iの昇順になるように並び替え、上から順番に区間を選択すればよい。ただし区間は一度しか使用できないので、すでに使用している区間を選択した場合は、その次の区間を選択する必要がある。最後に座標0に戻る必要があるので、地点xの絶対値を足しておく。あとは区間を右→左→右→・・・と与える場合と左→右→左→・・・と与える場合の移動距離が大きいほうを出力する。

   static class TaskX {
        PriorityQueue<Segment> s1min;
        PriorityQueue<Segment> s1max;
        PriorityQueue<Segment> s2min;
        PriorityQueue<Segment> s2max;
        int n, num;
        boolean[] used;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            n = in.nextInt();
            s1min = new PriorityQueue<>((o1, o2) -> o1.r - o2.r);
            s1max = new PriorityQueue<>((o1, o2) -> o2.l - o1.l);
            s2min = new PriorityQueue<>((o1, o2) -> o1.r - o2.r);
            s2max = new PriorityQueue<>((o1, o2) -> o2.l - o1.l);

            for (int i = 0; i < n; i++) {
                int l = in.nextInt(), r = in.nextInt();
                s1min.add(new Segment(i, l, r));
                s1max.add(new Segment(i, l, r));
                s2min.add(new Segment(i, l, r));
                s2max.add(new Segment(i, l, r));
            }

            long a1 = 0, a2 = 0;
            // 右→左→右→・・・
            used = new boolean[n];
            num = 1;
            a1 = move();

            // 左→右→左→・・・
            used = new boolean[n];
            num = 0;
            s1min = s2min;
            s1max = s2max;
            a2 = move();

            out.println(Math.max(a1, a2));

        }
        long move() {

            long ret = 0;
            long now = 0;
            while (!s1min.isEmpty() || !s1max.isEmpty()) {
                // 右
                num ^= 1;
                if (num == 0) {
                    while (!s1max.isEmpty()) {
                        Segment s = s1max.poll();
                        if (used[s.idx]) continue;
                        if (s.l >= now) {
                            ret += Math.abs(now - s.l);
                            now = s.l;
                        }
                        used[s.idx] = true;
                        break;
                    }
                }
                // 左
                else if (num == 1) {
                    while (!s1min.isEmpty()) {
                        Segment s = s1min.poll();
                        if (used[s.idx]) continue;
                        if (s.r <= now) {
                            ret += Math.abs(now - s.r);
                            now = s.r;
                        }
                        used[s.idx] = true;
                        break;
                    }
                }
            }
            ret += Math.abs(now);

            return ret;
        }

    }

    static class Segment {
        int idx, l, r;

        public Segment(int idx, int l, int r) {
            super();
            this.idx = idx;
            this.l = l;
            this.r = r;
        }

    }

雑記

地点xにいたときに、区間の端点が逆転する場合にはその場に立ち止まるのが最適なので、計算しないという点が見落としていた。右→左→右→・・・と左→右→左→・・・と両方計算しないといけないが、関数で持っておくことで同じ実装を2回せずに若干シンプルにできる。