寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C #ALDS1_3_D Areas on the Cross-Section Diagram

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題
 地域の治水対策として、洪水の被害状況をシミュレーションで仮想してみよう。
 図のように 1×1(m2) の区画からなる格子上に表された地域の模式断面図が与えられるので、地域にできる各水たまりの面積を報告してください。
f:id:neguse_atama:20200426165529p:plain
 与えられた地域に対して限りなく雨が降り、地域から溢れ出た水は左右の海に流れ出ると仮定します。
  例えば、図の断面図では、左から面積が 4、2、1、19、9 の水たまりができます。

・入力される値
 模式断面図における斜面を '/' と '\'、平地を '_' で表した文字列が1行に与えられます。
 例えば、図の模式断面図は文字列 \\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\ で与えられます。

・期待する出力
 次の形式で水たまりの面積を出力してください。
f:id:neguse_atama:20200426165639p:plain
 1行目に地域にできる水たまりの総面積を表す整数 A を出力してください。
f:id:neguse_atama:20200426165715p:plain

・条件
 1≤文字列の長さ≤20,000
 ただし、得点の 50 点分は以下の条件を満たす。
 水たまりの数は1つ以下であり (k≤1)、かつ文字列の長さは 100 以下である。

僕が作成、提出したコードは、以下のとおりです。

/*
 ALDS1_3_D Areas on the Cross-Section Diagram
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<stdio.h>
#include<string.h>
#define MAX 20001
typedef struct idx_S{
    int idx;
    int S;
}idx_S;
void Push1(int S[],int x,int *top){
    S[*top]=x;
    (*top)++;
    return;
}
void Push2(idx_S S[],int idx,int s,int *top){
    S[*top].idx=idx;
    S[*top].S=s;
    (*top)++;
    return;
}
int Pop(int S[],int *top){
    (*top)--;
    return S[*top];
}
void Union(idx_S S[],int *top){
    int i;
    for(i=(*top)-1;i>0;i--){
        if(S[i].idx < S[i-1].idx){
            (*top)--;
            S[i-1].idx=S[i].idx;
            S[i-1].S+=S[i].S;
        }
    }
    return;
}
int main(void){
    int i,j,idx,Stack1[MAX];;
    char str[MAX];
    idx_S Stack2[MAX];
    int top1=0,top2=0,sum=0;
    scanf("%s",str);
    for(i=0;i<strlen(str);i++){
        switch(str[i]){
            case '\\':
                Push1(Stack1,i,&top1);
                break;
            case '/' :
                if(top1==0){
                    break;
                }
                idx=Pop(Stack1,&top1);
                sum+=(i-idx);
                Push2(Stack2,idx,i-idx,&top2);
                Union(Stack2,&top2);
                break;
            default:
                break;
        }
    }
    printf("%d\n",sum);
    if(top2==0){
        printf("%d\n",top2);
    }else{
        printf("%d ",top2);
        for(i=0;i<top2-1;i++){
            printf("%d ",Stack2[i].S);
        }
        printf("%d\n",Stack2[top2-1].S);
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_3_D Areas on the Cross-Section Diagram