AtCoder Beginner Contest 237(Rated範囲外)

ABC

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


またまた結果ボロボロだったし、時間もあまりないので雑に書きます。

A - Not Overflow

問題

思考過程
  1. JavaではInteger.MIN_VALUEが-2^{31}、Integer.MAX_VALUEが2^{31}-1なので、それらを用いて判定する。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        if (Integer.MIN_VALUE <= n && n <= Integer.MAX_VALUE) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分32秒＋0ペナ。634位。


B - Matrix Transposition

問題
誤ってD問題が表示されていたのを20分近く解けず、諦めてCを解こうとするもそれもWAで、もう一度開き直したら正しいB問題が表示されて結局この問題からやることに。

思考過程
  1. 問題文の通りB_{ij}にA_{ji}を設定していく・・・と思ったがそのまま出力することにする。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        for (int i = 0; i < w; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < h; j++) {
                sb.append(a[j][i]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

ここまで32分51秒＋0ペナ。4783位。


C - kasaka

問題
下記2.で一旦行き詰ってしまい、Eまで解いてから戻ってくる。

思考過程
  1. 先頭と末尾の'a'を取り除いた部分が回文になっているかを調べる。　→5ケースWA
  2. 'a'を取り除いた数が、先頭\leq末尾でないと駄目だった。　→2ケースWA
  3. 上記2.の判定が、全部'a'の時におかしくなっていたので直す。
import java.util.Scanner;

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

        int n = s.length;
        // 先頭から見て初めてa以外が登場する位置
        int l = n;
        for (int i = 0; i < n; i++) {
            if (s[i] != 'a') {
                l = i;
                break;
            }
        }

        // 末尾から見て初めてa以外が登場する位置
        int r = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != 'a') {
                r = i;
                break;
            }
        }

        // l～rの範囲が回文か
        boolean flg = true;
        for (int i = 0; i < r - l; i++) {
            if (s[l + i] != s[r - i]) {
                flg = false;
                break;
            }
        }

        // 回文かつ、全部a または 先頭aの数≦末尾aの数
        if (flg && (r < l || l < n - r)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ABDECと解いた時点で64分46秒＋2ペナ。1002位。


D - LR insertion

問題
逆からやるとか全く考えておらず、無理矢理前からやった。

思考過程
  1. LinkedListは挿入操作がO(1)だと思いがちだが、挿入位置を特定するのが難しそうなのでやめる。（使える方法あるんだろうか）
  2. 「LRR\cdots」の単位にまとめてみてどうかとかやろうとしてみたけど上手くいかずやめる。
    　
  3. 各要素の左右にある要素は何であるかを上手く管理することを考える。（ある種、LinkedListを自力実装しているようなものかもしれない）
  4. 例１を見ながら、まず0の左に1を置いたとき、L[0]=1, R[1]=0とする。
  5. 次に1の右に2を置くと、L[2]=1, R[1]=2となるのに加え、L[0]=2, R[2]=0となる。
  6. といった更新を行うと、最後に左側が存在しない要素から始めて右側の要素をたどっていけば並び順がわかる。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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();
        char[] s = sc.next().toCharArray();
        sc.close();

        int[] l = new int[n + 1];
        int[] r = new int[n + 1];
        Arrays.fill(l, -1);
        Arrays.fill(r, -1);
        for (int i = 0; i < n; i++) {
            if (s[i] == 'L') {
                if (l[i] != -1) {
                    r[l[i]] = i + 1;
                    l[i + 1] = l[i];
                }
                l[i] = i + 1;
                r[i + 1] = i;
            } else {
                if (r[i] != -1) {
                    l[r[i]] = i + 1;
                    r[i + 1] = r[i];
                }
                r[i] = i + 1;
                l[i + 1] = i;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < l.length; i++) {
            if (l[i] == -1) {
                ans.add(i);
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            ans.add(r[ans.get(ans.size() - 1)]);
        }

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

ABDと解いた時点で42分22秒＋0ペナ。2205位。


E - Skiing

問題

思考過程
  1. 2点の標高差をCとすると、標高が高い方から低い方に向かってコスト-C、標高が低い方から高い方に向かってコスト2Cの辺を張る。
  2. コストが負の辺は存在するが、負閉路は存在しないと思われるので（同じ広場に戻ってくるために途中で標高が上下したらコストは必ず正になるため、コスト0の閉路が最小）、あとはただのダイクストラ法を行う。
  3. 怪しさは感じたけど出遅れまくっているのでとりあえず投げ、通ったのでヨシ。

案の定After_contestで落とされた。
提出
ABDEと解いた時点で52分44秒＋0ペナ。837位。


F - |LIS| = 3

問題
残り時間30秒で例３まで通っていける！と思ったら、試行錯誤していた時の名残で、modを取る部分のfor文の範囲を直せておらず、オーバーフローで1ペナ。
直して再提出したら、8秒遅れでAC。

思考過程
  1. 「dp[i][j][k]:=i番目まで見てLISの長さがjでLISの最後がkの通り数」をしようとしたが上手くいかず。
  2. 「dp[i][j_1][j_2][j_3]:=i番目まで見てLISをした時のDP配列のx番目がj_xの通り数」とすると、LISをした時のDP配列が更新される条件と対応させることで遷移が書ける。
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 = sc.nextInt();
        sc.close();

        int mod = 998244353;
        long[][][] dp = new long[m + 2][m + 2][m + 2];
        dp[m + 1][m + 1][m + 1] = 1;
        for (int i = 0; i < n; i++) {
            long[][][] wk = new long[m + 2][m + 2][m + 2];
            for (int j = 1; j <= m + 1; j++) {
                for (int j2 = j; j2 <= m + 1; j2++) {
                    for (int j3 = j2; j3 <= m + 1; j3++) {
                        for (int k = 1; k <= m; k++) {
                            if (k <= j) {
                                wk[k][j2][j3] += dp[j][j2][j3];
                            } else if (k <= j2) {
                                wk[j][k][j3] += dp[j][j2][j3];
                            } else if (k <= j3) {
                                wk[j][j2][k] += dp[j][j2][j3];
                            }
                        }
                    }
                }
            }
            for (int j = 1; j <= m + 1; j++) {
                for (int j2 = j; j2 <= m + 1; j2++) {
                    for (int j3 = j2; j3 <= m + 1; j3++) {
                        wk[j][j2][j3] %= mod;
                    }
                }
            }
            dp = wk;
        }
        long ans = 0;
        for (int j = 1; j < m + 1; j++) {
            for (int j2 = j; j2 < m + 1; j2++) {
                for (int j3 = j2; j3 < m + 1; j3++) {
                    ans += dp[j][j2][j3];
                }
            }
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで100分08秒＋3ペナ。（間に合っていない）



Gも問題は読んだが、Fの方が解ける見込みありそうと思ってすぐに捨てた。



最終結果：ABCDEの5完1500点、74分46秒、1117位、パフォーマンス1409相当
レート変動：2074（Unrated）


Fが間に合っていて2000点115分だったとしても、パフォは1800程度。

CとDでドハマりしているし、Fも早くはないのでまあ普通に駄目駄目としか言いようがない。
DとGの正解者数多すぎない？
Dは最初Bに置かれていたせいで、普段よりまともに取り組んだ人が多かったのかな。