AtCoder Beginner Contest 236(Rated範囲外)

コンテスト前のレート：2044
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：309位（1600点、66分37秒）

A - chukodai

問題

思考過程

1. をchar配列で受け取り、番目と番目を入れ替える。

import java.util.Scanner;

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

        char c = s[a];
        s[a] = s[b];
        s[b] = c;
        System.out.println(s);
    }
}

ここまで0分53秒＋0ペナ。423位。

B - Who is missing?

問題

思考過程

1. 入力された値の個数を保持しておく。
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[] c = new int[n + 1];
        int n4 = n * 4 - 1;
        for (int i = 0; i < n4; i++) {
            c[sc.nextInt()]++;
        }
        sc.close();

        for (int i = 1; i <= n; i++) {
            if (c[i] != 4) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで2分29秒＋0ペナ。355位。

C - Route Map

問題

思考過程

1. 各がに含まれているかどうかを調べたい。
2. をSetの形で持っておけば、各についてで上記1.の判定ができる。

import java.io.PrintWriter;
import java.util.HashSet;
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();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }
        Set<String> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            set.add(sc.next());
        }
        sc.close();

        PrintWriter pw = new PrintWriter(System.out);
        for (String str : s) {
            if (set.contains(str)) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
    }
}

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

D - Dance

問題
解けず。

思考過程

1. 制約小さいし、あり得る組合せを全探索すればいいのだろう。
2. まだ人組に決めていない人の中から人の組を選びながら再帰を行うことにする。　→15/28ケースTLE
3. 同じ人の集合が残っている状態への探索が多いのかも。メモ化をしてみる。　→11/28ケースTLE
4. を計算してみたら、近くになったのでこれだと無理っぽい。

解説を見たら、最初の提出に下記コード中「★」の箇所のbreakを足すだけでよかった。

import java.util.Scanner;

public class Main {
    static int n, n2, all;
    static int[][] a;
    static int ans;

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

        all = (1 << n2) - 1;
        dfs(0, 0);
        System.out.println(ans);
    }

    static void dfs(int used, int x) {
        if (used == all) {
            ans = Math.max(ans, x);
            return;
        }

        for (int i = 0; i < n2; i++) {
            if ((used >> i & 1) == 0) {
                for (int j = i + 1; j < n2; j++) {
                    if ((used >> j & 1) == 0) {
                        dfs(used + (1 << i) + (1 << j), x ^ a[i][j]);
                    }
                }
                break; // ★
            }
        }
    }
}

2回目TLEの時点でDを捨て、EとFを見てできそうな方からやることに。

Eは中央値の方は二分探索をしてmid以上を必ず取り、mid未満なら必ず1個飛ばす貪欲で判定すればできそうだと思ったが、平均値の方がよくわからず。
最終的に時間切れぎりぎりで嘘貪欲を投げてやっぱり通らず。

F - Spices

問題

思考過程

1. 掃き出し法をイメージすると、基底個の選び方の内、コストの合計が最小となるものを選べばよさそう。
2. これはクラスカル法と同じロジックで、コストの小さい順に見ていって、基底となり得るなら選択するということを、回選択するまで行えばよさそう。
3. ある値を選択してよいかどうかは、それまでに選択済みの値を組み合わせて作れないかどうかで判定する。　個選ぶごとに作れている値は倍になっていっているはず。

import java.io.BufferedReader;
import java.io.InputStreamReader;
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());
        int n2 = 1 << n;
        String[] sa = br.readLine().split(" ");
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.c - o2.c);
        for (int i = 0; i < n2 - 1; i++) {
            Obj o = new Obj();
            o.i = i + 1;
            o.c = Integer.parseInt(sa[i]);
            que.add(o);
        }
        br.close();

        long ans = 0;
        Set<Integer> set = new HashSet<>();
        set.add(0);
        while (!que.isEmpty()) {
            Obj o = que.poll();
            if (!set.contains(o.i)) {
                Integer[] arr = set.toArray(new Integer[0]);
                for (int e : arr) {
                    set.add(o.i ^ e);
                }
                ans += o.c;
            }
        }
        System.out.println(ans);
    }

    static class Obj {
        int i, c;
    }
}

ABCFと解いた時点で81分06秒＋0ペナ。500位。

最終結果：ABCFの4完1100点、81分06秒、610位、パフォーマンス1752相当
レート変動：2044（Unrated）

最後にEを通すことができればパフォ2030くらい。
Dはdiff1190だったようで、本当に一体いつになったら緑diffを落とさなくなるんだろう・・・。
未だに年間3問くらい落としてる。