AtCoder Beginner Contest 247(Rated範囲外)

ABC

コンテスト前のレート：2000
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：337位（2000点、61分45秒）

A - Move Right

問題

思考過程
  1. "0"にSの前から3文字を連結した文字列を出力する。
import java.util.Scanner;

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

        System.out.println("0" + s.substring(0, 3));
    }
}

ここまで0分55秒＋0ペナ。128位。


B - Unique Nicknames

問題

思考過程
  1. 全体で重複が出ないようにs_i, t_iから一方を選んでいく問題？難しくない？と思ったら違った。
  2. 問題をよく読めば、他の人がs_j, t_jのどちらを選ぶかに関わらず、a_iはs_j, t_jどちらとも一致してはいけないということだった。
  3. よって、素直に1人ずつ順番に判定を行っていくことにする。
  4. s_iと一致するs_jまたはt_jが存在するかどうか、t_iと一致するs_jまたはt_jが存在するかどうかをそれぞれ調べ、両方とも存在するような人が1人でもいれば"No"。
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();
        String[] s = new String[n];
        String[] t = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
            t[i] = sc.next();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            boolean fs = true;
            boolean ft = true;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    if (s[i].equals(s[j]) || s[i].equals(t[j])) {
                        fs = false;
                    }
                    if (t[i].equals(s[j]) || t[i].equals(t[j])) {
                        ft = false;
                    }
                }
            }
            if (!fs && !ft) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで4分46秒＋0ペナ。131位。


C - 1 2 1 3 1 2 1

問題

思考過程
  1. 再帰関数にすることも一瞬考えたが、前回の列を取っておくことで題意通り連結する処理を繰り返すことができるので、その方が書きやすそう。
import java.util.ArrayList;
import java.util.List;
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();
        sc.close();

        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            List<Integer> wk = new ArrayList<>();
            wk.addAll(list);
            wk.add(i);
            wk.addAll(list);
            list = wk;
        }

        StringBuilder sb = new StringBuilder();
        for (int e : list) {
            sb.append(e).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで6分56秒＋0ペナ。82位。


D - Cylinder

問題

思考過程
  1. クエリ1ではx, cをセットにしてQueueに追加する。
  2. クエリ2では、Queueの先頭がc個より多く残っていれば残数を更新するだけ、c個以下であれば取り出す。
  3. ということを上手くやっていけば、どちらのクエリも全体でO(N)となる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        Queue<Obj> que = new ArrayDeque<>();
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]);
            if (a == 1) {
                Obj o = new Obj();
                o.x = Integer.parseInt(sa[1]);
                o.c = Integer.parseInt(sa[2]);
                que.add(o);
            } else {
                int c = Integer.parseInt(sa[1]);
                long ans = 0;
                while (c > 0) {
                    Obj o = que.peek();
                    int m = Math.min(c, o.c);
                    ans += (long) o.x * m;
                    o.c -= m;
                    c -= m;
                    if (o.c == 0) {
                        que.poll();
                    }
                }
                pw.println(ans);
            }
        }
        pw.flush();
        br.close();
    }

    static class Obj {
        int x, c;
    }
}

ここまで11分54秒＋0ペナ。90位。


E - Max Min

問題

思考過程
  1. Xより大きい値またはYより小さい値が出てくる箇所を含む区間は駄目なので、そこで区切ったとして、Y \leq A_i \leq Xであるものとして考える。
  2. A_L=X、A_R=Y（もしくはその逆）となるL, Rの組み合わせを取っ掛かりにすることを考えると、重複を排除するのが難しそう。
    　
  3. Lを固定した時に条件を満たす最小のRがわかれば、Rがそれ以上次の区切り未満の範囲では全て満たすので、次の区切りとの差を求めればよい。
  4. あらかじめA_i=X、A_i=Y、(A_i \lt Y or X \lt A_i)となるiをそれぞれTreeSetに入れておけば、各Lに対して次のX, Y, 区切りの位置がわかるので、それを元に計算する。
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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int x = Integer.parseInt(sa[1]);
        int y = Integer.parseInt(sa[2]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        TreeSet<Integer> l = new TreeSet<>();
        TreeSet<Integer> r = new TreeSet<>();
        TreeSet<Integer> ng = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            if (a[i] < y) ng.add(i);
            if (a[i] == y) l.add(i);
            if (a[i] == x) r.add(i);
            if (a[i] > x) ng.add(i);
        }
        l.add(n);
        r.add(n);
        ng.add(n);

        long ans = 0;
        for (int i = 0; i < n; i++) {
            int l1 = l.ceiling(i);
            int r1 = r.ceiling(i);
            int n1 = ng.ceiling(i);
            int m = Math.max(l1, r1); // 次のY,Xの内遠い方
            int v = Math.max(n1 - m, 0); // 遠い方～区切り前の個数
            ans += v;
        }
        System.out.println(ans);
    }
}

ここまで24分55秒＋0ペナ。108位。


F - Cards

問題

思考過程
  1. 全然解ける気がしないけど、とりあえずp_iとq_iの間に辺を張ったグラフをイメージしてみる？
  2. 例２では2つの連結成分ができる。連結成分ごとに独立に条件を満たす通り数を求めて掛け合わせればよい。あとは1つの連結成分について考える。
    　
  3. 1つの連結成分はサイクルの形になっていることを利用すると、DPをすれば求められそう？
  4. 「DP[i]:=i番目まで見た時の通り数」（これを最後のカードを選んだかどうか、最初のカードを選んだかどうかで分けておく）とすると、2連続で選ばないのはNGとして遷移を書ける。
  5. 答えは最初と最後の少なくとも一方を選んだものの合計となる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    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]);
        sa = br.readLine().split(" ");
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sa[i]) - 1;
        }
        sa = br.readLine().split(" ");
        int[] q = new int[n];
        for (int i = 0; i < n; i++) {
            q[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        int mod = 998244353;
        DSU uf = new DSU(n);
        for (int i = 0; i < n; i++) {
            uf.merge(p[i], q[i]);
        }
        List<List<Integer>> grps = uf.groups();
        long ans = 1;
        for (List<Integer> g : grps) {
            int size = g.size();
            long[] dp00 = new long[size]; // 最後を選ぶ、最初を選ぶ
            long[] dp01 = new long[size]; // 最後を選ぶ、最初を選ばない
            long[] dp10 = new long[size]; // 最後を選ばない、最初を選ぶ
            long[] dp11 = new long[size]; // 最後を選ばない、最初を選ばない
            dp00[0] = 1;
            dp11[0] = 1;
            for (int i = 1; i < size; i++) {
                dp00[i] = dp00[i - 1] + dp10[i - 1];
                dp00[i] %= mod;
                dp01[i] = dp01[i - 1] + dp11[i - 1];
                dp01[i] %= mod;
                dp10[i] = dp00[i - 1];
                dp11[i] = dp01[i - 1];
            }
            // dp11（最初も最後も選ばない）以外の合計
            long val = dp00[size -1] + dp10[size - 1] + dp01[size - 1];
            val %= mod;
            ans *= val;
            ans %= mod;
        }
        System.out.println(ans);
    }
}

// 以下ACLを移植したDSU

提出
ここまで45分25秒＋0ペナ。111位。



Gは最小費用流を使うことを考え、ACLのMinCostFlowのslopeを使えばよさそう（最初は使わずに150回グラフ構築していたらやっぱりTLE）なことまでわかったが、3/32ケースだけWAが取れず。
(容量, コスト)を、始点→(1, 0)→所属大学→(1, BIG-C_i)→人→(1, BIG-C_i)→得意分野→(1, 0)→終点のようにして、求まった答えを半分にすればいいのではと思ったのだが、これだとどこかおかしいらしい？
ちゃんと始点→(1, 0)→所属大学→(1, 0)→人→(1, BIG-C_i)→人→(1, 0)→得意分野→(1, 0)→終点にすればよかったか・・・。
と思ったけど後でそれを試しても変わらず。どうやらslopeの使い方がおかしいらしいがよくわからず。（人の提出を見ると、slopeの結果そのままではなく何かよくわからない計算をしている）



最終結果：ABCDEFの6完2000点、45分25秒、263位、パフォーマンス2115相当
レート変動：2000（Unrated）


前日にぎりぎり青落ちしなかったと思ったらFまでずっと100位前後で久しぶりにとてもスムーズに6問解くことができた。
Gは最小費用流まで見えてたのにあと何が駄目だったのか・・・。
ライブラリでどういう結果が得られるのかをきちんと把握できていないことが駄目か。