AtCoder Beginner Contest 272

コンテスト前のレート:1977
レート通りのパフォーマンスが得られる順位:337位(1500点、34分38秒)

A - Integer Sum

問題

思考過程
  1. そのまんまfor文回して合計を求めるだけ。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += a[i];
        }
        System.out.println(ans);
    }
}

ここまで0分45秒+0ペナ。661位。


B - Everyone is Friends

問題

思考過程
  1. _{k_i}C_2通りの組み合わせを全て調べ、同じ舞踏会に参加した組をN人の総当たり戦の表に記録していくイメージ。
  2. 表の右上半分が全て埋まっているかどうかを調べる。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] k = new int[m];
        int[][] x = new int[m][];
        for (int i = 0; i < m; i++) {
            k[i] = sc.nextInt();
            x[i] = new int[k[i]];
            for (int j = 0; j < k[i]; j++) {
                x[i][j] = sc.nextInt() - 1;
            }
        }
        sc.close();

        boolean[][] b = new boolean[n][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k[i]; j++) {
                for (int j2 = 0; j2 < j; j2++) {
                    b[x[i][j2]][x[i][j]] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (!b[j][i]) {
                    System.out.println("No");
                    return;
                }
            }
        }
        System.out.println("Yes");
    }
}

ここまで3分31秒+0ペナ。172位。


C - Max Even

問題

思考過程
  1. Aを奇数の集合と偶数の集合に分ける。降順に取り出せるPriorityQueueを使うのがよさそう。
  2. それぞれの集合について、要素数2個以上の場合に大きい要素から順に2つ取り出して和を求め、大きい方が答え。
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        PriorityQueue<Integer> odd = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> even = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 0) {
                even.add(a[i]);
            } else {
                odd.add(a[i]);
            }
        }

        int ans = -1;
        if (odd.size() >= 2) {
            int v1 = odd.poll();
            int v2 = odd.poll();
            ans = v1 + v2;
        }
        if (even.size() >= 2) {
            int v1 = even.poll();
            int v2 = even.poll();
            ans = Math.max(ans, v1 + v2);
        }
        System.out.println(ans);
    }
}

ここまで6分30秒+0ペナ。218位。


D - Root M Leaper

問題

思考過程
  1. やることはただのBFS。だが遷移部分が大変。
  2. A^2 + B^2 = Mとなる(x, y)の組をあらかじめ求めておき、各組について(+x, +y), (+x, -y), (-x, +y), (-x, -y)の遷移を行う。
  3. あらかじめ求める部分は、x0から単調増加、y\sqrt{M}=1000から単調減少させながら条件を満たす値を探せばO(\sqrt{M})
    だが後から思えば\sqrt{M}ではなくNまでで十分だったし、なんならO(N^2)でも問題なかった。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.close();

        List<Integer> listX = new ArrayList<>();
        List<Integer> listY = new ArrayList<>();
        int y = 1000;
        for (int x = 0; x <= 1000; x++) {
            int xx = x * x;
            if (xx > m) {
                break;
            }
            while (xx + y * y > m) {
                y--;
            }
            if (xx + y * y == m) {
                listX.add(x);
                listY.add(y);
            }
        }

        int[] sx = {1, 1, -1, -1};
        int[] sy = {1, -1, 1, -1};

        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        Queue<Integer> que = new ArrayDeque<>();
        que.add(0);
        a[0][0] = 0;
        while (!que.isEmpty()) {
            int cur = que.poll();
            int cx = cur / n;
            int cy = cur % n;
            for (int i = 0; i < listX.size(); i++) {
                int dx = listX.get(i);
                int dy = listY.get(i);
                for (int k = 0; k < 4; k++) {
                    int nx = cx + dx * sx[k];
                    int ny = cy + dy * sy[k];
                    if (nx < 0 || n <= nx || ny < 0 || n <= ny) {
                        continue;
                    }
                    if (a[nx][ny] == -1) {
                        a[nx][ny] = a[cx][cy] + 1;
                        que.add(nx * n + ny);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(a[i][j]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

ここまで16分29秒+0ペナ。170位。


E - Add and Mex

問題
しばらく何もわからず、先にFも問題だけは読んでいた。(Fもわからずすぐ戻ってきた)

思考過程
  1. 各要素について、「何回かの操作で0にできるか調べ、c (1 \leq c \leq M)回でできるならans[c]1にする」ということを0から順に更新がなくなるまでやってみたらどうか?
  2. 答えの最大値をXとしてO(NX)かかるが、Xはそんなに大きくならないのでは? →TLE
     
  3. 各要素が操作の過程で0Nになる部分だけに注目することができれば、調和級数O(NlogN)になる。
  4. それらを全部Setに突っ込んでしまえば、後は普通に0から調べていってMexを求めることができそう。 →1579ms、261MBでなんとか通る
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        List<Set<Integer>> list = new ArrayList<>(m + 1);
        for (int i = 0; i <= m; i++) {
            list.add(new HashSet<>());
        }
        for (int i = 1; i <= n; i++) {
            int d = 0;
            if (a[i] < 0) {
                d -= a[i] / i;
            }
            if (d == 0) {
                d = 1;
            }
            for (int j = d; j <= m; j++) {
                int v = a[i] + i * j;
                if (v < 0) {
                    continue;
                }
                if (v > n) {
                    break;
                }
                list.get(j).add(v);
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i <= m; i++) {
            Set<Integer> set = list.get(i);
            for (int j = 0; ; j++) {
                if (!set.contains(j)) {
                    pw.println(j);
                    break;
                }
            }
        }
        pw.flush();
    }
}

ここまで46分26秒+1ペナ。344位。



以降はFとGを両方見てG重視で解こうとしていたが、どちらも解けず。

Gは2要素の全組み合わせについて差に含まれる素因数を全探索していたら間に合いそうにないなで止まっていた。

FはS+S+T+TにSuffixArrayを使うことまで思い付いていたが、それだけだと半分くらいWA。(T+T+S+Sだと8割近く通った)
S=Tの場合などにT由来のindexが先に来てしまってカウントできておらず、小細工を試みるもAC数変わらず。
同率部分を上手くカウントすることばかり考えており、間にダミーを挟めば上手くいくとは全く考えられなかった。



終結果:ABCDEの5完1500点、51分26秒、464位、パフォーマンス1823
レート変動:1977→1962(-15)


Eが18分で解ければノルマ通り。
TLE解法とAC解法に15分ずつかかっていたので、最初からAC解法に行けていればぎりぎりなんとかなったかどうか。

問題の見た目と配点でFよりGを優先してしまったが、Fに集中していればなんとかできた可能性がもう少しあったかも?