パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 354）G問題メモ

パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 354）

G - Select Strings

問題

$N$ 個の文字列 $S_i$ とスコア $A_i$ が与えられる
$1$ 以上 $N$ 以下の整数からなる「よい集合」を、以下で定義する
- 集合に含まれるどの2つの要素 $(i,j)$ に対しても、$S_i$ は $S_j$ の部分文字列でない
「よい集合」$T$ に対する $\displaystyle \sum_{i \in T}A_i$ としてあり得る最大値を求めよ
$1 \le N \le 100$
$\sum |S_i| \le 5000$
$1 \le A_i \le 10^9$

解法1

やりたいことは、同時に選べない $i,j$ 間に辺を張ったグラフにおける重み付き最大独立集合だが、一般的な解法はNP困難（NP完全?）とされている。

今回は、辺を有向（含む方→含まれる方）にした場合、「DAGである」「$i→j,j→k$ に辺があれば、$i→k$ にも必ず辺がある（推移律）」という性質がある。
この場合は、Dilworthの定理を使えば解ける。

※ $S_i$ に全く同じ文字列が含まれる場合はDAGとは限らなくなるが、 $S_i$ が同じ同士では $A_i$ が最大のものを残して削除するなどの前処理をすればよい。

Dilworthの定理によると、

推移律を満たすDAG¹⁾では、「最小パス被覆＝最大独立集合」である
- 最小パス被覆: 全頂点がいずれかのパスに含まれるよう、グラフをパスの集合に分割する場合、その最小個数
- 最大独立集合: どの2頂点も辺で隣接しないような頂点集合の選び方で、個数最大のもの

最大独立集合はNP完全だが、最小パス被覆は二部グラフの最大マッチング問題に変換できて解ける。

グラフをパスに分割するとは、「各頂点の入次数・出次数が1を超えないように、辺を選ぶ」といえる
辺を $k$ 個選んだ場合、どのような選び方であろうとパスの本数は $N-k$ 本である
よって、「パスの個数の最小化＝選ぶ辺の個数の最大化」と言い換えられる
出る側の頂点を左、入る側の頂点を右に置いた二部マッチングで解ける

今回の場合は単なる最大独立集合ではなく、$A_i$ による重み付きだが、これは二部マッチングを最大流で解くときの辺の容量を調整すればよい。

始点 $S$、終点 $T$、出る側頂点 $1,...,N$、入る側頂点 $1',...,N'$ の $2N+2$ 個の頂点を用意
$S→i$ に容量 $A_i$ の辺
$i'→T$ に容量 $A_{i'}$ の辺
$S_i$ が $S_j$ を含んでいれば $i→j'$ に容量 $\infty$ の辺

これで、$\sum A_i - \rm{MaxFlow}(S→T)$ が答えとなる。

Python3

from atcoder import maxflow


def remove_same_string(n, sss, aaa):
    # 縮約 同じ文字列は最善のもののみ残す
    same_string = {}
    available_index = set(range(n))
    for i, s in enumerate(sss):
        if s not in same_string:
            same_string[s] = i
            continue
        j = same_string[s]
        if aaa[i] > aaa[j]:
            available_index.remove(j)
            same_string[s] = i
        else:
            available_index.remove(i)
    available_index = sorted(available_index)
    n = len(available_index)
    sss = [sss[i] for i in available_index]
    aaa = [aaa[i] for i in available_index]

    # ついでに s が短い順にソート
    order = sorted(enumerate(sss), key=lambda s: len(s[1]))
    sss = [s for i, s in order]
    aaa = [aaa[i] for i, s in order]

    return n, sss, aaa


def solve(n, sss, aaa):
    n, sss, aaa = remove_same_string(n, sss, aaa)

    mf = maxflow.MFGraph(n * 2 + 2)
    s = n * 2
    t = s + 1
    INF = 1 << 60

    for i in range(n):
        s1 = sss[i]
        for j in range(i + 1, n):
            s2 = sss[j]
            if s1 in s2:
                mf.add_edge(i, j + n, INF)
        mf.add_edge(s, i, aaa[i])
        mf.add_edge(i + n, t, aaa[i])

    ans = sum(aaa)
    ans -= mf.flow(s, t)

    return ans


n = int(input())
sss = [input() for _ in range(n)]
aaa = list(map(int, input().split()))
ans = solve(n, sss, aaa)
print(ans)

解法2

0-1整数計画問題として扱える。

目的: $\displaystyle \sum_{i}A_iX_i$ を最大化するように、$X=(X_1,...,X_N)$ を決める
制約:
- $X_i$ は0または1
- 「$X_i$ と $X_j$ が同時に1であってはいけない」という制約が何個かある

こういった問題はソルバを使える。

AtCoderのPythonで使えるソルバライブラリには、PuLP、OR-Tools、scipy.optimize、z3-solver などがある。

PuLPで解かせてみたところ、ほとんどは高速に解けるが、2ケースでTLEとなった。
（提出一覧には一部通っている提出もあるが、記事執筆時点では、PuLPで通している提出は時間のかかるケースを例外処理していたりする）

一方、OR-Toolsでは、特に例外処理せずとも全てのケースを高速に（200ms以内で）通すことができた。

また、scipyで通している例も見られた。

具体的に中身で何をやってるか不勉強にして分かっていないのだが、ソルバによっても得手不得手があるらしい。
AtCoderのPuLPで使えるソルバはCBC（COIN-OR Brand-and-Cut）のみだが、今回はこれで時間がかかってしまうテストケースが含まれていたのかもしれない。

（生成AI使って競プロするのがどうのこうのという話がたまに話題になるが、中身分かってなくても汎用的に使えてしまうという意味ではソルバも大概だな） ²⁾

Python3

from ortools.sat.python import cp_model


def solve(n, sss, aaa):
    model = cp_model.CpModel()

    xxx = [model.NewBoolVar(str(i)) for i in range(n)]
    for i in range(n):
        s1 = sss[i]
        for j in range(i + 1, n):
            s2 = sss[j]
            if s1 in s2 or s2 in s1:
                model.AddAtMostOne([xxx[i], xxx[j]])

    model.Maximize(sum(x * a for x, a in zip(xxx, aaa)))

    solver = cp_model.CpSolver()
    solver.Solve(model)
    ans = int(solver.ObjectiveValue())
    return ans


n = int(input())
sss = [input() for _ in range(n)]
aaa = list(map(int, input().split()))
ans = solve(n, sss, aaa)
print(ans)

¹⁾

本当はもう少し抽象的な条件らしい。上記リンク先参照

²⁾

ただし、現状どのソルバもfloat型で演算されるので、53bit程度で表現できない値が答えになり得るようにすれば割と簡単にシャットアウトできる?

目次

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 354）G問題メモ

G - Select Strings

問題

解法1

解法2

パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 354）G問題メモ