AtCoder Beginner Contest 199(Rated範囲外)

ABC

コンテスト前のレート：2008
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：355位（1500点、98分08秒）


最初にD問題を開いてみるが、すぐに解けそうになかったので、1分遅れて普通に前から解き始める。

A - Square Inequality

問題

思考過程
  1. 問題文の通り判定する。
import java.util.Scanner;

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

        if (a * a + b * b < c * c) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分47秒＋0ペナ。3276位。


B - Intersection

問題

思考過程
  1. A_i \leq x \leq B_iという条件をN個全部満たす必要があるということは、max(A_i) \leq x \leq min(B_i)と言い換えられる。
  2. max(A_i) \gt min(B_i)の場合に注意し、答えがマイナスにならないようにする。
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();
        }
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        sc.close();

        int ma = 0;
        for (int i = 0; i < n; i++) {
            ma = Math.max(ma, a[i]);
        }
        int mb = 10000;
        for (int i = 0; i < n; i++) {
            mb = Math.min(mb, b[i]);
        }
        System.out.println(Math.max(mb - ma + 1, 0));
    }
}

ここまで3分59秒＋0ペナ。984位。


C - IPFL

問題

思考過程
  1. 前半と後半を入れ替える処理を実際に行ってしまうとTLE。
  2. 前半後半を入れ替えているかどうかだけ管理しておき、入れ替わっていたら(A_i+N)\%2N文字目と(B_i+N)\%2N文字目の入れ替えを行うようにして上手くいきそうか考え、多分問題なさそうなのでそれでやってみる。
import java.io.BufferedReader;
import java.io.InputStreamReader;

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());
        char[] s = br.readLine().toCharArray();
        int q = Integer.parseInt(br.readLine());
        int[] t = new int[q];
        int[] a = new int[q];
        int[] b = new int[q];
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            a[i] = Integer.parseInt(sa[1]) - 1;
            b[i] = Integer.parseInt(sa[2]) - 1;
        }
        br.close();

        int n2 = n * 2;
        boolean flg = false;
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                int ai = a[i];
                int bi = b[i];
                if (flg) {
                    ai = (ai + n) % n2;
                    bi = (bi + n) % n2;
                }
                char tmp = s[ai];
                s[ai] = s[bi];
                s[bi] = tmp;
            } else {
                flg = !flg;
            }
        }
        if (flg) {
            StringBuilder sb = new StringBuilder();
            for (int i = n; i < n2; i++) {
                sb.append(s[i]);
            }
            for (int i = 0; i < n; i++) {
                sb.append(s[i]);
            }
            System.out.println(sb.toString());
        } else {
            System.out.println(String.valueOf(s));
        }
    }
}

ここまで11分59秒＋0ペナ。685位。


D - RGB Coloring 2

問題
BFSで連結成分内を調べるならUnionFindを持ち出す必要はなくなったが、迷走した結果なので仕方ない。

思考過程
  1. グラフが連結でも木でもなくて、計算で求められる気がしない。
  2. 3^N全探索して、条件を満たすものをカウントするのを一応考えるが、3^{20}は少し大きすぎる。
  3. 基本路線としては、連結成分ごとにDFSで3^M（Mは連結成分のサイズ）全探索をするが、隣接頂点と同じ色は探索しないことでそれなりに枝刈りされることを期待する。
    　
  4. 連結成分に含まれている頂点をランダムな順番で調べたせいか、WAが結構出てしまい（TLEも1ケースあり）、ちゃんと隣接している順番に調べる必要があるかと思ってBFSを追加してみる。
  5. WAの数がむしろ増えて意味不明になったが、よく見たら添え字ミスをしている箇所があり、直したらAC。

上記5.を直して4.を直さなかった場合は、ちゃんとO(2^NN)に落ちずにTLEするのではないかと思われる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {
    static List<List<Integer>> list;
    static int[] col;
    static int cnt;
    static List<Integer> g2;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        DSU uf = new DSU(n);
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            list.get(a).add(b);
            list.get(b).add(a);
            uf.merge(a, b);
        }
        br.close();

        List<List<Integer>> g = uf.groups();
        long ans = 1;
        for (List<Integer> gg : g) {
            // 1つの連結成分に対する処理
            // 4.始点から近い順に調べるためのリストを作るBFS
            g2 = new ArrayList<>(gg.size());
            Queue<Integer> que = new ArrayDeque<>();
            int f = gg.get(0);
            que.add(f);
            g2.add(f);
            boolean[] v = new boolean[n];
            v[f] = true;
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int i : list.get(cur)) {
                    if (!v[i]) {
                        que.add(i);
                        g2.add(i);
                        v[i] = true;
                    }
                }
            }
            // 3
            col = new int[n];
            cnt = 0;
            dfs(0);
            ans *= cnt;
        }
        System.out.println(ans);
    }

    static void dfs(int idx) {
        if (idx == g2.size()) {
            cnt++;
            return;
        }
        int x = g2.get(idx);
        // 頂点xに色1～3を入れようとしてみる
        for (int i = 1; i <= 3; i++) {
            boolean flg = true;
            for (int t : list.get(x)) {
                if (col[t] == i) {
                    flg = false;
                    break;
                }
            }
            // 隣接頂点に同じ色がない場合
            if (flg) {
                col[x] = i; // 5.添え字ミスしていた箇所
                dfs(idx + 1);
            }
        }
        col[x] = 0; // 5.添え字ミスしていた箇所
    }
}

// 以下ACLを移植したDSU

提出
ここまで47分29秒＋2ペナ。368位。



E問題は5～10分ほど考えて全然わからず。
Z_i個より多い場合を数えたり、包除的な何かをしたりするのかと思ったりした。
DPとは全く気付かなかった。


残り時間45分ほどはF問題をやっていて、一応実装までしてみたが、サンプルも合わず。
各頂点について、頂点1～Nがどれだけ寄与するのか、係数をダブリングをすることまで考えていたのに、何故か行列累乗を貼ろうとしなかった。
仮にそこまでしようとしていたとしても、行列のお気持ちが全然わかってなくて、行列を作る部分がなかなかできないのだが。



最終結果：ABCDの4完、57分29秒、656位、パフォーマンス1710相当
レート変動：2008（Unrated）


また今日も黄パフォ相当には程遠い結果で、実質ABC6連敗。
本当にいつまで黄色維持していられるんだろう。ARCで失敗しなければいいだけだけど。