Triangular Matrix [CSAcademy #59 C]

https://csacademy.com/contest/round-59/task/triangular-matrix/

文字が書かれた三角行列がある。
i行はi列までしかない。
最初(0,0)からスタートする。
ここからN-1回、下が右下に遷移する。
これでできるパスを繋げてできる文字列のうち辞書順最小のものを答えよ。

解法

dpっぽいことをする。
パスが来るかもしれないx座標を保存する集合vを用意する。
　
最初は(0,0)なので、これを答えに追加しておく。
そして、最初は座標x=0にしかいないので、vに0を追加する。
　
ある行から文字を選ぶ時にvの中にある座標から1つ選んで遷移することを考える。
この時に、xは0～y-1で選ぶことができるが、vの中にある座標から遷移可能なものだけ選べる。
あと、選ぶ場合は辞書順最小にするため、一番小さい文字を採用する。
一番小さい文字が複数ある場合はどれも選ぶ可能性があるため、次に文字を選ぶ候補として全て集合vvとして保存しておく。
これを続けて貪欲に辞書順最小を達成していけばいい。

int N;
string S[3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N; rep(i, 0, N) cin >> S[i];

    string ans = S[0];
    set<int> v; v.insert(0);
    rep(y, 1, N) {
        set<int> vv;
        char c = 125;

        fore(x, v) {
            rep(d, 0, 2) {
                int xx = x + d;

                if (S[y][xx] < c) {
                    c = S[y][xx];
                    vv.clear();
                    vv.insert(xx);
                }
                else if (S[y][xx] == c) vv.insert(xx);
            }
        }

        swap(v, vv);
        ans += c;
    }
    cout << ans << endl;
}