山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 023

問題

AtCoder Beginner Contest 023 - AtCoder Beginner Contest 023 | AtCoder

C問題が分からなかったので解説をみました。過去問のC問題は難しいと思います。

過去問の難易度を推定してくれたサイトがあるので紹介します。

過去のARC/ABCの問題難易度推測

推定された難易度は結構正確だと思います。僕の問題に対する感触とマッチしていました。

A - 加算王

典型的な問題です。与えられた数字の各桁の数字の和を出力します。

文字列として扱うと簡単に解答できます。

B - 手芸王

B問題にしては頭を使う?問題だと思います。

与えられた文字列の長さは奇数でなければならないので、真ん中の文字から左右へ調べていきます。3の周期で文字列の操作が行われるので、それに合わせて文字列をチェックしていきます。

コード
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        String S = scan.next();
        scan.close();
        if(N % 2 == 0) {
            System.out.println(-1);
            System.exit(0);
        }
        if(S.charAt(N / 2) != 'b') {
            System.out.println(-1);
            System.exit(0);
        }
        for(int i = 1; i <= N / 2; i++) {
            char c1 = S.charAt(N / 2 - i);
            char c2 = S.charAt(N / 2 + i);
            if(i % 3 == 1) {
                if(c1 != 'a' || c2 != 'c') {
                    System.out.println(-1);
                    System.exit(0);
                }
            }else if(i % 3 == 2) {
                if(c1 != 'c' || c2 != 'a') {
                    System.out.println(-1);
                    System.exit(0);
                }
            }else {
                if(c1 != 'b' || c2 != 'b') {
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }
        System.out.println(N / 2);

    }
}

C - 収集王

恐らく典型問題だと思います。

列と行の飴の個数を数え上げることは思いついたんですが、その後どのようにして解答を作るかができませんでした。

コード
import java.util.Arrays;
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int R = scan.nextInt();
        int C = scan.nextInt();
        int K = scan.nextInt();
        int N = scan.nextInt();

        int [][]p = new int[N][2];
        int []row = new int[R + 1];
        int []col = new int[C + 1];
        Arrays.fill(row, 0);
        Arrays.fill(col, 0);
        for(int i = 0; i < N; i++) {
            int r = scan.nextInt();
            int c = scan.nextInt();
            p[i][0] = r;
            p[i][1] = c;
            row[r] ++;
            col[c]++;
        }
        scan.close();
        int []row1 = new int[100000 + 1];
        int []col1 = new int[100000 + 1];

        Arrays.fill(row1, 0);
        Arrays.fill(col1, 0);
        for(int i = 1; i <= R; i++) {
            row1[row[i]]++;
        }
        for(int i = 1; i <= C; i++) {
            col1[col[i]]++;
        }
        long cnt = 0;
        for(int i = 0; i <= K; i++) {
            cnt += row1[i] * col1[K - i];
        }
        for(int i = 0; i < N; i++) {
            if(row[p[i][0]] + col[p[i][1]] == K) {
                cnt --;
            }else if(row[p[i][0]] + col[p[i][1]] == K + 1) {
                cnt ++;
            }
        }
        System.out.println(cnt);

    }
}