AtCoder Grand Contest 049 - ks2mのブログ

A - Erasing Vertices
- 思考過程
B - Flip Digits
- 思考過程
C - Robots
- 思考過程

コンテスト前のレート：1670
レート通りのパフォーマンスが得られる順位：496位（600点、41分56秒）

A - Erasing Vertices

問題
40分くらいかけて解けず。
最終的に実装が重そうな解法を考えてはいたが、そこまで自信があったわけでもなく、実装に時間かけて失敗するくらいならとC問題に賭けていた。

思考過程

例１の図を書いてみる。
さらにいくつかの頂点や辺を足してみる。
強連結成分分解をすると、削除する頂点から下流にある頂点が全て消えることがわかる。
メモ化再帰でDPすればできそうな気がしてくる。
枝分かれしている場合があり、全体が1つの連結成分ではない場合もある。
強連結成分分解した後、連結成分ごとに分けて、終点からの深さごとにまとめて計算できる？気がしないでもないけど、できたとしても大変そうだしサンプルが弱くて確認できない。

B - Flip Digits

問題
40分ほどで一応通せた。
初回提出がWAで死んだかと思ったけどなんとか。

思考過程

例３などを元に動きを考えてみると、"01"→"10"のように変えて'1'を左に動かしていくのが基本で、'1'を右に動かしていくことはできない。
'1'の数が増えることはなく、"01"→"10"で変わらないか、"11"→"00"で $2$ 個減るかしかない。
とりあえず右から見ていって、 $S, T$ に現れる'1'の累積数 $c1, c2$ を比較し、 $c1 \lt c2$ となる箇所があったら、'1'を右に動かす必要が出てくるので不可能。
最終的に'1'の個数の差 $d=c1-c2$ が奇数の場合も、'1'が減るのは $2$ 個ずつなので不可能。
　
もう一度右から調べていき、 $S, T$ に現れる'1'を対応付けていって、その位置の差を答えに足していく。
余った $d$ 個は、一番左まで持っていくと、"11"→"00"にできるので、その操作に必要な回数を答えに足す。　→半分くらいWA
　
別に一番左まで持っていかなくても"11"→"00"の操作を行うことはでき、 $c1 \lt c2$ を崩さない範囲でなるべく右の方でやった方が良さそう。
$T$ の各'1'を $S$ のどれかの'1'と対応付けた上、 $S$ の残った'1'を寄せて"11"→"00"を行うことになる。
対応付けについては、 $S$ で'1'となっている位置をあらかじめTreeSetに入れておき、 $T$ を左から調べて各'1'の位置以上で最小の値をTreeSetから取得していく。取得したものを取り除くことで、 $S$ の同じ位置と複数対応することを避ける。
TreeSetに $d$ 個の要素が残るので、それらは小さい順に $2$ 個ずつくっつける。
$1$ つ目の位置を $x$ 、 $2$ つ目の位置を $y$ とすると、 $y$ を $x$ の隣に持ってくるのに $y-x-1$ 回、"11"→"00"の操作に $1$ 回かかるので、足して $y-x$ 回。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] s = br.readLine().toCharArray();
        char[] t = br.readLine().toCharArray();
        br.close();

        int c1 = 0;
        int c2 = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '1') {
                c1++;
                set.add(i); // 思考過程9の事前処理
            }
            if (t[i] == '1') {
                c2++;
            }
            // 思考過程3
            if (c1 < c2) {
                System.out.println(-1);
                return;
            }
        }
        // 思考過程4
        int d = c1 - c2;
        if (d % 2 == 1) {
            System.out.println(-1);
            return;
        }

        long ans = 0;
        // 思考過程9
        for (int i = 0; i < n; i++) {
            if (t[i] == '1') {
                Integer x = set.ceiling(i);
                set.remove(x);
                ans += x - i;
            }
        }
        // 思考過程10, 11
        while (!set.isEmpty()) {
            int x = set.pollFirst();
            int y = set.pollFirst();
            ans += y - x;
        }
        System.out.println(ans);
    }
}

ここまで79分54秒＋1ペナ。485位。

C - Robots

問題
2時間近く費やして解けず。
初手で、適当な大きい数に変えれば実質ボールをなくすことができると思ってしまい、増やせるケースに全然気付かず、結局問題を正しく把握することすらできていなかった。

思考過程

例２を元に左からDPしていくことを考える。
$1$ 番目まで見たとき、 $B_1$ を $3→0$ に減らすしかないので $dp[1]=3$ 。
※実は $B_1$ を $3→2$ に減らして $A_1+1$ に書き換えれば $1$ 回で済むが、コンテスト終了まで気付くことはなかった。以下はそれが完全に抜けていることが前提。
　
$2$ 番目は $1$ 番目まで届かず全く関係ないので $dp[2]=3$ 。
$3$ 番目はちょうど前の $2$ つを破壊し、座標 $1$ で止まるので $dp[3]=0$ 。
・・・
色々なパターンを考えた結果、整理すると、 $A_i \leq B_i$ が来たら、 $dp[i]=B_i - A_i + 1$ 。
$A_i \gt B_i$ の場合は、 $(A_i-B_i)$ から $A_i$ までの範囲の左から途中までは壊さず、途中から右は壊すという操作ができるため、 $A_j \lt (A_i-B_i)$ となる最小の $x$ を求め、 $dp[i] = dp[x]$ ～ $dp[i-1]$ の最小値。
これはセグ木に乗せるだけ。　→8/41しか通らない。
　
ボールの値を適当な大きい数に変えて捨てることしか考えていなかったが、普通にロボットの動きに影響ある範囲の数に書き換え、後ろの方のロボットがより前の方まで壊せるようにすることもできる。
※なお、この時点ではまだ $B_i$ を減らして $B_j$ に足すことしか考えていない $(i \lt j)$ 。
これだと $O(N^2)$ はかかりそうな・・・という思考から抜け出すことなく終了。