AtCoder Regular Contest 130 - ks2mのブログ

A - Remove One Character
- 思考過程
B - Colorful Lines
- 思考過程
C - Digit Sum Minimization
- 思考過程

コンテスト前のレート：1984
レート通りのパフォーマンスが得られる順位：302位（1200点、85分53秒）

A - Remove One Character

思考過程

同じ文字が $K$ 個連続する区間ごとに、 $_KC_2$ を足していきたい。
これは、同じ文字が $K$ 個目であるごとに $K-1$ を足していっても同じなので（ $K$ 個目の文字を $j$ とした時の相方となる $i$ が $K-1$ 通りのため）、そのように実装する。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] s = br.readLine().toCharArray();
        br.close();

        long ans = 0;
        long cnt = 0;
        for (int i = 1; i < n; i++) {
            if (s[i - 1] == s[i]) {
                cnt++;
                ans += cnt;
            } else {
                cnt = 0;
            }
        }
        System.out.println(ans);
    }
}

ここまで1分58秒＋0ペナ。39位。

B - Colorful Lines

問題

思考過程

普通に前からやって上書き部分を正しく処理できるか、もしくは後ろからやって一度塗られた部分は避けることを上手く処理できるか。
以下のようにすれば後ろからできる。
ある行を塗ったら、その行は二度と塗れないとし（塗った行番号をSetで管理する）、次回列方向に塗る際に塗れるマスの数を $1$ 減らす（ $H$ を $1$ 減らす）。　列を塗る場合も同様。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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 q = Integer.parseInt(sa[3]);
        int[] t = new int[q];
        int[] n = new int[q];
        int[] c = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            n[i] = Integer.parseInt(sa[1]);
            c[i] = Integer.parseInt(sa[2]) - 1;
        }
        br.close();

        long[] ans = new long[m];
        Set<Integer> x = new HashSet<>();
        Set<Integer> y = new HashSet<>();
        for (int i = q - 1; i >= 0; i--) {
            if (t[i] == 1) {
                if (x.add(n[i])) {
                    ans[c[i]] += w;
                    h--;
                }
            } else {
                if (y.add(n[i])) {
                    ans[c[i]] += h;
                    w--;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (long i : ans) {
            sb.append(i).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで8分13秒＋0ペナ。80位。

C - Digit Sum Minimization

問題
下記の方法で穴がないのかはあまり自信ない。
たまたま例２で引っかかったおかげでなんとかなった。

思考過程

繰り上がりがなければ、どのように並べ替えようとも合計は変わらず、逆に言えば繰り上がる度に減っていくので、繰り上がり回数を最大化する問題。
　
$a_i+b_i+k \geq 10$ （ $k$ は繰り上がりがあれば $1$ 、なければ $0$ ）となる組合せをなるべく多くするには、下の桁から順に、合計 $10$ ～ $19$ の優先順で作ればよい？
合計 $10$ ～ $19$ のいずれも作れなくなったら、合計 $2$ ～ $9$ を適当に作り、 $a, b$ の短い方の桁数を過ぎた後は、繰り上がりが維持されている可能性も考慮して余ったものを $9$ ～ $1$ の順に並べることにする。
これだけだと嘘くさいとは思ったがやはり例２が駄目で、一の位が $4+6$ になってしまい、十の位で $3+6+1$ が作れなくなるため、一の位を $5+5$ にできる方法を考える。
　
一の位は、十の位以降で $a_i+b_i=9$ を作れる個数が減らないように決める方法があるならば、そのようにする必要がある。
$a, b$ に含まれる $1$ ～ $9$ の個数から、 $(1, 8), (2, 7), \cdots, (8, 1)$ の組合せを作れる個数を一旦引いた上で合計 $10$ ～ $19$ が作れるかどうかを試すようにする。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();
        br.close();

        int[] x = new int[10];
        for (int i = 0; i < a.length; i++) {
            x[a[i] - '0']++;
        }
        int[] y = new int[10];
        for (int i = 0; i < b.length; i++) {
            y[b[i] - '0']++;
        }

        // (1, 8)、(2, 7)、・・・分を一旦引く
        int[] q = new int[10];
        for (int i = 1; i < 9; i++) {
            q[i] = Math.min(x[i], y[9 - i]);
            x[i] -= q[i];
            y[9 - i] -= q[i];
        }

        int min = Math.min(a.length, b.length);
        StringBuilder sa = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        int k = 0;
        int s = 0;
        // 一の位
        label:
        for (int j = 10; j < 20; j++) {
            for (int j1 = 1; j1 < 10; j1++) {
                int j2 = j - j1 - k;
                if (j2 < 10 && x[j1] > 0 && y[j2] > 0) {
                    sa.append(j1);
                    sb.append(j2);
                    x[j1]--;
                    y[j2]--;
                    k = 1;
                    s = 1;
                    break label;
                }
            }
        }

        // 引いた分を戻す
        for (int i = 1; i < 9; i++) {
            x[i] += q[i];
            y[9 - i] += q[i];
        }

        label:
        for (int i = s; i < min; i++) {
            for (int j = 10; j < 20; j++) {
                for (int j1 = 1; j1 < 10; j1++) {
                    int j2 = j - j1 - k;
                    if (j2 < 10 && x[j1] > 0 && y[j2] > 0) {
                        sa.append(j1);
                        sb.append(j2);
                        x[j1]--;
                        y[j2]--;
                        k = 1;
                        continue label;
                    }
                }
            }
            for (int j = 2; j < 10; j++) {
                for (int j1 = 1; j1 < j; j1++) {
                    int j2 = j - j1 - k;
                    if (j2 < 10 && x[j1] > 0 && y[j2] > 0) {
                        sa.append(j1);
                        sb.append(j2);
                        x[j1]--;
                        y[j2]--;
                        k = 0;
                        continue label;
                    }
                }
            }
        }

        // aとbの桁数が異なる場合の余り分の処理
        int[] z = x;
        StringBuilder sb2 = sa;
        if (b.length > min) {
            z = y;
            sb2 = sb;
        }
        for (int i = 9; i > 0; i--) {
            for (int j = 0; j < z[i]; j++) {
                sb2.append(i);
            }
        }

        sa.reverse();
        sb.reverse();
        System.out.println(sa.toString());
        System.out.println(sb.toString());
    }
}