ABC-only 回に参加しました。

競プロ参戦記

この連載記事では、着手した問題の考察を自分なりに書いていきます。

前回: 競プロ参戦記 #40 Cake 123 | ABC123

AtCoder Beginner Contest 124

問題の詳細は問題一覧を参照してください。
問題一覧: https://atcoder.jp/contests/abc124/tasks

A - Buttons

問題概要: 大きさが X のボタンを押すと、X 枚のコインを獲得し、そのボタンは大きさが1小さくなる。いま2個のボタンがあって、それぞれ大きさが A, B である。いずれかのボタンを押す操作を最大2回まで行うとき、最大で何枚のコインを獲得できるか。

考察:

選択肢は以下の3つです:

大きさ A のボタンを押し、(少し縮んだ) 大きさ (A-1) のボタンを押す
大きさ B のボタンを押し、大きさ (B-1) のボタンを押す
大きさ A のボタンを押し、B のボタンを押す

上記の各操作で獲得できるコインの枚数を式で表すと以下の通りです。

A + A - 1 = 2A - 1
B + B - 1 = 2B - 1
A + B

この3つの最大値を取ればいいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc124/submissions/4943244

    // 抜粋
    println!("{}", max(A + A - 1, max(A + B, B + B - 1)))

B - Great Ocean View

問題概要: 直線上に N 個の山があり、左端の山の左側には海がある。各山の山頂には旅館があり、以下の条件が成り立つとき i 番目の旅館から海を眺められる。海を眺められる旅館の個数を求めよ。

H[1] ≤ H[i], H[2] ≤ H[i], .., H[i - 1] ≤ H[i] がすべて成り立つ

考察:

言われたとおりに2重ループを書くと、旅館の個数 N が小さいので正解になりますが、もう少し考察してみましょう。

条件は「H[i] が左側にあるすべての山の高さ以上である」ことを表していますが、言い換えれば「H[i] は左側にある山の高さの 最大値 以上である」ともいえます。

そのため i を増加させながら「i 番目より左にある山の最大値」を変数で持っておけば1重ループになります。

左端にある山 (i = 0) だけは必ず海を眺められるので、ループの外に出して特別扱いします。

    // 抜粋

    // 海を眺められる旅館の個数
    // (左端の旅館からは必ず海を眺められるので始めから 1)
    let mut count = 1;
    // i 番目の旅館より左にある山の高さの最大値
    let mut max_h = H[0];

    for i in 1..N {
        if H[i] < max_h {
            // i 番目の旅館から海を眺められない
            // max_h を更新する必要もない
            continue;
        }

        max_h = max(max_h, H[i]);
        count += 1;
    }

    println!("{}", count)

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc124/submissions/4942153

C - Coloring Colorfully

問題概要: 直線上に N 個のタイルがあり、左から i 番目のタイルの色は S[i] (0 または 1) である。いくつかのタイルの色を 0 (黒) か 1 (白) に塗って、どの隣り合う 2 枚のタイルも異なる色で塗られているようにするには、最小で何枚のタイルを塗る必要があるか求めよ。

考察:

「どの隣り合う 2 枚のタイルも異なる色で塗られている」とは、要するに 0101.. と 1010.. のどちらかです。

色を塗った後のタイルの色が 0101.. になるケースを考えます。このとき塗った枚数は明らかで、各タイルのもとの色と塗られた後の色を比較して、色が違っているタイルは塗られたタイル、同じなら塗られていないタイルと数えればいいです。

結局、0101.. になるケースと 1010.. になるケースの2つで、塗る必要があるタイルの枚数を求めて、小さいほうが答えになります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc124/submissions/4939562

D - Handstand

問題概要: 0 と 1 からなる長さ N の数列が与えられる。以下の操作を最大で K 回まで行った後、1 が連続する区間の長さの最大値を求めよ。

操作: 数列上の区間を1つ選び、区間内の 0 を 1 に、1 を 0 に置き換える。

考察

例えば数列 S=1010001、操作回数 K=1 とします。後半の 000 の部分に対して操作をして S=1011111 にすると最良です。

このように 0 が連続している部分に操作をすると最善になりそうな気がします。

考察 1

気になるのは「1 を含む区間を反転してから、0 になった部分を再び反転する」ようなケースがあるかどうかです。

例えば 00100 → 11011 → 11111。しかし、これはよく見ると 00100 → 11100 → 11111 でも操作回数が同じです。1 → 0 になるような操作はしなくてよさそう。

考察 2

次に考えるのは「どの 0 を操作対象に選ぶか」です。操作した区間が最終的に 1 が連続する最長の区間に含まれなければ、操作は最善ではなかったことになります。(例えば 0100111 → 1100111 は最善ではない。)

「最終的に 1 が連続する最長の区間」(以下、最長区間) が分かれば解けそうです。もちろん区間をすべて列挙するのは O(N^2) なので間に合いません。

「最長区間の先頭」はどうでしょうか。先頭を決めれば、そこから右に向かってトンネルを掘り進めるように、右にある 0 を 1 にしていくのが最善です。例えば 1010010 で2個目の 1 を最長区間の先頭に選んだとすると、1010010 → 101110 → 101111。

実装

最後に実装です。

0 や 1 が連続している部分はひとまとめに扱うことになるので、連続している個数の列に変換するとよさそうです。

例: S=11101111011111 → X=31415

この数列 X の上で最長区間の候補を列挙します。ここではしゃくとり法というアルゴリズムを使うと楽です。(2分探索を使う方法もあります。)

状態として、区間の左右に加えて、区間の総和 (S 上での長さ) と操作回数 (0 を 1 に変えた回数) をもっておきます。

例えば K=1 だとして、最長区間の先頭が 3 (1 が3個並ぶ部分) だとすると、0 の区間を1つだけ 1 の区間にできるので、314 の部分が最長区間になります。

    31415
    ^^^

次に 3 をこの区間から取り除いて、先頭が 1 (左のほう) のケースを考えると、右端は変わらず最長区間は 14 の部分です。

    31415
     ^^

次に 1 をこの区間から取り除くと、操作できる回数が 1 増えます。右側にある 1 (0 が 1 個あるという意味) を区間に含めることができるようになって、最長区間が右端に達します。

    31415
      ^^^

このように進めていくと O(N) 時間で最長区間の候補を列挙できます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc124/submissions/4948410

追記 1

さらに考察を進めると、これは厳密な表現ではありませんが、列挙すべき数列 X 上の区間は長さ 2K+1 のものに限られると分かります。0 の区間と 1 の区間は交互に出現するからです。この事実を利用すると、公式の解説 PDF に書かれている通り累積和で解けるらしいです。

追記 2

上述の「同じ値が連続する部分を個数で置き換える」操作 (ランレングス圧縮) は、しゃくとり法による解法では必須ではありません。区間の端点を進める際に、r += 1 とするのではなく、同じ値が連続している部分を一気にスキップするようなループを回すようにすればいいからです。

提出 (Rust, AC): https://atcoder.jp/contests/abc124/submissions/4957166

3重ループなのに O(N) 時間というのが微妙におもしろい。

今回の教訓

C: 最適な操作をした後の状態を考えるといいかも
D: 「何が分かれば答えが求まるのか」と考えるといいかも