AtCoder Beginner Contest 258

ABC

コンテスト前のレート：1990
レート通りのパフォーマンスが得られる順位：343位（2000点、96分50秒）

A - When?

問題
サンプルに助けられた。

思考過程
  1. K \lt 60か60 \le Kかで場合分けする。
  2. 例１が"22:3"となってしまったので0埋めしたい。
  3. printfメソッドで"%02d"と形式指定すれば2桁まで0埋めができる。
import java.util.Scanner;

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

        if (k < 60) {
            System.out.printf("21:%02d\n", k);
        } else {
            System.out.printf("22:%02d\n", k - 60);
        }
    }
}

ここまで1分54秒＋0ペナ。589位。


B - Number Box

問題
初め誤読した上、実装にも時間がかかった。

思考過程
  1. 8方向に隣接する2マスを全探索して最大の組を見つけ、その2マスを往復し続ける？
  2. と思ったら、一直線にしか移動できないらしい。
  3. であれば、始点N^2箇所\times 8方向を全探索する。
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 = new char[n][n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = s[i][j] - '0';
            }
        }

        int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
        int[] dy = {0, 1, 0, -1, 1, -1, 1, -1};
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 8; k++) {
                    long v = 0;
                    for (int k2 = 0; k2 < n; k2++) {
                        int x = (i + dx[k] * k2 + n) % n;
                        int y = (j + dy[k] * k2 + n) % n;
                        v = v * 10 + a[x][y];
                        ans = Math.max(ans, v);
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで8分55秒＋0ペナ。419位。


C - Rotation

問題

思考過程
  1. クエリ1では、文字列の先頭とする位置を管理する変数に対して計算を行う。
  2. クエリ2では、上記の変数+x番目を出力する。
  3. サンプルが合わず、クエリ1で加算していたのを減算に修正。NQはintに収まらないのでオーバーフロー対策もする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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 q = Integer.parseInt(sa[1]);
        char[] s = br.readLine().toCharArray();
        int idx = 0;
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            int x = Integer.parseInt(sa[1]);
            if (t == 1) {
                idx += n - x;
                idx %= n;
            } else {
                System.out.println(s[(idx + x - 1) % n]);
            }
        }
        pw.flush();
        br.close();
    }
}

ここまで12分20秒＋0ペナ。307位。


D - Trophy

問題

思考過程
  1. B_iが小さいステージにたどり着いたら、あとはそのステージのみクリアし続けることになる。
  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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        long x = Integer.parseInt(sa[1]);
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            a[i] = Integer.parseInt(sa[0]);
            b[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        long ans = Long.MAX_VALUE;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i] + b[i];
            x--;
            if (x < 0) {
                break;
            }
            long val = sum + b[i] * x;
            ans = Math.min(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで16分46秒＋0ペナ。152位。


E - Packing Potatoes

問題

思考過程
  1. mod Nで何番目のじゃがいもから箱に入れ始めるかで、何個入るか（次に何番目のじゃがいもから入れ始めることになるか）が決まる。これはしゃくとり法で求められる。箱1つでじゃがいもが何周もする場合にも注意する。
  2. ダブリングをすれば「dp[i][j]:=j番目のじゃがいもからスタートして2^i個の箱に詰めた時の次のスタート位置」が求められるので、これでK_i-1個詰めた後のスタート位置がわかる。
  3. 答えの出力用に、上記2.のDP配列だけでなく、上記1.の「何個入るか」の配列もDP配列と一緒に準備しておく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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 q = Integer.parseInt(sa[1]);
        int x = Integer.parseInt(sa[2]);
        sa = br.readLine().split(" ");
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(sa[i]);
        }
        long[] k = new long[q];
        for (int i = 0; i < q; i++) {
            k[i] = Long.parseLong(br.readLine()) - 1;
        }
        br.close();

        // じゃがいもの周期1周分の合計
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += w[i];
        }

        long x1 = x / sum * n; // 周期部分の個数
        long x2 = x % sum; // 1周しない範囲で箱に入れるべき重さ
        int m = 41;
        int[][] dp = new int[m][n];
        long[] num = new long[n]; // 3
        long now = 0;
        int r = 0;
        for (int i = 0; i < n; i++) {
            // 1
            while (now < x2) {
                now += w[r % n];
                r++;
            }
            dp[0][i] = r % n;
            num[i] = x1 + r - i;
            now -= w[i];
        }

        // 2
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n; j++) {
                dp[i + 1][j] = dp[i][dp[i][j]];
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int a = 0;
            for (int j = 0; j < m; j++) {
                if ((k[i] >> j & 1) == 1) {
                    a = dp[j][a];
                }
            }
            pw.println(num[a]);
        }
        pw.flush();
    }
}

ここまで35分38秒＋ペナ。96位。



この時点で既にGの方が正解者数が多かったのでそちらからやることも考えたが、まずはFの問題を読む。
場合分けは大変だけど知識が必要な感じではなさそう？
とりあえず頑張ってみたら、かなり時間がかかった挙句例２が2ケース合わない。

そこまでやってGをまともに見始めるが、すぐに解けそうな感じではなく、8割方解けていると思われるFを頑張ることにする。
しかし結局解けず。

Gは5～10分程度しか見ていないが、右上半分だけ見ていて横方向と縦方向に見る場所を動かしながら比較したい感じで、それだけだとどうやって高速化できるのか全く想像できないと思っていた。



最終結果：ABCDEの5完1500点、35分38秒、491位、パフォーマンス1842
レート変動：1990→1976（-14）


やっぱりFやGの打率が上がらないと早解きで傷を浅くできるかどうかになってしまう感じ。
ノルマ的にはFが時間内に解けさえすればよかった程度だが、今回はFもGも「仕方ない」ではなく「ちゃんと解けたい」と思う内容だった。