初めてD問題を解いてみます、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc124)にて開催されました、AtCoder Beginner Contest 124 D問題「D - Handstand」の問題と僕との戦闘記です。

0.はじめに

1.問題文

N 人の人が左右一列に並んでいます。

0, 1 からなる長さ N の文字列 S と正整数 K が与えられます。

左から i 番目の人は、 S の i 文字目が 0 のとき直立し、1 のとき逆立ちしています。

あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。

指示: 1 ≤ l ≤ r ≤ N を満たす整数 l , r を選ぶ。左から l , l + 1 , . . . , r 番目の人の状態を反転する。すなわち、 i= l , l + 1 , . . . , r について、左から i 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

2.制約

N は 1 ≤ N ≤ 10⁵ を満たす整数である。
K は 1 ≤ K ≤ 10⁵ を満たす整数である。
文字列 S の長さは N である。
文字列 S の各文字は 0 または 1 である。

3.入力例

入力

14 2
11101010110011

出力

4.初見の感想

入れ替える範囲を選ぶ基準となるものが、「入れ替え範囲の長さ+入れ替え範囲の左右の1のみからなる文字列の長さ」と複雑
全探索的な手法が有効そう、しかし計算量が爆発してしまう
文字列の真ん中の方を入れ替える方が効率的、なぜなら範囲の両端も長さに含めることができるから

→「0が連なる塊」をK個だけ含む大きな区間で考えられる

5.学びポイント

左端と右端が移動する場合なので、累積和の考え方が使えそう
他にも「尺取り法」で実装するパターンや、真ん中が効率的なことから中央から2部探索とかも別解としてあるようです

6.コードの簡単な解説

まず、入力の値のパースを行う

        string[] line = Console.ReadLine().Split(' ');
        int N = int.Parse(line[0]);
        int K = int.Parse(line[1]);
        char[] input = Console.ReadLine().ToArray();

0から1に切り替わる点を保存するリストなどを準備

        List<int> list = new List<int>();
        int now = 1;
        int ct = 0;
        list.Add(0);
        int ans = 0;

１から０に切り替わる瞬間ではK個入れ替えた時の区間の長さを計算します

        for(int i = 0; i < N; i++)
        {
            if (now == 1 && input[i] == '0')
            {
                now = 0;
                if (ct - K >= 0) { ans = Math.Max(ans, i - list[ct - K]); }
            }

1から0に切り替わる瞬間ではリストに区間の始点として保存

            else if (now == 0 && input[i] == '1')
            {
                now = 1;
                list.Add(i);
                ct++;
            }
        }

文字列が全て1の時、文字列が全て0の時、K=0の時、これらは切り替え点がないので例外処理

        if (now == 1)
        {
            if ((ct - K) >= 0) { ans=Math.Max(ans,N-1-list[ct-K]+1); }
            else { ans = N; }
        }
        else if ((ct - K + 1) >= 0)
        {
            ans = Math.Max(ans, N - 1 - list[ct - K+1] + 1);
        }
        else
        {
            ans = N;
        }
        Console.WriteLine(ans);
    }
}

7.全コード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string[] line = Console.ReadLine().Split(' ');
        int N = int.Parse(line[0]);
        int K = int.Parse(line[1]);
        char[] input = Console.ReadLine().ToArray();
        List<int> list = new List<int>();
        int now = 1;
        int ct = 0;
        list.Add(0);
        int ans = 0;
        for(int i = 0; i < N; i++)
        {
            if (now == 1 && input[i] == '0')
            {
                now = 0;
                if (ct - K >= 0) { ans = Math.Max(ans, i - list[ct - K]); }
            }
            else if (now == 0 && input[i] == '1')
            {
                now = 1;
                list.Add(i);
                ct++;
            }
        }
        if (now == 1)
        {
            if ((ct - K) >= 0) { ans=Math.Max(ans,N-1-list[ct-K]+1); }
            else { ans = N; }
        }
        else if ((ct - K + 1) >= 0)
        {
            ans = Math.Max(ans, N - 1 - list[ct - K+1] + 1);
        }
        else
        {
            ans = N;
        }
        Console.WriteLine(ans);
    }
}

8.最後に

他の解法もできればやってみたいですね！

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 124 D - Handstand