これは面積のマージ部分のロジックが全然思いつかなくてダメでした。。解説を読みつつ書いたものがコレ。
#include <iostream> #include <string> #include <vector> #include <stack> using namespace std; static const char DOWN = '\\'; static const char EVEN = '_'; static const char UP = '/'; struct AREA { int index; int area; }; int main() { string data; cin >> data; stack<int> input; vector<AREA> answers; AREA current = {}; int lastIndex = 0; int total = 0; for (int i = 0; i < data.length(); i++) { switch (data[i]) { case DOWN: input.push(i); break; case EVEN: break; case UP: if (input.empty()) { continue; } lastIndex = input.top(); input.pop(); current.area = i - lastIndex; current.index = lastIndex; total += current.area; while (answers.size() > 0 && answers.back().index > lastIndex) { current.area += answers.back().area; answers.pop_back(); } answers.push_back(current); break; default: break; } } cout << total << endl; cout << answers.size(); for (AREA answer : answers) { cout << " " << answer.area; } cout << endl; return 0; }
面積のマージ条件に、標高の概念を採り入れてみたのですが、入力データと答えに相当する stack/vector を、ひとつの箱でやろうとして混乱してしまい、結局解けませんでした。一通り本書を終えた後にリベンジしたいところです。