AtCoder Regular Contest 111

コンテスト前のレート:1832
レート通りのパフォーマンスが得られる順位:481位(1300点、111分58秒)

A - Simple Math 2

問題
1問目から大苦戦。下手したらNoSubになるところだった。
なお、思考過程2に進むまでに30分以上かかっている。

思考過程
  1. 10000Mで割った商と余りを10^{N-4} \% M倍して・・・などということをやっていたりしたが、商の方はよいが余りの方をそのように処理するのはおかしい。
     
  2. そもそも求めようとしている値と、よくある10^N \% Mはどう違うのか?
  3. 上記2の値を求めた後にMで割ることはできないので、先に分母分子をM倍してみたら? Mの制約が微妙に小さいのは2乗するからか?
  4. とりあえず10^N \% M^2を求めつつ(最後にMで割った余りを取ることを考えたら、分子のM倍は省略できる)、あとはそれらしいことをやって例3を合わせる。
import java.util.Scanner;

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

        int m2 = m * m;
        long ans = power(10, n, m2);
        System.out.println(ans / m % m);
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }
}

ここまで58分22秒+0ペナ。1066位。


B - Reversible Cards

問題
A問題にあまりに時間がかかりすぎたので、B問題が解けるまでNoSubを視野に入れて提出を保留していた。
結局58分20秒頃にAとBを2問まとめて提出したが、B問題はWA。

思考過程
  1. まず一旦全部aを選び、被っているものをbに変えていくことを念のため考えてみるが、変えていく順序で上手くいくかが変わったり、連鎖的に変えていかないと上手くいかなかったりするケースがありそうで、できるとは思えない。
  2. DPも上手く状態を整理できる気がしない。
  3. 最大流とかを使えないかとも思ったが、制約が大きいので無理そうな気がする。
     
  4. 上記1の、連鎖的に決まっていくケースを考えてみる。
  5. abを辺としたグラフを作ってみると、各辺についてどちらかの頂点を選ぶことを行い、全体で選ぶ頂点の数を最大化する問題になる。
  6. これは、上手く選べば連結成分内の頂点を漏れなく選べるので、辺が存在する連結成分の頂点数の和を求めればよさそう。 →WA
     
  7. 連結成分の頂点数と、連結成分に対して統合を行った回数(=辺の数。頂点数-1回の可能性がある)の小さい方を求める必要があった。
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));
		int n = Integer.parseInt(br.readLine());
		DSU dsu = new DSU(400000);
		for (int i = 0; i < n; i++) {
			String[] sa = br.readLine().split(" ");
			int a = Integer.parseInt(sa[0]) - 1;
			int b = Integer.parseInt(sa[1]) - 1;
			dsu.merge(a, b);
		}
		br.close();

		List<List<Integer>> g = dsu.groups();
		int ans = 0;
		for (List<Integer> g2 : g) {
			int s = g2.size();
			int l = dsu.leader(g2.get(0));
			int max = dsu.t[l]; // lを含む連結成分にmergeを行っている回数
			ans += Math.min(s, max);
		}
		System.out.println(ans);
	}
}

// 以下、ACLのDisjoint Set Unionに配列tに関する処理を追加

提出
ここまで64分11秒+1ペナ。559位。


C - Too Heavy

問題
方針は比較的すぐ立ったが、実装で添え字周りで混乱して時間かかってしまった。

思考過程
  1. 重さの制約を抜きにすれば、1番目から順に正しい荷物を持たせていけば最小回数になりそう。
  2. 体重でソートして体重が軽い順に上記を行えば、正しい荷物を持たせる代わりに受け取る荷物の重さが、元々持っていた人の体重未満なので、元々一度も交換できない場合以外で、受け取った人がそれ以上交換できなくなることはない。
  3. 交換の操作を管理しながらシミュレーションしていく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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));
        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]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;       // 人の番号
            o.a = a[i];    // 人iの体重
            o.w = b[p[i]]; // 人iが持っている荷物の重さ
            o.p = p[i];    // 人iが持っている荷物の番号
            arr[i] = o;
        }

        Arrays.sort(arr, (o1, o2) -> o1.a - o2.a); // 体重の昇順
        // 荷物idxをarrの何番目の人が持っているか
        // ※arrのindexを示しており、人の番号ではない
        int[] pi = new int[n];
        for (int i = 0; i < n; i++) {
            pi[arr[i].p] = i;
        }

        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Obj o = arr[i];
            if (o.p == o.i) {
                continue;
            }
            if (o.a <= o.w) {
                System.out.println(-1);
                return;
            }
            int ni = pi[o.i]; // 正しい荷物を持っている人のindex
            int nw = arr[ni].w;
            int np = arr[ni].p;
            pi[o.i] = i;
            arr[ni].w = o.w;
            arr[ni].p = o.p;
            pi[o.p] = ni;
            o.w = nw;
            o.p = np;
            list.add((o.i + 1) + " " + (arr[ni].i + 1));
        }
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(list.size());
        for (String s : list) {
            pw.println(s);
        }
        pw.flush();
    }

    static class Obj {
        int i, a, w, p;
    }
}

ここまで102分36秒+1ペナ。443位。


D - Orientation

問題
解けず。
以下の思考過程3の実装に苦戦している間に時間切れ。

思考過程
  1. とりあえず連結成分にごとに分ける。
  2. 構成される有効グラフがどのような形になるのかを考える。
  3. まず連結成分内で最小のcの集合で長さcのサイクルを作る。
  4. それ以外は、cの小さい順に見ていき、cの頂点からはc-1のいずれかの頂点へつながる?

解説を読んだ上でもう少し考えてみると、まず上記3は、サイクルとは限らず、強連結成分だった。
上記4は、c-1へつながるとは限らず、辺の両端のcが異なるなら小さい方へ流しておけばよい。
結局、cが異なるなら小さいほうへ向け、同じならその中で強連結成分を作ればいいらしい。
でも強連結成分の作り方がまだいまいちピンと来ていない。


EとFは問題を見ていない。



終結果:ABCの3完、107分36秒、468位、パフォーマンス1849
レート変動:1832→1834(+2)


今回はDifficultyが緑水青黄橙赤で、緩やかな良い傾斜。

Aがやや難しすぎだとは思ったけど、それにしてもハマりすぎだし、サンプルが強めだったからできたに過ぎない感じ。
経過20分くらいで全くわからない中、正解者数は既に600人とかいて、ノルマより完全に遅れててやる気をなくしかけてもいた。

解法が一番すぐにわかったのがCで、青diff解けたのは良かったが、実装をもっとスムーズにできなかったものか・・・。
i番の人」と、「配列上のi番目」をこんがらがらせすぎ。
まあでも最終的には通せてなんとか救われた。

D問題の強連結成分を作る部分は、近日中にちゃんとやっておくことにする。