CSAcademy Triangular Matrix
<問題>
つの文字列が与えられます。番目の文字列の長さはです。
これらつの文字からひとつずつ文字を選び、辞書順最小の長さの文字列を答えなさい。
ただし、番目の文字列の番目の文字を選んだ場合、
次の番目の文字列からは番目の文字しか選べません。
<解説>
答える文字列はどう選んでも長さなので、
先頭から順にアルファベット順に小さい文字を選んでいけばよいです。
ただし、候補がいくつかある場合には、その先の分岐を考える必要があります。
ただ、次の文字列の候補だけを持っておけばよいので、すべてを探索する必要はありません。
(何番目の文字を選んでも、辞書順最小のアルファベットであることは変わりません)
<コード>
int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; string s; vi next,tmp; next.pb(0); rep(i, n) { cin >> s; char ans = 'z'; for(auto j : next) { ans = min(ans, s[j]); } cout << ans; for( auto j : next) { if (s[j] == ans) { tmp.pb(j + 1); tmp.pb(j); } } next = tmp; tmp.clear(); UNIQ(next); } cout << endl; return 0; }
<感想>
週末まではCCENT!!
また日曜頑張ります。