D - Ears

はじめに

競技プログラミングみんなのプロコン2019
D - Ears
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

数直線上にすぬけ君がいます。
すぬけ君は L個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。

・座標0未満の点や座標がLより大きい点を通ることはない
・整数座標の点で散歩を開始し、整数座標の点で散歩を終了する
・整数座標の点でのみ、進む方向を変えることができる

すぬけ君は、座標が整数iを用いてi−0.5と表される点を通るたびに、i番目の耳に石を1個入れます。

すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、
各iに対しすぬけ君のi番目の耳にはAi個の石が入っているようにしたいです。

すぬけ君の耳をひとつ選び、石を1個入れる石が1個以上入っているすぬけ君の耳をひとつ選び、石を1個取り出す

すぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。

制約

・1≤L≤2×10^5
・0≤Ai≤10^9(1≤i≤L)
入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

L
A1
:
AL

出力

必要な操作の回数の最小値を出力せよ。

解き方

こちらの解き方を参考にしています。 goo.gl goo.gl goo.gl goo.gl

りんごさんの操作の回数は
すぬけ君がどれだけ入力に沿って歩けるかどうかによって決まるので
まずすぬけ君が歩いて作れる石のパターンを考えます。

すぬけ君が歩いて作れる石のパターンを考えると
次の5パターンがあることが分かります。
・0偶奇偶0
・0偶奇0
・0奇偶0
・0偶0
・0奇0

このパターンをよく見ると
一番上の「0偶奇偶0」が下の4つのパターンを全て含んでいることが分かります。
そのため、ここからは一番上の「0偶奇偶0」だけに着目していきます。

・0偶奇偶0
・0偶奇0
・0奇偶0
・0偶奇偶0
・00

(この時点では少し分かりにくいですが、
dpを回す段になると
なぜ一番上だけでいいのか少し分かり易くなると思います。)

このパターンをもとに動的計画法でこの問題を解いていくのですが
dpの形は以下のようになります。

dp[Ai,すぬけ君が歩いて作れる石のパターンの区分け]=ここまでで、りんごさんが操作を行う最小回数


「すぬけ君が歩いて作れる石のパターンの区分け」は、先程の「0偶奇偶0」です。
動的計画法ができるように、
これらの区分けに以下のように番号をふっておきます。

0→0(領域0)
偶→1(領域1)
奇→2(領域2)
偶→3(領域3)
0→4(領域4)


これらをもとに
例えば、dp[0,0]は
「「A0」を「領域0」としたときの、りんごさんが操作を行う最小回数」という意味になります。

コードを見ながら具体的に値を入れてみていきます。

✩準備

まず動的計画法を始めるために配列を用意します。

//A1~ALを格納する配列
var A = new List<long>();
for (int i = 0; i < L; ++i)
{
    A.Add(Int64.Parse(Console.ReadLine()));
}
//LはAi
//5は領域0~領域4
var dp = new long[L, 5];

Lの部分をA[0]から順番に埋めていきます。

✩A[0]


まず領域0は「0偶奇偶0」の一番初めの「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[0]」となります。
(すぬけ君が歩かないので、りんごさんがA[0]回石を入れる操作を繰り返す)

dp[0,0]=A[0];


次に領域1は「0偶奇偶0」の一番初めの「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[0]==0?2:A[0]%2」になります。
(A[0]が0なら2回、偶数なら0回、奇数なら1回)

dp[0,1]=A[0]==0?2:A0%2;


次に領域2について見ていきます。
ここは、「0偶奇偶0」の「奇」の部分です。
ここはすぬけ君が「奇数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[0]==0?1:(A[0]+1)%2」になります。
(A[0]が0なら1回、偶数なら1回、奇数なら0回)

dp[0,2]=A[0]==0?1:(A[0]+1)%2;


次に領域3について見ていきます。
ここは、「0偶奇偶0」の二番目に出てくる「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[0]==0?2:A[0]%2」になります。
(A[0]が0なら2回、偶数なら0回、奇数なら1回)

dp[0,3]=A[0]==0?2:A[0]%2;


領域4は「0偶奇偶0」の二番目に出てくる「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[0]」となります。
(すぬけ君が歩かないので、りんごさんがA[0]回石を入れる操作を繰り返す)

dp[0,4]=A[0];


✩A[1]

次に、A[1]について見ていきます。

まず領域0は「0偶奇偶0」の一番初めの「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[1]」となります。
(すぬけ君が歩かないので、りんごさんがA[1]回石を入れる操作を繰り返す)

ただし、A[1]の前にはA[0]があり
A[1]が領域0になるということは
A[0]も「領域0」であることを示すので
A[0]の値を足しておきます。

dp[0,0]=A[1]+dp[0,0]/*(=A[0])*/;


次に領域1は「0偶奇偶0」の一番初めの「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[1]==0?2:A[1]%2」になります。
(A[1]が0なら2回、偶数なら0回、奇数なら1回)

ただし、A[1]の前にはA[0]があり、ここで2パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
①②どちらを取るかは、りんごさんの操作を最小にしたいので
値の小さいほうを取ります。

仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,A[0]が領域1のパターン);
として、値が小さいほうを「A[1]==0?2:A[1]%2」に足します。

var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,dp[0,1]/*(=A[0]が領域1のパターン)*/);
dp[1,1]=A[1]==0?2:A[1]%2+value;


次に領域2について見ていきます。
ここは、「0偶奇偶0」の「奇」の部分です。
ここはすぬけ君が「奇数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[1]==0?1:(A[1]+1)%2」になります。
(A[1]が0なら1回、偶数なら1回、奇数なら0回)

ただし、A[1]の前にはA[0]があり、ここで3パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
③A[0]が領域2のパターン
①②③どれを取るかは、りんごさんの操作を最小にしたいので
値の小さいものを取ります。

仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,
Math.Min(A[0]が領域1のパターン,A[0]が領域2のパターン));
として、値が小さいものを「A[0]==0?1:(A[0]+1)%2」に足します。

var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,
          Math.Min(dp[0,1]/*(=A[0]が領域1のパターン)*/,dp[0,2]/*(=A[0]が領域2のパターン)*/));
dp[1,2]=A[1]==0?1:(A[1]+1)%2;


次に領域3は「0偶奇偶0」の二番目に出てくるの「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[1]==0?2:A[1]%2」になります。
(A[1]が0なら2回、偶数なら0回、奇数なら1回)

ただし、A[1]の前にはA[0]があり、ここで4パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
③A[0]が領域2のパターン
④A[0]が領域3のパターン
①②③④どれを取るかは、りんごさんの操作を最小にしたいので
値の小さいものを取ります。

仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,
Math.Min(A[0]が領域1のパターン,
Math.Min(A[0]が領域2のパターン,A[0]が領域3のパターン)));
として、値が小さいものを「A[1]==0?2:A[1]%2」に足します。

var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,
          Math.Min(dp[0,1]/*(=A[0]が領域1のパターン)*/,
          Math.Min(dp[0,2]/*(=A[0]が領域2のパターン)*/,dp[0,3]/*(=A[0]が領域3のパターン)*/)));
dp[1,1]=A[1]==0?2:A[1]%2+value;


領域4は「0偶奇偶0」の二番目に出てくるの「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[1]」となります。
(すぬけ君が歩かないので、りんごさんがA[1]回石を入れる操作を繰り返す)

ただし、A[1]の前にはA[0]があり、ここで5パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
③A[0]が領域2のパターン
④A[0]が領域3のパターン
⑤A[0]が領域4のパターン
①②③④⑤どれを取るかは、りんごさんの操作を最小にしたいので
値の小さいものを取ります。

仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,
Math.Min(A[0]が領域1のパターン,
Math.Min(A[0]が領域2のパターン,
Math.Min(A[0]が領域3のパターン,A[0]が領域4のパターン))));
として、値が小さいものを「A[1]」に足します。

var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,
          Math.Min(dp[0,1]/*(=A[0]が領域1のパターン)*/,
          Math.Min(dp[0,2]/*(=A[0]が領域2のパターン)*/,
          Math.Min(dp[0,3]/*(=A[0]が領域3のパターン)*/,dp[0,4]/*(=A[0]が領域4のパターン)*/))));
dp[1,4]=A[1]+value;



あとのA[2]以降はこの操作を繰り返し、
dp[L-1,4]までいけば動的計画法はおしまいです。

✩最も小さい値を出す

最後に
dp[L-1,0](1番初めの0で終わるパターン),
dp[L-1,1](1番初めの偶で終わるパターン),
dp[L-1,2](奇で終わるパターン),
dp[L-1,3](二番目に出てくる偶で終わるパターン),
dp[L-1,4](二番目に出てくる0で終わるパターン)の中で
最も最小の値を出せばそれが答えになります。

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var L = Int64.Parse(Console.ReadLine());
        var A = new List<long>();
        for (int i = 0; i < L; ++i)
        {
            A.Add(Int64.Parse(Console.ReadLine()));
        }
        //動的計画法
        var dp = new long[L, 5];
        for (int i = 0; i < L; ++i)
        {
            var num = A[i] % 2;
            //偶数領域のコスト
            var even = A[i] == 0 ? 2 : num == 0 ? 0 : 1;
            //奇数領域のコスト
            var odd = A[i] == 0 ? 1 : num == 0 ? 1 : 0;

            //領域0(0)
            //自分の前の値すべてが領域0に属していたときのコスト
            var value = GetValue(dp, i, 0);
            //自分もさらに領域0に属すときのコスト
            dp[i, 0] = A[i] + value;

            //領域1(偶)
            //自分の前までの値が、領域0と領域1どちらかに属したときの最小コスト
            value = GetValue(dp, i, 1, value);
            //自分が領域1に属すときのコスト
            dp[i, 1] = even + value;

            //領域2(奇)
            //自分の前までの値が、領域0、領域1、領域2のどれかに属したときの最小コスト
            value = GetValue(dp, i, 2, value);
            //自分が領域2に属すときのコスト
            dp[i, 2] = odd + value;

            //領域3(偶)
            //自分の前までの値が、領域0、領域1、領域2どれかに属したときの最小コスト
            value = GetValue(dp, i, 3, value);
            //自分が領域3に属すときのコスト
            dp[i, 3] = even + value;

            //領域4(0)
            //自分の前までの値が、領域0、領域1、領域2、領域3どれかに属したときの最小コスト
            value = GetValue(dp, i, 4, value);
            //自分が領域4に属すときのコスト
            dp[i, 4] = A[i] + value;
        }
        //一番小さいパターンを出す
        var ans = Math.Min(dp[L - 1, 0],
                  Math.Min(dp[L - 1, 1],
                  Math.Min(dp[L - 1, 2],
                  Math.Min(dp[L - 1, 3], dp[L - 1, 4]))));

        Console.WriteLine(ans);
    }
    
    //value(自分の手前までの値の最小コスト)を返す
    static long GetValue(long[,] dp, long num, int section, long value = long.MaxValue)
    {
        //A[0]は自分の前に値がないので、前の値は考えない
        if (num == 0) return 0;
        else
        {
            switch (section)
            {
                //領域0なので、自分の前の値全てが領域0に属していたときのコスト
                case 0: return dp[num - 1, section];
                //自分の前の値の、領域ぶんの可能性の中の、最小コストを返す
                default: return Math.Min(value, dp[num - 1, section]);
            }
        }
    }
}