AtCoder Grand Contest 030 F: Permutation and Minimum

問題概要

日本語があるので原文参照 → F - Permutation and Minimum

解説

と の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態としてありえるものは以下の 3 通りである。

• 2 つとも値が確定している (入力の段階で の値がどうなるか分かる)
• 1 つだけ値が確定している
• なにも値が確定していない

今回はブロック内の値の最小値が数列 の値となるので、値の大きいものから確定させていく (値が 2 個未満入っているブロックに対して値を追加) ことを考える。動的計画法で処理しよう。

ここで、はじめに与えられる数列 で登場しなかった要素 それぞれについて、最後に生成される に登場するかどうかで場合分けして考える。

• で登場しない場合
  • は、 で登場しなかった で登場した 未満の要素とペアを組むか、 で登場してなおかつ 1 つだけ値が確定しているブロックに属している 未満の要素とペアを組む可能性がある
• で登場する場合
  • は、 で登場しなかった で登場しない を超える要素とペアを組むか、 で登場してなおかつ 1 つだけ値が確定しているブロックに属している を超える要素とペアを組む可能性がある

で登場しなかった要素が で登場するかしないかを分けて考えることで、

番目の要素まで見て、 で登場せずに でも登場しない要素でペアになっていないものが 個、 で登場せずに で登場する要素でペアになっていないものが 個あるときの場合の数

という DP を考えることができる。

下で書いたソースコードでは、 で登場しない要素同士のペアの順序を考慮していないため、最後に階乗で掛けている。

ソースコード

using mint = ModInt<MOD>;
mint dp[2][310][310];
signed main() {
    int N, M; cin >> N; M = N; N *= 2;
    int both_neg = 0;
    
    vector<int> tp(N + 1);
    for(int i=0; i<N/2; i++) {
        int a, b; cin >> a >> b;
        if(a > b) swap(a, b);

        if(b == -1) both_neg++;
        else if(a == -1 and b != -1) tp[b] = 1;
        else tp[a] = tp[b] = 2;
    }

    dp[0][0][0] = mint(1);
    for(int i=N; i>=1; i--) {
        int cur = i % 2, nxt = 1 - cur;
        for(int j=0; j<=M; j++) {
            for(int k=0; k<=M; k++) {
                if(dp[cur][j][k] == mint(0)) continue;
                if(tp[i] == 2) {
                    dp[nxt][j][k] += dp[cur][j][k];
                }
                // k 増えるのここだけ → 3 次元目は (-1, 値入っているもの) のペア
                if(tp[i] == 1) {
                    dp[nxt][j][k+1] += dp[cur][j][k];
                    if(j) dp[nxt][j-1][k] += dp[cur][j][k];
                }
                // j 増えるのここだけ → 2 次元目は (-1, -1) のペア 
                if(tp[i] == 0) {
                    dp[nxt][j+1][k] += dp[cur][j][k];
                    if(j) dp[nxt][j-1][k] += dp[cur][j][k];
                    if(k) dp[nxt][j][k-1] += dp[cur][j][k] * mint(k);
                }
                dp[cur][j][k] = mint(0);
            }
        }
    }

    mint ans = dp[0][0][0];
    while(both_neg) ans *= mint(both_neg--);
    cout << ans << endl;
    return 0;
}

説明がかなり難しいですね・・・。これ自力で解きたかったなぁ

Codeforces Round #581 Div. 2 D: Kirk and a Binary String

問題概要

原文 → Problem - D2 - Codeforces

0 と 1 のみからなる長さ の文字列 が与えられる。 の文字を、以下の条件が満たされた上で変更することを考える。

• 全ての に対して、 の 文字目から 文字目までのみからできる最長単調非減少列の大きさが元の文字列と変わらない

変更後の文字列であって、0 を最も多く含むものを求めよ。

解説

まず、"10" という文字列について変更不可能であることがわかる。ここから考察を進めていこう。

"10" という文字列は 1 と 0 を 1 文字ずつ含んでいるが、"10" を通過する直前の部分列が最後にどの文字を使ったかによって場合分けする。

• 部分列が最後に "0" を使用していた場合、つまり "....0xxx10" (x は選択していない文字) のような状況であった場合、それに "10" の 0 を続けるか 1 を続けるか 2 通りの選択ができる
• 部分列が最後に "1" を使用していた場合、つまり "...1xxx10" のような状況であった場合、それに "10" の 1 を続けることができる

最後に使用した文字に続きうる文字のうち、どれか 1 つを "10" から使用することができることがわかるであろう。言い換えれば、「"10" を通過するときは必ずどれか 1 文字をその中から使っていて、適切に選択すれば最長単調非減少列の大きさに影響しない」ということにもなるため、このようなパターンは元々なかったものとして (削除して) 構わない。

文字列から "10" というパターンを左から順に消していくと、最終的にできる文字列は "0000...0111.....1" のように左が 0 で右が 1 となる文字列である。この文字列に関しては全て "0" に変更してしまっても最長単調非減少列の大きさは変わらない。

ゆえに、stack などを用いて高速に解くことができる。

ソースコード

int main() {
    string s; cin >> s;

    vector<bool> checked(s.size());
    stack< pair<char, int> > st;
    for(size_t i=0; i<s.size(); i++) {
        if(st.empty() or st.top().first == s[i] or st.top().first == '0') {
            st.emplace(s[i], i);
        }
        else {
            checked[i] = checked[st.top().second] = true;
            st.pop();
        }
    }

    for(size_t i=0; i<s.size(); i++) {
        if(!checked[i]) s[i] = '0';
    }
    cout << s << endl;
    return 0;
}

"10" が変わらないのは思いついたけど、その後が全然ダメだった。難しい・・・

LeetCode Weekly Contest 149: Swap For Longest Repeated Character Substring

本番に書いたコードの実装が悪すぎたので書き直し

問題概要

原文 → Loading...

文字列 が与えられる。この文字列に対して、あるふたつの文字を選んで swap することが一度だけできる。同じアルファベットを最大で何連続させられるか答えよ。

解説

まずランレングス圧縮をする。あとはそれぞれの要素に対して次に示すものを計算して max をとればよい。

• swap する前の長さ
• swap する前の長さ + 1 (ただし、この結果が文字の登場回数より多くなってはいけない)
• aa...a b aa...a のように真ん中が 1 文字だけ異なる場合を考慮するために、(左の要素の長さ) + (右の要素の長さ) + 1 を計算する。ただし、この結果が文字の登場回数より多くなってはいけない。

ソースコード

class Solution {
public:
    int maxRepOpt1(string text) {
        vector< pair<char, int> > rle;
        vector<int> cnt(26);
        
        for(auto c : text) {
            if(rle.empty() or rle.back().first != c) rle.emplace_back(c, 1);
            else rle.back().second++;
            cnt[c - 'a']++;
        }
        
        int N = rle.size(), ans = 0;
        for(int i=0; i<N; i++) {
            int id = rle[i].first - 'a';
            ans = max(ans, min(cnt[id], rle[i].second + 1));
        }
        for(int i=1; i+1<N; i++) {
            if(rle[i-1].first == rle[i+1].first and rle[i].second == 1) {
                int id = rle[i-1].first - 'a';
                ans = max(ans, min(cnt[id], rle[i-1].second + rle[i+1].second + 1));
            }
        }
        return ans;
    }
};

これくらい簡潔な実装を思いつきたかったなあ。