モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）(Rated範囲外)

A - Jogging
- 思考過程
B - Perfect String
- 思考過程
C - Just K
- 思考過程
D - Index Trio
- 思考過程
F - Ignore Operations
- 思考過程

コンテスト前のレート：2000
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：328位（1500点、63分24秒）

A - Jogging

問題
ABC-Aとしては過去最も時間がかかったレベル。

思考過程

なんかめんどくさいけど $X$ 秒後に進んでいる距離をそれぞれ求めて結果を比較することにする。
高橋君については、まず $A \times B$ メートル進むのが $\frac{X}{A+C}$ 回。
さらに余りの $X \% (A+C)$ 秒間の内最初の $A$ 秒間（つまり両者のminを取った秒数）、 $B$ メートル進む。
青木君も同様。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int e = sc.nextInt();
        int f = sc.nextInt();
        int x = sc.nextInt();
        sc.close();

        int a1 = x / (a + c) * a * b;
        a1 += b * Math.min(x % (a + c), a);

        int a2 = x / (d + f) * d * e;
        a2 += e * Math.min(x % (d + f), d);

        if (a1 == a2) {
            System.out.println("Draw");
        } else if (a1 > a2) {
            System.out.println("Takahashi");
        } else {
            System.out.println("Aoki");
        }
    }
}

ここまで5分06秒＋0ペナ。476位。

B - Perfect String

問題

思考過程

英大文字と英小文字の条件は、一度でも現れたらtrueとするフラグを用意する。
相異なるの条件は、Setに全ての文字を入れて要素数が減っていないか確認する。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

        boolean a = false;
        boolean b = false;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length; i++) {
            set.add(s[i]);
            if ('A' <= s[i] && s[i] <= 'Z') {
                a = true;
            }
            if ('a' <= s[i] && s[i] <= 'z') {
                b = true;
            }
        }
        if (set.size() == s.length && a && b) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで7分35秒＋0ペナ。310位。

C - Just K

問題
題意の理解に時間がかかったが、結局やるだけ。

思考過程

$S_i$ の選び方を $2^N$ 通り全部試す。
選んだ $S_i$ に登場した各文字の回数をカウントする。
回数が $K$ のものをカウントし、答えとのmaxを取る。

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 k = sc.nextInt();
        char[][] s = new char[n][];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int ans = 0;
        // 1
        int end = 1 << n;
        for (int i = 0; i < end; i++) {
            // 2
            int[] cnt = new int[26];
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    for (int j2 = 0; j2 < s[j].length; j2++) {
                        cnt[s[j][j2] - 'a']++;
                    }
                }
            }
            // 3
            int val = 0;
            for (int j = 0; j < 26; j++) {
                if (cnt[j] == k) {
                    val++;
                }
            }
            ans = Math.max(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで13分03秒＋0ペナ。279位。

D - Index Trio

問題

思考過程

$A_i = A_j \times A_k$ と変形する。
$i, j, k$ の組み合わせを全探索したら $O(N^3)$ で全然駄目だが、 $1 \times 1$ ～ $N$ 、 $2 \times 1$ ～ $\frac{N}{2}$ 、 $\cdots$ のように、上記1.の式に具体的に当てはまる値の組み合わせを全探索すれば調和級数の計算量 $O(A_{max}logA_{max})$ で済む。

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 m = 200000;
        int[] c = new int[m + 1];
        for (int i = 0; i < n; i++) {
            c[sc.nextInt()]++;
        }
        sc.close();

        long ans = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; i * j <= m; j++) {
                ans += (long) c[i] * c[j] * c[i * j];
            }
        }
        System.out.println(ans);
    }
}

ここまで17分44秒＋0ペナ。134位。

Eは「 $i$ 番目まで見て変換後の文字列長が $j$ で最後の文字が $k$ 連続」といったDPを考えて、 $O(N^3)$ から落とせる気がせず。
一応配列ではなくMapを使って $j, k$ が実際にあり得るところしかデータを持たないようにしてみたが、例４が手元実行で明らかにTLEだったので飛ばしてFへ。
Fを解いて戻った後も考察は進まず。

F - Ignore Operations

問題

思考過程

クエリ $1$ を無視しなかった時点で、それより前の操作は全て無意味なので、最後にどのクエリ $1$ を実行したかに注目して考える。
ひとまず入力上の最後のクエリ $1$ を実行したとすると、それより後のクエリ $2$ を $y$ の昇順に並び替え、 $y$ が負であるものを最大 $K$ 個取り除くのが最適。
そこからもう $1$ つ前のクエリ $1$ を起点とするよう変更したとすると、 $K$ を $1$ 減らし、間のクエリ $2$ を加えて取り除くものを再調整すれば差分計算できる。（ここで色々漏れていてWAを重ねる）

import java.io.BufferedReader;
import java.io.InputStreamReader;
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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int k = Integer.parseInt(sa[1]);
        int[] t = new int[n + 1];
        int[] y = new int[n + 1];
        t[0] = 1;
        for (int i = 1; i <= n; i++) {
            sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            y[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        // 実行対象のクエリ2（yの昇順）
        PriorityQueue<Integer> que = new PriorityQueue<>();
        // 除外対象のクエリ2（yの降順）
        PriorityQueue<Integer> que2 = new PriorityQueue<>(Collections.reverseOrder());
        long sum = 0; // 実行対象のクエリ2のyの合計
        long ans = Long.MIN_VALUE;
        for (int i = n; i >= 0; i--) {
            if (t[i] == 2) {
                sum += y[i];
                que.add(y[i]);
            } else {
                ans = Math.max(ans, y[i] + sum);
                // 負の要素を最大k個まで除外
                while (que2.size() < k) {
                    if (!que.isEmpty() && que.peek() < 0) {
                        int e = que.poll();
                        sum -= e;
                        ans = Math.max(ans, y[i] + sum);
                        que2.add(e);
                    } else {
                        break;
                    }
                }
                // 除外した要素の方が大きい場合、入れ替え
                while (!que.isEmpty() && !que2.isEmpty() &&
                        que.peek() < que2.peek()) {
                    int e1 = que.poll();
                    int e2 = que2.poll();
                    que.add(e2);
                    que2.add(e1);
                    sum -= e1;
                    sum += e2;
                    ans = Math.max(ans, y[i] + sum);
                }

                // 1つ前のクエリ1を調べるにあたって、今調べているクエリ1を除外する分を考慮
                k--;
                if (k < 0) {
                    break;
                }
                // 1つ前のクエリ1を調べるにあたって、既に上限まで除外していたら
                // 1個戻す必要がある
                while (que2.size() > k) {
                    int e2 = que2.poll();
                    sum += e2;
                    que.add(e2);
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで71分23秒＋3ペナ。351位。

最終結果：ABCDFの5完1500点、86分23秒、458位、パフォーマンス1835相当
レート変動：2000（Unrated）

今回はノルマを達成するにはEをすぐに飛ばしていればよかったという感じ。
実際一旦すぐにFの問題だけは読んだのだが、Fもすぐに解けそうにないと戻ってしまっていた。

Fではまたもや後でするつもりだった実装を忘れたりしていた。
忘れなければペナ1回は減ったと思う。