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; }