mayoko’s diary

プロコンとかいろいろ。

GCJ Round3 Problem A. Teaching Assistant

せっかく Round3 にまで進むことができたので参加してみたんですが, 上位陣のレベルの高さを実感してしまい場違い感を感じました…ついていけるようになりたいですね。

問題

Dashboard - Round 3 2016 - Google Code Jam

長さ 2n の C か J のみが書かれた文字列 s が与えられる。同様に長さ 2n の valid なかっこ列を考える。valid なかっこ列について,

  • 対応する ( と ) が s で同じ文字なら +10
  • 対応する ( と ) が s で別の文字なら +5

というように評価する。valid なかっこ列のうち, 評価値が最も高いものの値を求めよ。

解法

例えば JCJJCCCJJJCJ という文字列を考えてみます。隣り合っている文字が同じ場合, 明らかにそれらの文字をペアにするのが得であるので, この文字列から隣り合った同じ文字を取り除くと, JCCJCJ となります。また隣り合っている文字で同じものがあるので取り除くと, JJCJ -> CJ となり, これで隣り合った同じ文字はなくなりました。今までに消したペアは 5 ペアあり, 合計で 6 ペア作るので, 答えは 5*10+ 1*5 です。

これを高速に処理すれば良いですが, この処理は「同じ隣り合った文字を見つけたら貪欲に消す」という方針で良いので, stack で計算できます。

void solve() {
    string s;
    cin >> s;
    stack<int> st;
    int ans = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (!st.empty() && s[st.top()] == s[i]) {
            ans += 10;
            st.pop();
        } else {
            st.push(i);
        }
    }
    ans += st.size()*5/2;
    cout << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        solve();
    }
    return 0;
}