AtCoder Regular Contest 133

コンテスト前のレート：2024
レート通りのパフォーマンスが得られる順位：373位（1300点、73分10秒）

A - Erase by Value

問題

思考過程

1. 初めて値が減少している箇所を特定したいが、広義単調増加になっている場合はそのような箇所が見つからないことも考慮が必要。
2. ひとまず初め先頭要素を削除候補としておき、番目以降を見ていってとの大小関係により適切にの更新や処理の打ち切りをすることを考える。

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

        int x = a[0];
        for (int i = 1; i < n; i++) {
            if (a[i] > x) {
                x = a[i];
            }
            if (a[i] < x) {
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (a[i] != x) {
                sb.append(a[i]).append(' ');
            }
        }
        if (sb.length() == 0) {
            System.out.println();
        } else {
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

ここまで4分30秒＋0ペナ。336位。

B - Dividing Subsequence

問題
本当はMLEなのにREになるのなんとかしてほしい。（JavaだとOutOfMemoryErrorが発生するとREになる模様）
下記思考過程5.までは完全に無駄なことをしている。

思考過程

1. 最長共通部分列（LCS）を、イコールではなく割り切れるかどうかに変えるだけで解けそう。　→RE
2. 配列外参照や除算していないかを一生懸命見直すが、入力が制約を満たしていない以外でそのようなことはなさそう。
3. ふと提出結果をよく見たら、メモリが947640KBになっていてMLEっぽいと気付く。
4. 確かに空間計算量だと駄目なので、長さの配列本だけを使うように書き直す。　→TLE
5. 時間計算量も当然駄目だった。一体何をやっているのか。
   　
6. 改めて一から考え直すと、最長増加部分列（LIS）がやりたいことに近い。
7. 通常のLISでは「長さのLISの末尾としてあり得る最小値」を更新していくが、この問題ではと対応させるのインデックスをLISとして捉え、「まで見て長さのLISの末尾としてあり得る最小値」を更新していきたい。
8. これは各についてを全部調べていたらだが、がの倍数になっているだけ調べればになる。
   　
9. あとはLISを貼って少々変更する程度の実装をしたいところだが、まず値からインデックスを取得できるよう、入力時にそのような情報も作成しておく。
10. 各については、対応するの集合を取得し、個数無制限ナップサックのようにならないよう、各を降順に処理する。
11. 各に対して行う処理は通常のLISと同じ。

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

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());
        String[] sa = br.readLine().split(" ");
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] q = new int[n];
        int[] x = new int[n + 1]; // 9
        for (int i = 0; i < n; i++) {
            q[i] = Integer.parseInt(sa[i]);
            x[q[i]] = i + 1;
        }
        br.close();

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < n; i++) {
            // 10. jの降順
            PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
            for (int qj = p[i]; qj <= n; qj += p[i]) {
                int j = x[qj];
                que.add(j);
            }
            while (!que.isEmpty()) {
                int j = que.poll();
                // 11
                int idx = Arrays.binarySearch(dp, j);
                if (idx < 0) idx = ~idx;
                dp[idx] = j;
            }
        }

        int lis = Arrays.binarySearch(dp, Integer.MAX_VALUE - 1);
        if (lis < 0) {
            lis = ~lis;
            lis--;
        }
        System.out.println(lis);
    }
}

ここまで33分02秒＋2ペナ。570位。

C - Row Column Sums

問題

思考過程

1. サンプルの入力値の場合について、とりあえず全マスを最大値であるで埋めてみる。
2. 各行、各列を独立に、それぞれ最小いくつ減らせば余りの条件を満たすのかを調べてみる。
3. 例１が可能で例２が不可能である理由を考える。
   　
4. 行方向についての上記2.の合計と、列方向についての上記2.の合計を比較し、で一致する必要があるのではと当たりを付ける。あるマスの値を減らすと、行方向、列方向共に減らした数の合計が増えるため。
5. 上記4.の条件を満たす場合、（例１の場合）から大きい方（例１の場合）を引いた結果が答えとしてあり得る最大値。
6. あとはそれが構築できないケースがあるのかどうかだが、まあ多分ないのだろう。

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));
        String[] sa = br.readLine().split(" ");
        int h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int k = Integer.parseInt(sa[2]);
        sa = br.readLine().split(" ");
        int[] a = new int[h];
        for (int i = 0; i < h; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[w];
        for (int i = 0; i < w; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long x1 = (long) (k - 1) * w % k;
        long x2 = 0;
        for (int i = 0; i < h; i++) {
            x2 += (x1 - a[i] + k) % k;
        }

        long y1 = (long) (k - 1) * h % k;
        long y2 = 0;
        for (int i = 0; i < w; i++) {
            y2 += (y1 - b[i] + k) % k;
        }

        if (Math.abs(x2 - y2) % k == 0) {
            long rem = Math.max(x2, y2);
            long total = (long) (k - 1) * h * w;
            System.out.println(total - rem);
        } else {
            System.out.println(-1);
        }
    }
}

ここまで44分17秒＋2ペナ。187位。

残り時間はほぼ全てDに使用。Eは問題読んだだけ、Fは開いていない。
Dは愚直を書いて出力された結果を見てエスパーしようとしたが例４が合わず。

最終結果：ABCの3完1300点、54分17秒、252位、パフォーマンス2211
レート変動：2024→2044（+20）

B問題で無駄な考察から離れるまでに10分と2ペナを費やしているのが本当に意味不明だった。
LCSがすぐに出てきたことでうれしくなりすぎて（Aの提出後Bの初回提出まで3分）、計算量が完全に頭から抜けていた。