AtCoder Beginner Contest 278(Rated範囲外)

ABC

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

A - Shift

問題

思考過程
  1. AのK+1番目から末尾までの要素と、0をK個出力する。
  2. これだとK \gt Nの場合0を多く出力してしまうので、0をmin(K, N)個とする。
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 k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

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

ここまで2分16秒＋0ペナ。946位。


B - Misjudge the Time

問題

思考過程
  1. 現在時刻から1分ずつ増やしていき、条件を満たしたところで終了させる全探索を行う。
  2. AB:CDからAC:BDを得るには、ABやCDの各桁の値を10で割ったり余りを取ったりして上手く取り出す。
import java.util.Scanner;

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

        int start = h * 60 + m;
        for (int i = start; ; i++) {
            int x = i / 60 % 24;
            int y = i % 60;
            int x2 = x / 10 * 10 + y / 10;
            int y2 = x % 10 * 10 + y % 10;
            if (x2 < 24 && y2 < 60) {
                System.out.println(x + " " + y);
                return;
            }
        }
    }
}

ここまで7分39秒＋0ペナ。401位。


C - FF

問題
一瞬第1回PAST-Eかと思ったけどもっと簡単だった。

思考過程
  1. 制約が大きいので配列は使えない。Map＜ユーザー、Set＜フォロー対象＞＞の形で管理する。
  2. クエリ1：ユーザーAのSetにBを追加する。
  3. クエリ2：ユーザーAのSetからBを削除する。
  4. クエリ3：ユーザーA, BそれぞれのSetに相手が存在するか確認する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

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 q = Integer.parseInt(sa[1]);
        int[] t = new int[q];
        int[] a = new int[q];
        int[] b = new int[q];
        for (int i = 0; i < q; i++) {
            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();

        Map<Integer, Set<Integer>> map = new HashMap<>();
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                Set<Integer> set = map.get(a[i]);
                if (set == null) {
                    set = new HashSet<>();
                    map.put(a[i], set);
                }
                set.add(b[i]);

            } else if (t[i] == 2) {
                Set<Integer> set = map.get(a[i]);
                if (set != null) {
                    set.remove(b[i]);
                }

            } else {
                Set<Integer> set1 = map.get(a[i]);
                Set<Integer> set2 = map.get(b[i]);
                if (set1 != null && set1.contains(b[i]) &&
                        set2 != null && set2.contains(a[i])) {
                    pw.println("Yes");
                } else {
                    pw.println("No");
                }
            }
        }
        pw.flush();
    }
}

ここまで12分40秒＋0ペナ。376位。


D - All Assign Point Add

問題

思考過程
  1. これもデータ構造Map＜index、加算値＞とクエリ1の代入値を管理する。
  2. クエリ1：代入値にxを設定し、Mapを空にする。
  3. クエリ2：Mapのiにxを加算。
  4. クエリ3：元のA_iの値もしくは代入値にMapから取得した値を加算して出力。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

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(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        int q = Integer.parseInt(br.readLine());

        Map<Integer, Long> map = new HashMap<>();
        long all = -1;
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            if (t == 1) {
                all = Integer.parseInt(sa[1]);
                map.clear();

            } else if (t == 2) {
                int iq = Integer.parseInt(sa[1]) - 1;
                int x = Integer.parseInt(sa[2]);
                map.put(iq, map.getOrDefault(iq, 0L) + x);

            } else {
                int iq = Integer.parseInt(sa[1]) - 1;
                if (all == -1) {
                    pw.println(a[iq] + map.getOrDefault(iq, 0L));
                } else {
                    pw.println(all + map.getOrDefault(iq, 0L));
                }
            }
        }
        pw.flush();
        br.close();
    }
}

ここまで19分10秒＋0ペナ。253位。


E - Grid Filling

問題

思考過程
  1. 色ごとに二次元累積和をすれば、塗りつぶし範囲1箇所につきO(N)で求められ、全体でO(HWN)となる。
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));
        String[] sa = br.readLine().split(" ");
        int h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int n = Integer.parseInt(sa[2]);
        int x = Integer.parseInt(sa[3]);
        int y = Integer.parseInt(sa[4]);

        int[][][] b = new int[n][h + 1][w + 1]; // 二次元累積和用
        int[] c = new int[n]; // 各色の全体の個数
        for (int i = 0; i < h; i++) {
            sa = br.readLine().split(" ");
            for (int j = 0; j < w; j++) {
                int a = Integer.parseInt(sa[j]) - 1;
                b[a][i + 1][j + 1]++;
                c[a]++;
            }
        }
        br.close();

        // 二次元累積和
        for (int k = 0; k < n; k++) {
            for (int i = 0; i <= h; i++) {
                for (int j = 0; j < w; j++) {
                    b[k][i][j + 1] += b[k][i][j];
                }
            }
            for (int j = 0; j <= w; j++) {
                for (int i = 0; i < h; i++) {
                    b[k][i + 1][j] += b[k][i][j];
                }
            }
        }

        for (int i = 0; i <= h - x; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j <= w - y; j++) {
                int ans = 0;
                for (int k = 0; k < n; k++) {
                    // 塗りつぶし範囲内の色kの個数が全体より少ないか
                    int cnt = b[k][i + x][j + y]
                            - b[k][i][j + y]
                            - b[k][i + x][j]
                            + b[k][i][j];
                    if (c[k] > cnt) {
                        ans++;
                    }
                }
                sb.append(ans).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

ここまで30分23秒＋0ペナ。158位。


F - Shiritori

問題

思考過程
  1. 巡回セールスマン問題とほぼ同様の形で、「dp[x][y]:=既に使用した文字列の集合がxで最後の文字がyの時、次の手番の人が勝利できるか」と定義してみる。
  2. これを後ろから埋めていきたいので、メモ化再帰をする。
  3. 勝利できないいずれかの状態に遷移できる場合、勝利できることになる。
import java.util.Scanner;

public class Main {
    static int n;
    static int[] a, b;
    static int[][] dp;

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

        a = new int[n]; // 先頭文字
        b = new int[n]; // 末尾文字
        for (int i = 0; i < n; i++) {
            a[i] = s[i].charAt(0) - 'a';
            b[i] = s[i].charAt(s[i].length() - 1) - 'a';
        }

        int end = 1 << n;
        dp = new int[end][26]; // 0:未判定、1:勝利、2:敗北
        int res = dfs(0, 0);
        if (res == 1) {
            System.out.println("First");
        } else {
            System.out.println("Second");
        }
    }

    static int dfs(int x, int y) {
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        int ret = 2;
        for (int i = 0; i < n; i++) {
            if (x == 0 || (x >> i & 1) == 0 && a[i] == y) {
                int res = dfs(x + (1 << i), b[i]);
                if (res == 2) {
                    ret = 1;
                    break;
                }
            }
        }
        return dp[x][y] = ret;
    }
}

ここまで42分02秒＋0ペナ。117位。



Gは5～10分ほど考えてみたが、わかる気がしなかったのでAHCのために撤退。
初手で同じ長さの領域2つに分割できるなら後は真似すれば勝てるが、初手でそうできない場合がわからず。
1が選べれば後手を選択、選べなければ長さAとA+1に分ければよかったんだろうか。
くらいはぼんやりと考えたが、後手を選んだ後の実装のことを考える気力があるならAHCに使いたかった。



最終結果：ABCDEFの6完2000点、42分02秒、138位、パフォーマンス2348相当
レート変動：2000（Unrated）


初めてコンテスト終了と同時に記事を書き終わっていた。
公開はAtCoder Replayの結果を確認できるのなどを待ってからにはなったが。