NOMURA プログラミングコンテスト 2021(AtCoder Regular Contest 121)

ARC

コンテスト前のレート：
レート通りのパフォーマンスが得られる順位：396位（1400点、122分41秒）

A - 2nd Greatest Distance

問題
ぱっと見ですぐにはわからず、最初は今日も爆死かと思った。

思考過程
  1. 最も大きい距離を求めるのであれば、x座標でソートした「末尾-先頭」とy座標で同じことをした結果の大きい方。
  2. 2番目になる可能性があるのは、上記の2つに加え、「末尾から2番目-先頭」と「末尾-先頭から2番目」をx, yそれぞれについて求めたものの4つ。
  3. これら6つの値の内、i, jの組み合わせが重複するものを除いて2番目に大きいものを求める。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            String[] sa = br.readLine().split(" ");
            o.x = Integer.parseInt(sa[0]);
            o.y = Integer.parseInt(sa[1]);
            o.i = i;
            arr[i] = o;
        }
        br.close();

        PriorityQueue<Obj2> que = new PriorityQueue<>((o1, o2) -> o2.x - o1.x);
        Arrays.sort(arr, (o1, o2) -> o1.x - o2.x);
        // x座標：末尾 - 先頭
        {
            Obj2 o2 = new Obj2();
            o2.i = (long) arr[0].i * n + arr[n - 1].i;
            o2.x = arr[n - 1].x - arr[0].x;
            que.add(o2);
        }
        // x座標：末尾 - 先頭から2番目
        {
            Obj2 o2 = new Obj2();
            o2.i = (long) arr[1].i * n + arr[n - 1].i;
            o2.x = arr[n - 1].x - arr[1].x;
            que.add(o2);
        }
        // x座標：末尾から2番目 - 先頭
        {
            Obj2 o2 = new Obj2();
            o2.i = (long) arr[0].i * n + arr[n - 2].i;
            o2.x = arr[n - 2].x - arr[0].x;
            que.add(o2);
        }

        Arrays.sort(arr, (o1, o2) -> o1.y - o2.y);
        // y座標：末尾 - 先頭
        {
            Obj2 o2 = new Obj2();
            o2.i = (long) arr[0].i * n + arr[n - 1].i;
            o2.x = arr[n - 1].y - arr[0].y;
            que.add(o2);
        }
        // y座標：末尾 - 先頭から2番目
        {
            Obj2 o2 = new Obj2();
            o2.i = (long) arr[1].i * n + arr[n - 1].i;
            o2.x = arr[n - 1].y - arr[1].y;
            que.add(o2);
        }
        // y座標：末尾から2番目 - 先頭
        {
            Obj2 o2 = new Obj2();
            o2.i = (long) arr[0].i * n + arr[n - 2].i;
            o2.x = arr[n - 2].y - arr[0].y;
            que.add(o2);
        }

        // (i * n + j)をキーとして重複判定
        // わざわざSetなんて使わなくても、long型の変数1つでよかった
        Set<Long> set = new HashSet<>();
        Obj2 o1 = que.poll();
        set.add(o1.i);
        while (true) {
            Obj2 o2 = que.poll();
            if (!set.contains(o2.i)) {
                System.out.println(o2.x);
                return;
            }
        }
    }

    static class Obj {
        int i, x, y;
    }

    static class Obj2 {
        long i;
        int x;
    }
}

ここまで10分11秒＋0ペナ。168位。


B - RGB Matching

問題
下記4.で、j=lとなる場合があることに全く気付いていなかったが、気付いていなくても影響ないことが幸いした。

思考過程
  1. まず、R, G, Bが全て偶数匹ずつなら0。
  2. 上記に当てはまらない場合、全体は偶数匹なので、各色の配分は奇数、奇数、偶数となる。以下、色XとYが奇数、Zが偶数とし、色Xのi匹目をX_iのように呼ぶ。
    　
  3. 答えとなる可能性のあるものとして、XとYの内ペアにならなかった1匹ずつを組ませた場合の、|X_i-Y_j|が最小となるものが挙げられる。
  4. もう1つ、Zの1ペアをバラしてX, Yの余りと組ませた場合の、|X_i-Z_j|+|Y_k-Z_l|が最小となるものも考えられる。
    　
  5. 上記3. 4.の最小となるものは、各X_iについて、X_i以下で最大のY_jと、X_i以上で最小のY_jを探すことで求められる。
  6. これは個人的には二分探索するよりTreeSetのfloorやceilingを使う方がわかりやすいので、そのように実装する。

後から見たら、要素数を調べるまでの部分でTreeSetを使っているのは駄目。これでは、a_iの値に重複があると壊れるので、初めはListにでもしておき、要素数を調べた後にTreeSetに移し替える必要がある。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int n2 = n * 2;
        TreeSet<Long> r = new TreeSet<>();
        TreeSet<Long> g = new TreeSet<>();
        TreeSet<Long> b = new TreeSet<>();
        for (int i = 0; i < n2; i++) {
            String[] sa = br.readLine().split(" ");
            long a = Long.parseLong(sa[0]);
            char c = sa[1].charAt(0);
            if (c == 'R') r.add(a);
            if (c == 'G') g.add(a);
            if (c == 'B') b.add(a);
        }
        br.close();

        // 全て偶数の場合
        if (r.size() % 2 == 0 && g.size() % 2 == 0 && b.size() % 2 == 0) {
            System.out.println(0);
            return;
        }

        // r, g, bの内奇数のものをx, y、偶数のものをzとする
        TreeSet<Long> x = null;
        TreeSet<Long> y = null;
        TreeSet<Long> z = null;
        if (r.size() % 2 == 1) {
            x = r;
            if (g.size() % 2 == 1) {
                y = g;
                z = b;
            } else {
                y = b;
                z = g;
            }
        } else {
            x = g;
            y = b;
            z = r;
        }

        long ans1 = Long.MAX_VALUE; // |x - y|の最小
        long ans2 = Long.MAX_VALUE; // |x - z|の最小
        long ans3 = Long.MAX_VALUE; // |y - z|の最小
        Long[] arr = x.toArray(new Long[0]);
        for (long i : arr) {
            // x以下で最大のy
            Long a = y.floor(i);
            if (a != null) {
                ans1 = Math.min(ans1, i - a);
            }
            // x以上で最小のy
            a = y.ceiling(i);
            if (a != null) {
                ans1 = Math.min(ans1, a - i);
            }

            // x以下で最大のz
            a = z.floor(i);
            if (a != null) {
                ans2 = Math.min(ans2, i - a);
            }
            // x以上で最小のz
            a = z.ceiling(i);
            if (a != null) {
                ans2 = Math.min(ans2, a - i);
            }
        }
        Long[] arr2 = y.toArray(new Long[0]);
        for (long i : arr2) {
            // y以下で最大のz
            Long a = z.floor(i);
            if (a != null) {
                ans3 = Math.min(ans3, i - a);
            }
            // y以上で最小のz
            a = z.ceiling(i);
            if (a != null) {
                ans3 = Math.min(ans3, a - i);
            }
        }

        // zが空の場合を考慮
        if (ans2 != Long.MAX_VALUE && ans3 != Long.MAX_VALUE) {
            ans1 = Math.min(ans1, ans2 + ans3);
        }
        System.out.println(ans1);
    }
}

ここまで27分10秒＋0ペナ。62位。


C - Odd Even Sort

問題
あまりに単純な方法で通ってしまい、本当にこれでよかったの？ってなった。

思考過程
  1. 昇順になっていたら終了。
  2. 奇数or偶数番目を前から見ていって、最初にp_n \gt p_{n+1}となっていたところに対して操作を行う。
    ただし、そのようなところがなければ、（奇数or偶数番目の中で）一番最後に対して操作を行う。
    　
  3. という方法でできそうか、N=5くらいで試してみてできそう。
  4. 計算量がO(TN^3)になりそうだと思ったが、Nが大きければTは小さくなるし、500^3だけならまあ大丈夫かと思い、とりあえず提出してみたらAC。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            int n = Integer.parseInt(br.readLine());
            int[] p = new int[n];
            String[] sa = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                p[i] = Integer.parseInt(sa[i]);
            }

            StringBuilder sb = new StringBuilder();
            int cnt = 0;
            while (true) {
                // 1
                boolean flg = true;
                for (int i = 1; i < n; i++) {
                    if (p[i - 1] > p[i]) {
                        flg = false;
                        break;
                    }
                }
                if (flg) {
                    break;
                }
                // 2
                for (int i = cnt % 2; i < n; i += 2) {
                    if (i >= n - 3 || p[i] > p[i + 1]) {
                        int tmp = p[i];
                        p[i] = p[i + 1];
                        p[i + 1] = tmp;
                        sb.append(i + 1).append(' ');
                        cnt++;
                        break;
                    }
                }
            }
            pw.println(cnt);
            if (sb.length() > 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
            pw.println(sb.toString());
        }
        pw.flush();
        br.close();
    }
}

ここまで39分46秒＋0ペナ。17位。


D - 1 or 2

問題
Cまでで十分すぎる成績で、順位表を見ていてもあまり解ける気がする正解者数でもなく、D～Fを全部見てできそうな気がするものを適当に考えていた。

思考過程
  1. 値が正であるものと負であるもの同士は、絶対値が大きい方から順にペアにしていって損することはなさそう。
  2. 正と負のどちらかが余った場合、そのまま絶対値が大きい順に、0とペアにするのは行って問題ない。
  3. 正のものが余り、上記1.での最小値が0以下の場合、余ったものの処理で最小値がこれ以上下がることがなく、最大値は上げたくないので、残りは全て1つずつ選ぶのが最適。負のものが余り、最大値が0以上の場合も同様。
    　
  4. これ以降は、値が正である要素のみが余り、かつこれまでの処理における最小値が正である場合のみであるとする。（負のものが余った場合は符号を反転させる）
  5. 例１を見ると、昇順に並んでいる内の後ろの方は1つだけで選び、前の方だけペアにすることで差が縮まるケースがあることがわかる。
    　
  6. 前の方をペアにするとして、ペアにする範囲内では、「先頭と末尾」、「先頭から2番目と末尾から2番目」、\cdotsのように組み合わせるのが最適。
  7. あとはその「前の方」をどこまでにするかだが、これはO(N^2)が許される制約なので、全探索する。
    　
  8. INFをLong.MAX_VALUEとかにしていたら、符号反転でおかしくなっていたので、適当に小さくする。
  9. 他に考慮が必要な構成方法が本当にないのかは自信が持てなかったが、とりあえず提出してみたら通った。

後から見たら、0が余っている場合を考慮できていなかった。
以下のコードでは、全て0の場合に-2INFになるなどしてしまう。（コメント部分を追加すれば問題なくなるはず）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        PriorityQueue<Integer> p = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> m = new PriorityQueue<>();
        int z = 0;
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sa[i]);
            if (a == 0) {
                z++;
            } else if (a > 0) {
                p.add(a);
            } else {
                m.add(a);
            }
        }

        long inf = 100100100100100L; // 8
        long min = inf;
        long max = -inf;
        // 1
        while (!p.isEmpty() && !m.isEmpty()) {
            int v = p.poll() + m.poll();
            min = Math.min(min, v);
            max = Math.max(max, v);
        }

        // 2
        while (!p.isEmpty() && z > 0) {
            int v = p.poll();
            min = Math.min(min, v);
            max = Math.max(max, v);
            z--;
        }
        while (!m.isEmpty() && z > 0) {
            int v = m.poll();
            min = Math.min(min, v);
            max = Math.max(max, v);
            z--;
        }

        // 3
        if (!p.isEmpty() && min <= 0) {
            while (!p.isEmpty()) {
                max = Math.max(max, p.poll());
            }
            System.out.println(max - min);
            return;
        }
        if (!m.isEmpty() && max >= 0) {
            while (!m.isEmpty()) {
                min = Math.min(min, m.poll());
            }
            System.out.println(max - min);
            return;
        }

        // 4
        List<Integer> list = new ArrayList<>();
        while (!p.isEmpty()) {
            list.add(p.poll());
        }
        if (!m.isEmpty()) {
            long t = -min;
            min = -max;
            max = t;
            while (!m.isEmpty()) {
                list.add(-m.poll());
            }
        }
//      for (int i = 0; i < z; i++) {
//          list.add(0);
//      }

        long ans = inf;
        int size = list.size();
        // 7. iは「前の方」の要素数（偶数）
        // ※ただし、listは降順になっているので、後ろのi件をペアにする
        for (int i = 0; i <= size; i += 2) {
            long min2 = min;
            long max2 = max;
            int end = size - i;
            for (int j = 0; j < end; j++) {
                long v = list.get(j);
                min2 = Math.min(min2, v);
                max2 = Math.max(max2, v);
            }
            int i2 = i / 2;
            for (int j = 0; j < i2; j++) {
                long v = list.get(end + j) + list.get(end + i - 1 - j);
                min2 = Math.min(min2, v);
                max2 = Math.max(max2, v);
            }
            ans = Math.min(ans, max2 - min2);
        }
        System.out.println(ans);
    }
}

ここまで89分52秒＋0ペナ。48位。



EとFは解けず。
Eは、各頂点について祖先が選べないくらいしかわからず、どう数えればいいのかさっぱりだった。
Fはほぼ問題読んだだけ。こちらもどう数えればいいのかわかる気がしなかったのですぐDやEに戻った。



最終結果：ABCDの4完、89分52秒、65位、パフォーマンス2774
レート変動：1969→2080（+111）


ARC118と同様に、3完でもプラスなのに4完できて大きくプラスという結果。
引き続き、ABCがUnratedになる権利を得られた。

ただ、今回はこのブログを書いている間にBとDで欠陥を見つけており、絶妙にテストケースが弱かったから通ったものの、通らなかったときに、ちょっとしたミスなのか完全に考察が間違っているのか、きちんと判断できたのかはあまり自信がない。

最近は順位表を見ると周りが解くスピードが速すぎて絶望することの方が多いのだが、今回は順位表を確認する度に順位が想像よりだいぶ高く（Bまで30分近くかかっていても2桁、Cまで40分近くかかっていて1ページ目とは全く思わず）、人々との得意分野の乖離を感じなくもない。