ICPC 国内予選2015C ICPC 計算機 AOJ1602

シミュレーションやるだけ

. （ドット）の多いところから計算すればよい

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int d[100][100];
int sum[100];

int main(){
    int n;

    while(1){

        cin >> n;
        if(n == 0)break;
        char tmp[100];
        for(int i = 0;i < n;i++){
            cin >> tmp;
            sum[i] = 0;
            for(int j = 0;j < strlen(tmp);j++){
                if(tmp[j] == '.'){
                    d[i][j] = -1;
                    sum[i] = j+1;
                }else if(tmp[j] == '+'){
                    d[i][j] = -2;
                    break;
                }else if(tmp[j] == '*'){
                    d[i][j] = -3;
                    break;
                }else{
                    d[i][j] = tmp[j] - '0';
                }
            }
        }
        while(n != 1){
            /*
            cout << "+++++" << endl;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < sum[i]+1;j++){
                    cout << d[i][j] ;
                }
                cout << endl;
            }
*/

            int maxlen = 0,o = -1;
            for(int i = 0;i < n;i++){
                if(sum[i] > maxlen){
                    o = i;
                    maxlen = sum[i];
                }
            }
            int count = 1,ans = d[o][maxlen];
            for(int i = o+1;i < n;i++){
                if(maxlen == sum[i]){
                    count++;
                    if(d[o-1][maxlen-1] == -2){
                        ans += d[i][maxlen];
                    }else{
                        ans *= d[i][maxlen];
                    }
                }else{
                    break;
                }
            }
            d[o-1][maxlen-1] = ans;
            for(int i = o + count;i < n;i++){
                for(int j = 0;j <= sum[i];j++){
                    d[i-count][j] = d[i][j];
                }
            }
            for(int i = o+count;i < n;i++) sum[i-count] = sum[i];
            n -= count;
        }
        cout << d[0][0] << endl;


    }
}