AtCoder Beginner Contest 181

コンテスト前のレート:1676
レート通りのパフォーマンスが得られる順位:467位(1500点、53分42秒)

A - Heavy Rotation

問題

思考過程
  1. 白と黒は交互なので、N\%2で分岐。
  2. 例1より、2(余り0)の場合に"White"。
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();

        if (n % 2 == 0) {
            System.out.println("White");
        } else {
            System.out.println("Black");
        }
    }
}

ここまで0分44秒+0ペナ。242位。


B - Trapezoid Sum

問題
A問題と比べていきなりだいぶめんどくさそうなのが出てきた。

思考過程
  1. 制約が大きいので、O(NB)ではなくO(N)でやる必要がある。
  2. ABの和は、台形の面積を求める要領で、(A+B) \times (B-A+1) \div 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[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        sc.close();

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

ここまで2分42秒+0ペナ。329位。


C - Collinearity

問題

思考過程
  1. O(N^3)3点の組み合わせを全探索。
  2. 3I,J,Kが同一直線上にあるかどうかは、IJの傾きとIKの傾きが等しいかどうかで判定する。
  3. x, yをそれぞれx座標、y座標の差として、\frac{y_1}{x_1}=\frac{y_2}{x_2}であるかどうかを求めたい。
  4. 移項して、x_1y_2=x_2y_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[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int x1 = x[j] - x[i];
                    int x2 = x[k] - x[i];
                    int y1 = y[j] - y[i];
                    int y2 = y[k] - y[i];
                    if (x1 * y2 == x2 * y1) {
                        System.out.println("Yes");
                        return;
                    }
                }
            }
        }
        System.out.println("No");
    }
}

ここまで6分39秒+0ペナ。146位。
早解きできるときはできるんだけどな・・・。


D - Hachi

問題
ここからボロッボロ。
正解者数の伸びはそれほど早くはないと思って焦らずやっていたつもりだったが、それで時間かかるにしても限度がある。

思考過程
  1. とりあえずSに現れる各数字の数をカウントしておく。
  2. S1桁の場合、81個の場合のみ。
  3. S2桁の場合、1696まで大した数でもないので、場合分けで頑張る。
  4. S3桁以上の場合、下3桁の構成だけ考えればよい。下から3桁目の偶奇で場合分けする?
  5. いや、0999を構成可能か調べ、構成可能な数が8で割り切れれば"Yes"のようにできる。
     
  6. などとやっている内に、結局3桁以上の場合のロジックで1桁や2桁の場合もまとめてできそうなので、余計な場合分けを消しにかかる。
  7. しかし結局、桁数によって探索範囲を絞ることになる。(絞らずにWA喰らうなどした)
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();
        sc.close();

        solve(s);

        // 上手くいかずにデバッグした跡
//      for (int i = 0; i < 1000; i++) {
//          String si = String.valueOf(i);
//          System.out.print(i + "\t");
//          solve(si.toCharArray());
//      }
    }

    static void solve(char[] s) {
        int[] cnt = new int[10];
        for (int i = 0; i < s.length; i++) {
            cnt[s[i] - '0']++;
        }

        int start = 1;
        int end = 10;
        if (s.length == 2) {
            start = 11;
            end = 100;
        }
        if (s.length >= 3) {
            start = 101;
            end = 1000;
        }
        for (int i = start; i < end; i++) {
            // iに現れる数字の数を調べる
            int[] a = new int[10];
            String si = String.valueOf(i);
            for (int j = 0; j < si.length(); j++) {
                a[si.charAt(j) - '0']++;
            }
            // Sに含まれる数字より多く必要な数字があればfalse
            boolean flg = true;
            for (int j = 0; j < 10; j++) {
                if (a[j] > cnt[j]) {
                    flg = false;
                    break;
                }
            }
            if (flg) {
                if (i % 8 == 0) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }
}

ここまで35分45秒+2ペナ。990位。


E - Transformable Teacher

問題
大まかな方針はほぼ一瞬でわかったのに、実装が下手くそ。

思考過程
  1. Hをソートし、その中にWから1個を選んで適切な位置に挿入し、Hの前から順に2つずつペアにしていく。ということをやる場合に、Wからどの1個を選べばよいかという問題。
  2. Wもソートして、0番目を挿入したときの結果を求める。
  3. Wの0番目を抜き出して1番目を挿入したときの差分を求める。ということをやっていけば、差分を求めるのにHを参照する部分がM回の合計でO(N)で済む。
  4. しかし、差分を求める計算が偶奇でこんがらがってしまい、実装できそうになかったので、累積和を使うことを考える。
     
  5. 大まかにいえば、W_iの挿入位置をidxとすると、idxより前までは(0,1), (2,3), \cdotsのようにペアになるので、(偶, 奇)ペアの合計を、idxより後からは(奇, 偶)ペアの合計を足し、さらにabs(W_i - H_{idx})を足す。
  6. これだけではWAだったので、デバッグしながら、idx\pm 1したりして添え字ガチャをする。
  7. 結局、idxの偶奇と両端の処理が肝であったらしい。

ソースはとりあえず本番時そのままのものを貼っておくが、後半のif文等は多分ぐちゃぐちゃ。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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 m = Integer.parseInt(sa[1]);

        sa = br.readLine().split(" ");
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] w = new int[m];
        for (int i = 0; i < m; i++) {
            w[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        Arrays.sort(h);
        Arrays.sort(w);

        long[] v1 = new long[n + 1];
        long[] v2 = new long[n + 1];
        for (int i = 1; i < n; i++) {
            if (i % 2 == 1) {
                v1[i] = h[i] - h[i - 1];
            } else {
                v2[i] = h[i] - h[i - 1];
            }
        }
        for (int i = 2; i <= n; i++) {
            v1[i] += v1[i - 1];
            v2[i] += v2[i - 1];
        }

        long ans = Long.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            int idx = Arrays.binarySearch(h, w[i]);
            if (idx < 0) {
                idx = ~idx;
                if (idx > 0) {
                    idx--;
                }
            }
            long val1 = v1[idx];
            long val2 = v2[n] - v2[idx];
            long val3 = Math.abs(w[i] - h[n - 1]);
            if (idx < n - 1) {
                if (idx % 2 == 0) {
                    val3 = Math.abs(h[idx] - w[i]);
                } else {
                    val2 = v2[n] - v2[idx + 1];
                    val3 = Math.abs(h[idx + 1] - w[i]);
                }
            }
            long val = val1 + val2 + val3;
            ans = Math.min(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで86分43秒+3ペナ。1037位。


F - Silver Woods

問題
さすがに時間が足りない。

思考過程
  1. 2(A,B)の組み合わせを全探索。
  2. 各組み合わせについて、Y座標の値がA \leq Bとして、下の壁とAの距離、上の壁とBの距離、ABの距離の内の最大値を求める。
  3. 上記2の最小値が答え? →例2までしか合わない。
  4. 例3を紙の上にそれらしくプロットしてみると、他の点が邪魔をして、必ずしも上記2の3つの距離の内の最大のところを通れるとは限らないようだった。

ここからあと何分あれば、二分探索+UnionFindにたどり着けたのか・・・。



終結果:ABCDEの5完、101分43秒、1131位、パフォーマンス1277
レート変動:1676→1642(-34)


Highest-98からこの土日でさらに-80。
次回はパフォ1130未満程度で水色落ち。

今日のような状況で、E問題をスキップしてF問題に挑戦して失敗みたいなことになれば、普通にあり得そう。

10/3に黄パフォを出してほぼHighestまで回復後、この1ヶ月の結果が1勝6敗。内2回は緑パフォ。
最近の緑~水diffが難しすぎる・・・。

7月後半以降まともな精進をしていないので、周りができるようになった結果ならまだいいのだが、ここまでの急落はさすがに自分が落ちているのも合わさっていないとあり得ない気がするので、水diff前後の問題を詰まらず解けるように、あさかつ/くじかつとかに参加していくのがいいのかもしれない。