【ABC361】AtCoder ABC361 Problem Cを解く

AtCoder Beginning Contest 361、今回は不参加でした。ですがコンテスト終了後に当該の問題を解いたので、その方法論を記載して見ようと思います。

AtCoder ABC361 problem C

問題内容は以下からご確認下さい。

C - Make Them Narrow

提出１回目（WA）

標準入力より与えられた配列から指定された数の要素を削除し、削除後の配列内の最大値と最小値の差が最も低くなるような値を出力する、という問題になります。

まず削除後の配列内の最大値と最小値の差が最も低くなるような値を出力する事の意味を考えると、要素を削除する時の１回分の操作の基本的な要件として、

• 削除する要素はその時点での配列の最小値か最大値

になります。

これは図にすると明確で、例えば５要素ある配列から１要素を抜いた時の、配列内の最大値と最小値の差を求めようと考えた場合、配列をソートした時の最小値と最大値以外の要素を削除するより、最小値か最大値を削除した方が最適な結果が得られるという事が分かります。

ソート済の配列の端以外の数値を削除しても、最適な結果は得られない

では最大値と最小値のどちらを削除するかという点についてですが、最小値と最大値を削除した時の値の変化を評価し、大きい方を削除する処理をK回分行えば良いのかなと考えました。

以上の事から、配列$${A}$$をソートした上で、配列$${A}$$の隣り合う要素の値の差を新た配列$${B}$$に格納する事にしました。配列は昇順ソートしているので、配列$${B}$$は全て正の値になります。配列$${B}$$の要素の端同士の値を確認し、その要素の大きい方を中央方向に進める、という操作を$${K}$$回行う事で、適切な配列が完成すると予想を立てました。

以上の方針で作成したものが、以下のコードになります。

def function():
    # 標準入力
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()

    # 配列Aの差配列Bを生成
    B = []
    A_bef = A[0]
    for i in range(1,N):
        B.append(A[i]-A_bef)
        A_bef = A[i]
    
    # 差配列の両端を比べ、大きい方を中央方向に1つ進める
    left_key = 0
    right_key = N-1
    for _ in range(K):
        if(B[left_key]>=B[right_key-1]):
            left_key += 1
        else:
            right_key -= 1
    
    # 出力
    print(A[right_key]-A[left_key])
    return


if __name__ == "__main__":
    function()

本コードの提出結果はWAでした。不適切な答えだったということです。

何故上記回答が不適切だったか

何故上記回答が不適切かの理由は単純で、各操作において目の前の１手分の最適化しか判断出来ない為です。例えば配列内に５要素ある状態で、そこから２つの要素を削除して今回の題意に沿った回答を出す場合、下の様な図の状態であれば青の矢印になってしまい、適切な回答（このケースだと赤の矢印）を導き出す事が出来ません。

１回分の最適操作を複数回行う場合、その処理の最適が全体での最適とは限らない

上図の様な例であれば要素間の値の差が最も大きいのは要素2と要素3の間の10000という値であり、これらの要素差が含まれない様に削除する事が目的を達成する為の大きなポイントです。これは要素1と要素2を削除した場合（赤矢印）に相当します。
しかしながら今の計算方法であれば、要素1と要素2の要素間の値が著しく小さいので、図で言うと右側から要素を削除してしまう結果（青矢印）になってしまいます。この方針は失敗でした。

提出２回目（AC）

1回目の提出の手順では失敗しましたが、そもそものプランが間違っていたことが分かりました。評価する対象は、各処理毎の最大値と最小値の差で評価するのではなく、最終的に完成した以下図において各矢印での最大値と最小値の差を評価すべきでした。

最終的に、最大値／最小値の差が一番小さくなる矢印を探索すべき

先の調査において、全ての操作において配列の端以外の要素を削除すべきでは無い、という事は事実なので、最適な配列の組み合わせは上図に示すような矢印となり、その長さは$${N-K}$$、組み合わせは$${K+1}$$通りになります。矢印の長さ、つまり最終的な配列の長さは常に一定なので、配列$${A}$$を二種類のインデックスで走査し、その値の差の最小値を求めれば良いのです。

最終的なコードは以下となります。

def function():
    # 標準入力
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()

    # 初期区間設定
    ans = 10**9
    left_key = 0
    right_key = N-K-1

    # 区間を右に１個ずつずらす
    while(right_key < N):
        if(A[right_key]-A[left_key] < ans):
            ans = A[right_key]-A[left_key]
        left_key += 1
        right_key += 1
    
    # 出力
    print(ans)
    return

if __name__ == "__main__":
    function()

このコードは無事ACとなりました。後で読みましたが、概ね公式解説の考え方もこの通りでした。

おわりに

私は、自分で解いた際に上手く行かなかった問題を主に記事にしていますが、その際には失敗したコードや考え方も併せて掲載しています。
もしかしたら他の何かに役に立つかもしれないし、失敗した事を無かった事にするのは学習としてはもったいないな、と感じます。間違えたとしても、それは取り返しの付くことで、次は気を付けたいという気持ちで、適切で無かった部分も含めて掲載しています。
問題の解説としては最速で適切な考え方が載っていない事で、邪魔な要素かも知れません。ただ、自身のメモも兼ねているので、ご容赦下さい。