AtCoder Beginner Contest 175 - ks2mのブログ

A - Rainy Season
- 思考過程
B - Making Triangle
- 思考過程
C - Walking Takahashi
- 思考過程
D - Moving Piece
- 思考過程
- ペナルティ
E - Picking Goods
- 思考過程
E - Picking Goods（2020/8/16追記）
F - Making Palindrome

コンテスト前のレート：1775
レート通りのパフォーマンスが得られる順位：528位

A - Rainy Season

問題
長さが3しかないので、愚直にif文を書く方針とした。

思考過程

"RRR"、"RR"、"R"の順に、 $S$ に含まれているか試す。

import java.util.Scanner;

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

        if (s.indexOf("RRR") != -1) {
            System.out.println(3);
        } else if (s.indexOf("RR") != -1) {
            System.out.println(2);
        } else if (s.indexOf("R") != -1) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

ここまで1分22秒＋0ペナ。162位。

B - Making Triangle

問題
場合分けが極力少なくなるように考えた。

思考過程

$O(N^3)$ が間に合う制約なので、 $3$ 重ループを回して条件を満たすものを数える。
カウントするものを、 $i \neq j \neq k$ かつ $L_i \lt L_j \lt L_k$ であるものに限定すれば、あとは三角形の成立条件として $L_i + L_j \gt L_k$ だけ判定すればよくなる。

後から気が付いたが、 $i \neq j \neq k$ は $L_i \lt L_j \lt L_k$ ならば必ず満たされるので、なくても通る。

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

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i != j && j != k
                            && l[i] < l[j] && l[j] < l[k]
                            && l[i] + l[j] > l[k]) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで5分05秒＋0ペナ。336位。

C - Walking Takahashi

問題
$K \times D$ でオーバーフローしないようにすることだけは常に頭に置いていた。

思考過程

座標 $0$ からの距離だけがわかればいいので、 $X$ の絶対値を取って $X \gt 0$ の場合のみ考える。
$K \times D$ が大き過ぎればオーバーフローするが、十分小さければ計算する必要もあるので、場合分けしたい。
$KD \leq X$ の場合、 $X - KD$ が答え。ただし、オーバーフロー回避のため、移項して $K \leq X/D$ という判定にする。
$K \gt X/D$ の場合、とりあえずまずは非負で $0$ に最も近い座標 $X_2$ まで移動する。
残りの移動は $X_2$ と $X_2-D$ を行ったり来たりするので、残った移動回数 $R = K - X/D$ の偶奇によりいずれかを出力する。

import java.util.Scanner;

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

        x = Math.abs(x);
        if (x / d >= k) {
            System.out.println(x - k * d);
        } else {
            long k2 = x / d;
            long x2 = x - k2 * d;
            long r = k - k2;
            r %= 2;
            x2 -= r * d; // 残りが偶数なら-0、奇数なら-D
            System.out.println(Math.abs(x2));
        }
    }
}

ここまで11分58秒＋0ペナ。247位。
10分超えていてちょっと手間取ったと思ったけど十分早かったらしい。

D - Moving Piece

問題
初回WAの時点でE問題も見たが、すぐに解けそうになかったので基本的にはDを考えることにした。WAを重ねるにつれて徐々にEに浮気していくが、Dも完全には捨てずにいたらなんとか解けた。
最終的にコーナーケースが何だったかわかるまでに20分以上。

思考過程

問題の制約では、数字の $6$ 字型のような遷移はせず、必ず $0$ 字型の遷移になる。（途中からループになるのではなく、必ずスタート地点に戻る）
$O(N^2)$ が間に合うので、スタート地点 $N$ 通りで毎回素直にスタートに戻るまでの遷移を行う。以下は $1$ つのスタート地点についてのみ考える。
　
スコアの合計値(one)と、合計値の最大値(max)を持ちながら、スタートに戻るまで遷移する。
戻る前に $K$ 回に達したら、その時点のmaxが答え。
$1$ 周したら、 $1$ 周の合計値(one)が正でない場合、最初の $1$ 周の間のmaxが答え。
oneが正の場合、最後の $1$ 周分手前まではone×周回分を計算してしまい、最後の $1$ 周分以上 $2$ 周分未満の部分だけ、改めて合計値(one)と合計値の最大値(max2)を持ちながらシミュレーションを行う。

ペナルティ

上記4で、全体のansとのmaxを取り忘れていた。　→9ケースWA
one×周回分を計算するところで、周回数を $K/J-1$ ではなく $K/J$ としていた（ $J$ は周期）。確定で計算してしまってよいのは、ゴールから丸 $1$ 周分以上手前まで。　→4ケースWA

本質的に解決していないとは思いながらも、ちょっとずつ書き換えながら4ケースWAを繰り返していた。

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

        long ans = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int idx = i;
            long max = Long.MIN_VALUE;
            long one = 0;
            for (int j = 1; j <= k; j++) {
                idx = p[idx];
                one += c[idx];
                max = Math.max(max, one);
                if (idx == i) { // 1周した場合
                    if (one > 0) { // 1周の合計が正の場合
                        long x = k / j;
                        long val = one * (x - 1); // 1周以上手前までの合計
                        long r = k % j + j; // 残りの移動回数
                        one = 0;
                        long max2 = 0;
                        for (int j2 = 0; j2 < r; j2++) {
                            idx = p[idx];
                            one += c[idx];
                            max2 = Math.max(max2, one);
                        }
                        val += max2;
                        max = Math.max(max, val);
                    }
                    break;
                }
            }
            ans = Math.max(ans, max);
        }
        System.out.println(ans);
    }
}

ここまで61分45秒＋4ペナ。650位。
ここから最終結果まで思ったより転落して辛い。

E - Picking Goods

問題
4ケースTLEで解けず。
以下はTLE解法。

思考過程

スタートを左上、ゴールを右下として、とりあえず上と左から大きい方を取って遷移するDPを考える。
アイテムがないマスは、単純に上と左のmaxを取るのみ。
アイテムがあるマスは、上と、左全部からの遷移を考える必要がある。
もう少しよく考えると、左の遷移元はアイテムがあるマスのみ候補にすればよい。
遷移先マスから左に向かって、上位 $3$ 個を保持しながら、「アイテムマスの $1$ つ上 $+$ 最大 $3$ 個の合計」を求めていく。
遷移元として調べるマスがならしで $O(K)$ なので、全体で $O(KC)$ くらい？
しかし、この見積もりが合ってたとしても、 $3$ 個保持する分の $3$ 倍も入れて $3 \times 3 \times 2 \times 10^8$ 程度で $10^9$ 以上なのでやっぱり間に合ってなさそう。（ $0$ の数だけ見て $10^8$ ならいけるのではと思ってしまった）
定数倍改善を試みるが当然変わらず。

E - Picking Goods（2020/8/16追記）

$dp[x][y][z]$ ：マス $(x, y)$ まで見て、 $x$ 行目で $z$ 個拾っている場合の最大値
で、 $3$ 個の内訳とかも全然気にする必要もなく、ナップサックのようなDPをするだけだった。

左からの遷移・・・拾わずに $z$ 個→ $z$ 個の場合と、拾って $z-1$ 個→ $z$ 個の場合のmax。
上からの遷移・・・拾わずに $0$ ～ $3$ 個→ $0$ 個の場合、拾って $0$ ～ $3$ 個→ $1$ 個の場合。

$0$ 個と $1$ 個の場合は、左と上のmaxも取る。

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

        long[][][] dp = new long[h + 1][w + 1][4];
        for (int x = 1; x <= h; x++) {
            for (int y = 1; y <= w; y++) {
                // 左からの遷移
                for (int z = 1; z <= 3; z++) {
                    // max（拾わない、拾う）
                    dp[x][y][z] = Math.max(dp[x][y - 1][z], dp[x][y - 1][z - 1] + v[x][y]);
                }
                // 上からの遷移＆左とのmax
                long ue = max(dp[x - 1][y]); // 1つ上のマス
                dp[x][y][0] = Math.max(dp[x][y - 1][0], ue); // max（左（拾わない）、上（拾わない））
                dp[x][y][1] = Math.max(dp[x][y][1], ue + v[x][y]); // max（左、上（拾う））
            }
        }
        System.out.println(max(dp[h][w]));
    }

    static long max(long[] a) {
        long ret = 0;
        for (int i = 0; i < a.length; i++) {
            ret = Math.max(ret, a[i]);
        }
        return ret;
    }
}

F - Making Palindrome

問題
Dが通ったところで一応5分ほど考えたが、正解者数の少なさも見て無理だと思ったので早々に諦め。
　

最終結果：ABCDの4完、81分45秒、1109位、パフォーマンス1450
レート変動：1775→1747

5完最下位ならパフォ1730、Dが早く解けたら1500強、Dが解けなくても1300程度といったところだったので、Dの恩恵が少なく、Eが解ければセーフ、Eが早く解ければおいしいという感じだった。

青diffまでの問題が枯渇しているので、最近は黒diffから程よい問題を発掘するべく、JOIの難易度6～8埋めをしているが、今日もDPができなかったし、DPまとめコンテストとかをやった方がいいのかもしれない。