AtCoder Beginner Contest 173

ABC

コンテスト前のレート：1790
レート通りのパフォーマンスが得られる順位：561位

A - Payment

問題
if文を使わずに書けないかと一瞬思ったけど思いつかなかった。

思考過程
  1. お釣りに関わるのは1000で割った余りの部分。
  2. 基本的に「1000-余り」が答えだが、余りが0の場合1000になるのでそれだけ場合分けする。
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();

        int m = n % 1000;
        if (m == 0) {
            System.out.println(0);
        } else {
            System.out.println(1000 - m);
        }
    }
}

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


B - Judge Status Summary

問題
解説PDFに珍しくJavaのソースがあると思ったら間違い発見。（8行目が、×：nextLine　○：next）
提出して確認していないのだろうか・・。

思考過程
  1. 文字列をキーとして個数を数えるので、マップを使う。
  2. 0個でも出力するので、初めに各文字列のエントリを作ってしまえば、containsKeyで場合分けとかが不要になる。
  3. 出力形式を間違えないように、"AC x "とかは出力例からコピーする。
import java.util.HashMap;
import java.util.Map;
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();
        Map<String, Integer> map = new HashMap<>();
        map.put("AC", 0);
        map.put("WA", 0);
        map.put("TLE", 0);
        map.put("RE", 0);
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            map.put(s, map.get(s) + 1);
        }
        sc.close();

        System.out.println("AC x " + map.get("AC"));
        System.out.println("WA x " + map.get("WA"));
        System.out.println("TLE x " + map.get("TLE"));
        System.out.println("RE x " + map.get("RE"));
    }
}

ここまで3分54秒＋0ペナ。636位。
3分近くかかったらやや遅いらしい。最後の4行を書くのに手間取ったかな・・。


C - H and V

問題
2^N通り全パターンを調べるbit全探索って競プロ始めるまで書いたことなかったけど、今ではこれでいけると思ったら迷わず書けるようになった。

思考過程
  1. 各行や列を赤く塗るかどうかのパターンは、2^H \times 2^W通り。制約は十分小さいのでこれで間に合う。
  2. ビットが1の時は赤く塗っているとし、ビットが1でない行や列の '#' を数えてKと一致するか調べる。
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 w = sc.nextInt();
        int k = sc.nextInt();
        char[][] c = new char[h][w];
        for (int i = 0; i < h; i++) {
            c[i] = sc.next().toCharArray();
        }
        sc.close();

        int h2 = 1 << h;
        int w2 = 1 << w;
        int ans = 0;
        // 赤く塗るパターンの全探索
        for (int x = 0; x < h2; x++) {
            for (int y = 0; y < w2; y++) {
                // 各パターンでの黒マスのカウント
                int cnt = 0;
                for (int i = 0; i < h; i++) {
                    if ((x >> i & 1) == 1) {
                        continue; // 赤い行はスキップ
                    }
                    for (int j = 0; j < w; j++) {
                        if ((y >> j & 1) == 1) {
                            continue; // 赤い列はスキップ
                        }
                        if (c[i][j] == '#') {
                            cnt++;
                        }
                    }
                }
                if (cnt == k) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで9分03秒＋0ペナ。288位。


D - Chat in a Circle

問題
実験ベースになって9割くらいの自信で出しがちだけど、ちゃんと合ってて助かった。

思考過程
  1. 適当に1, 2, 3, 4, 5とかの入力値で、小さい順に追加するのと大きい順に追加するのと、どちらが良さそうか試してみると、大きい順の方が明らかに良い。そもそもまず追加しないと、その要素の値が心地よさに寄与しない。
  2. もう少し数を増やして、10～1について、例１のような図を書き、貪欲に最も良い場所に追加してみる。すると、最大の数が1回、2番目からは2回ずつ使えそう。
  3. 例えば、10, 8, 9のように並んでいるところに、新たに6, 5 (\lt 8)を追加すると、10, 6, 8, 5, 9のようになり、6 \lt 8 > 5という並びができることになるため、その後8は使えなくなる。
    降順に追加していくという前提の下では、ある数を2回（最初だけ1回）使うと両隣がより小さい数になるということにより、上記2.が示せた。多分。
  4. 実装は、まず降順ソートして先頭を足し、2番目からN/2番目くらいまでの2倍を足して、Nが奇数ならさらに次の要素も足すという感じにしようと思うが、境界がかなり自信ない。奇数の場合と偶数の場合とそれぞれきちんとテストする。
import java.util.Arrays;
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();
        }
        sc.close();

        Arrays.sort(a);
        reverse(a);

        long ans = a[0];
        int n2 = n / 2;
        for (int i = 1; i < n2; i++) {
            ans += a[i] * 2;
        }
        if (n % 2 == 1) {
            ans += a[n2];
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static void reverse(int[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            int tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

ここまで20分16秒＋0ペナ。271位。


E - Multiplication 4

問題
ぱっと見で、Pairs（ABC155-D）とかで見たような、正、0、負の場合分けが大変そうな雰囲気を感じる。
順位表を見たらEが5人、Fが25人とかだったので、とりあえずF問題も見るが、すぐに解けそうになく、ちょっと場合分け頑張ればできそうなE問題に戻ってくる。
しかしそのまま解けずに終了。

思考過程
  1. まず、答えが正か0か負かを求めることを考える。正にできるなら正、正にできず0にできるなら0、それ以外は負とする。
  2. 0が1個以上含まれている場合、0にすることができる。
  3. 正にできるかを考える。正の要素数をP、負の要素数をMとして、
    • P+M=Kの場合、全てを選択する必要があるため、Mが偶数の場合のみ可能。（本番中はKとMの偶奇が一致の場合可能とかしていたりして破滅。）
    • P+M>Kの場合、P=0かつKが奇数の場合のみ不可。P>0ならば負数の個数を最低1個は調整できるため偶数にすることができ、P=0でもKが偶数なら正になるのでOK。
    • P+M \lt Kの場合、0が入るため不可。
      　
  4. 答えが正、0、負の3パターンの内、簡単なところからやっていく。
    • 答えが0の場合、固定値0を出力する。
    • 答えが負の場合、絶対値が小さい順にK個取る。
    • 答えが正の場合、正数降順のPriorityQueueと負数昇順のPriorityQueueそれぞれの先頭2要素を取り出して積を比較し、正の方が大きければ先頭1つを採用、負の方が大きければ先頭2つを採用し、採用しなかったものはキューに戻す。ということをK個になるまで繰り返す。
      いずれかのキューが残り1個以下の場合、K個まで残り1個の場合などに気を付ける。積のmodを取ってから比較しないようにも気を付ける。
      （本番中は、最後の1個を採用して良いかというところばかり見直していたが、2個先までの積ではなく1個だけで比較していたため、他をいくら直しても根本的に駄目なことに変わりはなかった。）

一応2個の積で比較するという情報だけ得て、場合分けで破滅しながらなんとかACしたソース（こちら）もあるが、番兵を使ったりなどしたらだいぶマシになったので、以下のソースはその実装方法で。

import java.util.Arrays;
import java.util.PriorityQueue;
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();

        // minus、zero、plusの個数
        int m = 0;
        int z = 0;
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                z++;
            } else if (a[i] > 0) {
                p++;
            } else {
                m++;
            }
        }

        // 0にできるか
        boolean bz = false;
        if (z > 0) {
            bz = true;
        }
        // 正にできるか
        boolean bp = false;
        if (p + m == k) {
            if (m % 2 == 0) {
                bp = true;
            }
        } else if (p + m > k) {
            if (p > 0 || k % 2 == 0) {
                bp = true;
            }
        }

        int mod = 1000000007;
        if (bp) {
            PriorityQueue<Integer> qp = new PriorityQueue<>((o1, o2) -> o2 - o1); // 正数降順
            PriorityQueue<Integer> qm = new PriorityQueue<>(); // 負数昇順
            for (int i = 0; i < n; i++) {
                if (a[i] > 0) {
                    qp.add(a[i]);
                } else {
                    qm.add(a[i]);
                }
            }
            // 番兵
            qp.add(0);
            qp.add(0);
            qm.add(0);
            qm.add(0);

            long ans = 1;
            for (int i = 0; i < k; i++) {
                Integer np = qp.poll();
                Integer np2 = qp.poll();
                Integer nm = qm.poll();
                Integer nm2 = qm.poll();
                long vp = (long) np * np2;
                long vm = (long) nm * nm2;
                // 正と負がどちらも残り1個の場合、vpもvmも0となり、
                // そのような場合に正を採用するため">"ではなく">="とする。
                // Kまで残り1個の場合も正を採用
                if (vp >= vm || i == k - 1) {
                    ans *= np; // 1つ採用
                    qp.add(np2);
                    qm.add(nm);
                    qm.add(nm2);
                } else {
                    ans *= vm % mod; // 2つ採用
                    qp.add(np);
                    qp.add(np2);
                    i++;
                }
                ans %= mod;
            }
            System.out.println(ans);

        } else if (bz) {
            System.out.println(0);

        } else {
            // 絶対値に変換して昇順にソート
            for (int i = 0; i < n; i++) {
                if (a[i] < 0) {
                    a[i] = -a[i];
                }
            }
            Arrays.sort(a);

            long ans = 1;
            for (int i = 0; i < k; i++) {
                ans *= a[i];
                ans %= mod;
            }
            // -ansにしてmodを取る
            ans = mod - ans;
            ans %= mod;
            System.out.println(ans);
        }
    }
}

　

F - Intervals on Tree

問題
10分ほどで下記の4.まで考えたのにE問題に戻ってしまった。
終了直後にTwitterで「辺の寄与数」的な文言が目に入った瞬間にすぐピンときたのでもったいない。

思考過程
  1. 1つも連結されないとした全体の数は、連結成分の数=頂点の数であり、\sum_{i=1}^N \sum_{j=1}^i j = \sum_{i=1}^N \frac{i (i+1)}{2}となる。
  2. 辺を1本引くごとに連結成分の数が1つ減るので、全てのL, Rの組み合わせについて、作られるグラフの辺の数を求め、その合計を先ほどの全体の数から引けばよさそう。
  3. 例えば例１では、｛1-3-2｝と｛3-2｝は作られる（合計3本）が、｛1-3｝は作られない。1+3+6-3=7となる。
  4. 作られる連結成分は、全ての隣接頂点が連結成分内の最小値未満か最大値超である場合っぽい？が、N回DFSするとかやっているとO(N^2)以上かかるのは確実で、高速に求める方法がわからない。
  5. 見方を変えて、辺ごとに使われる回数を数えようとすると、u \lt vとして、「u以下の頂点数\times v以上の頂点数」となる。
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[] u = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n - 1; i++) {
            u[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        sc.close();

        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += (long) i * (i + 1) / 2;
        }

        for (int i = 0; i < n - 1; i++) {
            ans -= (long) Math.min(u[i], v[i]) * (n - Math.max(u[i], v[i]) + 1);
        }
        System.out.println(ans);
    }
}

　


最終結果：ABCDの4完、20分16秒、1166位、パフォーマンス1477
レート変動：1790→1762

F問題にも最低20分は取るべきだったと思う。
今回は、バグさえ直せば通ると思ってしまって、根本的な見落としに気付かなかったところが大きいが。

E問題をぎりぎりで解いて1500点になったところでパフォ1540程度と大して変わらず、ABCDFの1600点なら1860程度と400近くも変わるので、F問題に賭ける手もある。
4完時点での残り時間の半分を使ってE問題を解けず、かつF問題の正解者数が3桁いるくらいならば、もっと狙っていきたい。