AtCoder Grand Contest 048 - ks2mのブログ

A - atcoder < S
- 思考過程
B - Bracket Score
- 思考過程
C - Penguin Skating
- 思考過程

コンテスト前のレート：1719
レート通りのパフォーマンスが得られる順位：507位（300点、7分05秒）

A - atcoder < S

思考過程

とりあえず、最初から条件を満たしていたら $0$ 。
"atcoder"と $S$ を先頭から比較していき、最初に前者の方が大きい文字となった位置を $f$ とする。
$S$ の $j$ 文字目を、 $1$ ～ $min(f, j-1)$ 文字目まで移動させるということを全部試し、条件を満たす中で最小値を求める。全体で $T \times |S| \times 7$ くらいの計算量。

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 t = Integer.parseInt(br.readLine());
        int inf = 1000000000;
        char[] s1 = "atcoder".toCharArray();
        label:
        for (int i = 0; i < t; i++) {
            String s = br.readLine();
            if (s.compareTo("atcoder") > 0) { // 思考過程1
                System.out.println(0);
            } else {
                char[] s2 = s.toCharArray();
                int min = Math.min(s1.length, s2.length);
                // 思考過程2
                int f = 6;
                for (int j = 0; j < min; j++) {
                    if (s1[j] < s2[j]) { // このブロックいらなそう
                        System.out.println(0);
                        continue label;
                    }
                    if (s1[j] > s2[j]) {
                        f = j;
                        break;
                    }
                }

                int ans = inf;
                for (int j = 1; j < s2.length; j++) {
                    for (int j2 = 0; j2 <= f && j2 < j; j2++) {
                        if (s2[j] > s1[j2]) {
                            ans = Math.min(ans, j - j2);
                        }
                    }
                }
                if (ans == inf) {
                    System.out.println(-1);
                } else {
                    System.out.println(ans);
                }
            }
        }
        br.close();
    }
}

ここまで26分02秒＋0ペナ。337位。

B - Bracket Score

問題
TLE解法しか思いつかず。

思考過程

"(())"のような文字列を作るくらいなら"()()"でよいので、括弧が開き続けるとしたら交互になる。
$dp[i][j][k]$ ： $i$ 番目まで見て括弧 $j$ から始まって $k$ 文字開いている状態の最大値
をしてみると $N \times 2 \times N/2$ くらいかなと思いつつ、他に思いつかなかったので念のため実装してみて案の定TLE。

C - Penguin Skating

問題
残り時間数分でやっとサンプルが合ったがWA。

思考過程

$A_i=B_i$ の箇所を動かすことはなさそう？
上記の箇所を除くと、 $A_i \lt B_i$ が連続する区間と $A_i \gt B_i$ が連続する区間に区切れる。
以下、が連続する区間について見てみる。
1. $1$ 個目は $A_0=B_1-1$ ならばOK。　※ $A_0$ は左端のマス $0$ か、 $A_1$ （区間内の最初の要素）の $1$ つ前の要素とする。
2. $2$ 個目は $A_0=B_2-2$ か、 $A_1=B_2-1$ ならばOK。
3. $3$ 個目は $A_0=B_3-3$ か、 $A_1=B_3-2$ か、 $A_2=B_3-1$ ならばOK。
4. ・・・のようになっている気がする。
これはSetを用いて毎回要素を $1$ つずつ追加していって $-X$ の部分を上手く合わせれば存在判定できそうと思ったが、可能かどうかだけでなく最小手数も必要だった。
追加要素は単調増加なので、何番目の要素に当たったかから必要手数がわからないかとかやっていたが、サンプルくらいしか合わず。