HHKB プログラミングコンテスト 2020

コンテスト前のレート:1815
レート通りのパフォーマンスが得られる順位:473位(1100点、28分42秒)

A - Keyboard

問題

思考過程
  1. Sが"Y"の場合、T.toUpperCase。以外はTそのまま。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        sc.close();

        if (s.equals("Y")) {
            System.out.println(t.toUpperCase());
        } else {
            System.out.println(t);
        }
    }
}

ここまで0分53秒+0ペナ。71位。


B - Futon

問題

思考過程
  1. 横向きと縦向きを独立に数える。
  2. 横向きについて数えるときは、(i, j-1)(i, j)が共に '.' であるかどうかを調べる。
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();
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int ans = 0;
        // 横向き
        for (int i = 0; i < h; i++) {
            for (int j = 1; j < w; j++) {
                if (s[i][j - 1] == '.' && s[i][j] == '.') {
                    ans++;
                }
            }
        }
        // 縦向き
        for (int i = 1; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i - 1][j] == '.' && s[i][j] == '.') {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで3分11秒+0ペナ。135位。


C - Neq Min

問題
こういう存在確認しそうな問題を見るとすぐSetを使いたくなる。けど配列で十分だった。

思考過程
  1. p_iとして出現した回数(出現したかどうか)を保持しておく配列cを用意する。
  2. 毎回x=0から順にc[x]=0かどうかを調べていたら、O(N^2)で駄目。
  3. 答えは広義単調増加になるので、毎回0からではなく、前回の答えから調べ始めればよい。これでならしO(N)となった。

後から思いついたが、最初に0200000をTreeSetに入れておき、p_iの削除とfirst()の出力を繰り返すのでもできそう。

import java.io.PrintWriter;
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[200001];
        PrintWriter pw = new PrintWriter(System.out);
        int min = 0;
        for (int i = 0; i < n; i++) {
            int p = sc.nextInt();
            c[p]++;
            while (c[min] > 0) {
                min++;
            }
            pw.println(min);
        }
        pw.flush();
        sc.close();
    }
}

ここまで5分57秒+0ペナ。185位。


D - Squares

問題
10分以上頑張っても全然解けない。といったところで順位表を見たら、まだ正解者数たった30人とかしかいなかったので、じっくり考えても良さそうだとなる。(でもこの時点でEの方が正解者数多かったので、素直にEを先にやれば良かった・・。)
30分経ってもできないので、いい加減Eを先にやることに。
Eを20分くらいで通して戻ってきた後、5分だけFを見たが、それ以外をずっとDに費やしても結局解けず。

思考過程
  1. 例1に誘導されて、全体から重なる場合を引くことを考える。どう考えても単純な計算ではできそうにない。
  2. 実は重ならない場合だけを考えていけるのではないかと考え直してみる。青が上の方にあって赤が下の方にある場合を数えて4倍する方向で考えてみるが、赤が左下や右下にある場合の重複を上手く取り除けず終了。真下~右下だけを数えるようにできれば、重複せず4倍でいけたのだろうか・・・。

E - Lamps

問題

思考過程
  1. 各マスが答えにどれだけ寄与するかを計算していく。
  2. とりあえず例2の '.' の各マスについて、そのマスが照らされる照明の置き場所数C_{ij}をカウントしてみる。
  3. C_{ij}個のマスの内いずれか1箇所以上に照明を置かれるのが2^{C_{ij}}-1通り。
  4. 残りのK-C_{ij}個のマスは任意なので、2^{K-C_{ij}}通り。
  5. これらを掛け合わせれば、1マス分の答えを求められる。(手計算で例2が合うことを確認。12+14+14+12=52
     
  6. C_{ij}の求め方は、ABC129-D:Lampをだいたい覚えていた。(緑diffで本番中に解けなかった問題はどれも結構印象に残っているので)
  7. 今回は、端や直前の '#' からマス(i, j)まで連続した '.' の数を4方向について足し、重複分の3を引くことで求めた。
     
  8. 2^{K-C_{ij}}の方を見て、「'.' マスの場合C_{ij}1以上なので、2^{K-1}までしかないだろう」と配列pのサイズをKにしていたら、3ケースREになった。(2^{C_{ij}}-1の方を見たら、C_{ij}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();
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int[][] c1 = new int[h][w]; // →
        int[][] c3 = new int[h][w]; // ↓
        int k = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '.') {
                    k++;
                    if (j == 0) {
                        c1[i][j] = 1;
                    } else {
                        c1[i][j] = c1[i][j - 1] + 1;
                    }
                    if (i == 0) {
                        c3[i][j] = 1;
                    } else {
                        c3[i][j] = c3[i - 1][j] + 1;
                    }
                }
            }
        }

        int[][] c2 = new int[h][w]; // ←
        int[][] c4 = new int[h][w]; // ↑
        for (int i = h - 1; i >= 0; i--) {
            for (int j = w - 1; j >= 0; j--) {
                if (s[i][j] == '.') {
                    if (j == w - 1) {
                        c2[i][j] = 1;
                    } else {
                        c2[i][j] = c2[i][j + 1] + 1;
                    }
                    if (i == h - 1) {
                        c4[i][j] = 1;
                    } else {
                        c4[i][j] = c4[i + 1][j] + 1;
                    }
                }
            }
        }

        int mod = 1000000007;
        long[] p = new long[k + 1]; // p[i] = 2 ^ i
        p[0] = 1;
        for (int i = 1; i <= k; i++) {
            p[i] = p[i - 1] * 2 % mod;
        }

        long ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int c = c1[i][j] + c2[i][j] + c3[i][j] + c4[i][j] - 3;
                if (c > 0) {
                    ans += (p[c] - 1) * p[k - c] % mod;
                    ans %= mod;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで55分28秒+1ペナ。532位。



終結果:ABCEの4完、60分28秒、724位、パフォーマンス1611
レート変動:1815→1796(-19)


今回の敗因は、Dもどうせ解くから慌ててEを先にやらなくてもいいやという慢心だったと思う。
あとEで、前計算の配列サイズをどうして無駄に1減らそうとしてしまったのか。

A問題が相対的に一番早くてだんたん順位が下がっていく推移も珍しい。