C++で解く「列を削除してソートされた配列を作る III」― 最小削除列数をLISのDPで求める

問題概要

小文字のアルファベットのみで構成され、長さがすべて同じ N 個の文字列からなる配列 A が与えられます。ここで、削除対象となる列(インデックス)の集合 D を自由に選び、各文字列からその位置の文字をすべて取り除くことを考えます。削除後の最終的な配列では、すべての行が次の条件を満たす必要があります。

A[0] の各文字が A[0][0] <= A[0][1] <= ... <= A[0][n - 1] と非降順に並んでおり、A[1] も同様に A[1][0] <= A[1][1] <= ... <= A[1][n - 1] となっている、という具合です(ここで n は文字列の長さ)。つまり、どの文字列も左から右へ読んだときに文字が辞書順に整列していなければなりません。

このとき、削除する列の数 |D| の最小値を求めるのが本問題です。

たとえば入力が ["cbcdb", "ccbxc"] の場合、出力は 3 になります。

アプローチ:LIS(最長増加部分列)への帰着

この問題は、各列をひとつの要素とみなした最長増加部分列(LIS)の動的計画法として捉えることができます。列 j のあとに列 i を続けて残せるのは、「すべての行 k について A[k][j] <= A[k][i] が成り立つ」場合、かつその場合に限ります。このような互換性のある列をつなげていき、残せる列数の最大値を求めれば、答えは「全体の列数 m − 残す列数の最大値」になります。

解法の手順

• ret := 0 と初期化する
• n := A のサイズ、m := A[0] のサイズとする
• サイズ (m + 1) の配列 lis を定義し、すべて 1 で埋める
• i を 0 から m 未満まで 1 ずつ増やしながら、以下を繰り返す
  • j を 0 から i 未満まで 1 ずつ増やしながら、以下を繰り返す
    • ok := true とする
    • k を 0 から n 未満まで 1 ずつ増やしながら、以下を繰り返す
      • A[k][j] > A[k][i] であれば、ok := false としてループを抜ける
    • ok が真であれば
      • lis[i] := max(lis[j] + 1, lis[i]) と更新する
      • ret := max(ret, lis[i]) と更新する
• ret が 0 の場合は m - 1 を返す(どの 2 列も両立できないため、1 列だけ残すのが最善)
• それ以外の場合は m - ret を返す

C++ 実装例

以下の実装を見ると、理解がより深まります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minDeletionSize(vector<string>& A){
        int ret = 0;
        int n = A.size();
        int m = A[0].size();
        vector<int> lis(m + 1, 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < i; j++) {
                bool ok = true;
                for (int k = 0; k < n; k++) {
                    if (A[k][j] > A[k][i]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    lis[i] = max(lis[j] + 1, lis[i]);
                    ret = max(ret, lis[i]);
                }
            }
        }
        if (ret == 0)
        return m - 1;
        return m - ret;
    }
};
main(){
    Solution ob;
    vector<string> v = {"cbcdb","ccbxc"};
    cout << (ob.minDeletionSize(v));
}

入力

{"cbcdb","ccbxc"}

出力

3

動作のポイント

入力 ["cbcdb", "ccbxc"] の場合、たとえば 1 番目と 3 番目の列(b/d と c/x)は、どちらの行でも非降順になるため同時に残せます。しかし、3 列同時に残せる組み合わせは存在しないため、最大で 2 列を残せます。全体の列数は 5 なので、答えは 5 − 2 = 3 となります。

計算量

調べる列のペア (j, i) は高々 m² 通りであり、それぞれの判定で全行の走査が必要なため、時間計算量は O(n × m²) です。補助配列は lis のみなので、空間計算量は O(m) で抑えられます。