パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

ABC

コンテスト前のレート：1855
レート通りのパフォーマンスが得られる順位：447位（1600点、98分23秒）

A - Brick

問題

思考過程
  1. N \div Wの切り捨て。
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 w = sc.nextInt();
        sc.close();

        System.out.println(n / w);
    }
}

ここまで0分27秒＋0ペナ。97位。


B - Blocks on Grid

問題

思考過程
  1. Aの最小値に合わせることを考える。
  2. 全要素を調べて、最小値を求める。
  3. 全要素を調べて、「要素の値-最小値」の合計を求める。
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[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        // 思考過程2
        int min = 1000; // 適当にAの制約より大きい値
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                min = Math.min(a[i][j], min);
            }
        }

        // 思考過程3
        int ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                ans += a[i][j] - min;
            }
        }
        System.out.println(ans);
    }
}

ここまで2分12秒＋0ペナ。183位。


C - Unlucky 7

問題

思考過程
  1. Nは十分小さいので、1からNまで全部試して条件を満たすか調べる。
  2. "7"が含まれるかどうかの判定は、文字列化してindexOfメソッドを使うのが楽そう。
  3. 10進数を8進数に変換できるメソッドは、標準でありそうな気もするので、少し探してみる。
  4. 「Integer.」と打ってみたら（自分の環境ではこれでIntegerクラスに存在するメソッドが全て出る）、toOctalStringメソッドが見つかった。
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 ans = 0;
        for (int i = 1; i <= n; i++) {
            String s = String.valueOf(i);
            String t = Integer.toOctalString(i); // 思考過程4
            if (s.indexOf("7") == -1 && t.indexOf("7") == -1) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ここまで4分46秒＋0ペナ。224位。


D - Sum of difference

問題

思考過程
  1. 要するに、N個の中から2個を選択する全ての組み合わせについて、差の絶対値の総和を求めよと言われている。
  2. 全ての組み合わせを見るので、要素の順番は関係ない。
  3. つまりソートしてOKで、ソートすれば必ずA_i \leq A_jとなり、絶対値は考えなくてよくなる。
  4. \sum_{i=1}^{N}(A_N-A_i)でいいのでは？とか思ったりしたが違う。
    　
  5. しばらく混乱するが、各A_{i+1}-A_iが何回足されるかを冷静に考える。
  6. その区間より左の要素数\times右の要素数であった。
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);
        long ans = 0;
        for (int i = 1; i < n; i++) {
            // 区間 × 左側の要素数 × 右側の要素数
            ans += (long) (a[i] - a[i - 1]) * i * (n - i);
        }
        System.out.println(ans);
    }
}

ここまで11分41秒＋0ペナ。537位。


E - Throne

問題
制約が10^5程度なら鳩ノ巣原理で愚直にやればいいだろうという感じだが、それよりだいぶ大きいので、数学的な解き方をするしかなさそう。
公式解説の1行目はすぐにわかったが、それをどう解けばいいのかがわからず。

順位表でEとFを比べてEの方が倍は解かれていたのでしばらく頑張ろうとしたが、30分ほどで飛ばしてFへ。


F - Rook on Grid

問題
考えやすそうな見た目をしていたので、そのままFをやることに決める。

思考過程
  1. 右→下か、下→右という移動方法しかない。
  2. これは、基本的には、1行目もしくは1列目から、最初の障害物に当たるまでの間にあるマスの数を求めればよいことになる。
  3. ただし、右→下と下→右の両方で行けるマスがあるため、重複を除いて数える必要がある。
  4. サンプルが弱すぎるので、適当な例を自分で作る。
    ※図内のオレンジは障害物、上側と左側に並んでいる値は最初に障害物に当たるまでのマス数。
    f:id:ks2m:20201220002801p:plain
  5. まず、右→下の方は、図の薄緑箇所が該当し、これは上側の値を全部足すだけ。
  6. 下→右の方で、紫箇所のみを数える方法を考える。
  7. 図の左側に記載の値から、最初の障害物に当たるまでの間の薄緑マスの数を引きたい。
  8. 薄緑マスの数は、i行目の最初の障害物の位置をy列目とすると、最初の列からy-1列目までの中で、最初の障害物の位置がi行目よりも下である列の数となる。
  9. 「最初の障害物の位置がi行目よりも下」の部分は、BITを用いてO(logH)で取得できる。
  10. 「最初の列からy-1列目までの中で」の部分は、BITにデータを入れたかどうかで実現する。つまり、障害物が左の方にある行から順に処理していく。
    　
  11. 1行目や1列目に障害物がある場合はそこで止めないといけないのを忘れ、半分くらいWA。
    図の薄紫のみをカウントしたくて、濃い紫はカウントしてはいけなかった。
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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int m = Integer.parseInt(sa[2]);
        int[] x = new int[m];
        int[] y = new int[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            x[i] = Integer.parseInt(sa[0]) - 1;
            y[i] = Integer.parseInt(sa[1]) - 1;
        }
        br.close();

        int[] a = new int[w];
        Arrays.fill(a, h);
        Obj[] arr = new Obj[h];
        for (int i = 0; i < h; i++) {
            Obj o = new Obj();
            o.i = i;
            o.y = w;
            arr[i] = o;
        }
        // 思考過程2
        for (int i = 0; i < m; i++) {
            a[y[i]] = Math.min(a[y[i]], x[i]);
            Obj o = arr[x[i]];
            o.y = Math.min(o.y, y[i]);
        }

        // 思考過程11 1行目に障害物があったら以降全て到達不可
        boolean flg = false;
        for (int i = 0; i < w; i++) {
            if (a[i] == 0) {
                flg = true;
            }
            if (flg) {
                a[i] = 0;
            }
        }
        // 思考過程11 1列目に障害物があったら以降全て到達不可
        flg = false;
        for (int i = 0; i < h; i++) {
            if (arr[i].y == 0) {
                flg = true;
            }
            if (flg) {
                arr[i].y = 0;
            }
        }

        // 思考過程5
        long ans = 0;
        for (int i = 0; i < w; i++) {
            ans += a[i];
        }

        Arrays.sort(arr, (o1, o2) -> o1.y - o2.y);
        FenwickTree ft = new FenwickTree(h + 1);
        int j = 0;
        for (int i = 0; i < h; i++) {
            Obj o = arr[i];
            // 思考過程10
            while (j < o.y) {
                ft.add(a[j], 1);
                j++;
            }
            // 思考過程7
            long v1 = o.y;
            long v2 = ft.sum(o.i, h + 1); // 障害物までのマス数がi以上の列数
            ans += v1 - v2;
        }
        System.out.println(ans);
    }

    static class Obj {
        int i, y;
    }
}

// 以下ACLのFenwick Tree

提出
ABCDFと解いた時点で75分32秒＋1ペナ。297位。



最終結果：ABCDFの5完、80分32秒、425位、パフォーマンス1884
レート変動：1855→1858（+3）


とりあえず1800台後半で踏みとどまれてよかった。

D問題に7分かかっているが、5分で解けなければ遅いというのがなかなか厳しい。
ソートするまではすぐだったのに、_NC_2全組み合わせ系がいつまで経っても苦手。

F問題は、BITを用いて走査する問題を今までにいくつもやったことがあり、図を描いてみたら発想は割とすぐに出てきたが、実装できる形に整理するのに手間取った。
まあちょうど五分五分くらいのDifficultyだったようなので、解けただけでも十分か。

E問題はもう少しググるなりできなかったものか。
Fが解けて安心してもういいやって思ってしまったのもあるが。

今回は同じ1600点の人が少なかったため、スピードはあまり影響しなかったが、F問題を見始めたのが遅いというムーブ自体はよくなかった。
ABCでは、詰まったらすぐ次の問題を見るくらいはしておくことにしよう。