AOJ : 2365 - Memory Leak
問題概要
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2365
立命合宿のDay3で出題しました.
問題文長くてごめんなさい.
解法
構文解析やるだけです.
問題文中に, 注意すべき制約がいっぱい書いてあるので注意しましょう.
(ジャッジ側で, もっと見やすいようにまとめておけばよかったです)
プログラム
ジャッジ解です.
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> using namespace std; int n, idx; //メモリ上限, 文字列の添字 int max_ptr, mem; //使用済みのアドレス値+1, 現在確保しているメモリのサイズ char s[1000002]; //文字列 int var[256]; //各変数に入っている値を格納 bool mem_flg[1000002]; //メモリ上に確保した領域が残っているかどうか int mem_size[1000002]; //確保した領域のサイズ int Number(); int Expr(); int Assign(); int Malloc(); bool Free(); int Clone(); bool Line(); int Number(){ int res = 0; while(isdigit(s[idx])){ res *= 10; res += s[idx] - '0'; idx++; } return res; } int Malloc(){ idx += 7; //"malloc("の文字数 int tmp = Number(); idx++; //")"の文字数 if(n < mem + tmp){ return 0; } mem_flg[max_ptr] = true; mem_size[max_ptr] = tmp; mem += tmp; max_ptr++; return max_ptr - 1; } int Assign(){ int alpha = s[idx]; idx += 2; //変数名と"="の文字数 int ptr = Expr(); return var[alpha] = ptr; } int Clone(){ idx += 6; //"clone("の文字数 int ptr = Expr(); if(ptr == 0){ return 0; } if(ptr == -2 || ptr == -1 || !mem_flg[ptr]){ return -2; } idx++; //")"の文字数 if(n < mem + mem_size[ptr]){ return 0; } mem_flg[max_ptr] = true; mem_size[max_ptr] = mem_size[ptr]; mem += mem_size[ptr]; max_ptr++; return max_ptr - 1; } int Expr(){ if(s[idx] == '('){ idx++; //"("の文字数 int tmp = Expr(); idx++; //")"の文字数 return tmp; } else if(s[idx] == 'N' && s[idx + 1] == 'U'){ idx += 4; //"NULL"の文字数 return 0; } else if(s[idx + 1] == '='){ return Assign(); } else if(s[idx] == 'm'){ return Malloc(); } else if(s[idx] == 'c'){ return Clone(); } else{ return var[(int)s[idx++]]; } } bool Free(){ idx += 5; //"free("の文字数 int ptr = Expr(); if(ptr == -2 || ptr == -1){ return false; } idx++; //")"の文字数 if(ptr == 0){ //NULLの場合, 無視 return true; } else{ if(!mem_flg[ptr]){ //すでに確保領域でないならError return false; } mem -= mem_size[ptr]; mem_flg[ptr] = false; mem_size[ptr] = 0; return true; } } bool Line(){ if(s[idx] == 'f'){ return Free(); } else{ int tmp = Expr(); if(tmp == -2){ return false; } return true; } } int main(){ bool error_flg = false; mem = 0; max_ptr = 1; memset(var, -1, sizeof(var)); memset(mem_flg, 0, sizeof(mem_flg)); memset(mem_size, 0, sizeof(mem_size)); scanf("%d", &n); while(scanf("%s", s) != EOF){ if(error_flg) continue; idx = 0; error_flg = !Line(); } if(error_flg){ printf("Error\n"); } else{ int ans = 0; for(int i = 'A'; i <= 'Z'; i++){ if(0 < var[i]){ mem_flg[var[i]] = false; } } for(int i = 1; i < max_ptr; i++){ if(mem_flg[i]){ ans += mem_size[i]; } } printf("%d\n", ans); } }
ジャッジ入出力
要望があったので, コーナケースっぽい入出力を貼っておきます.
100 A=malloc(10) B=clone(A) free(A) #=> 0 100 free(NULL) #=> 0 100 A=malloc(10) free(A) free(A) #=> Error 100 A=NULL free(A) free(A) #=> 0 100 clone(NULL) #=> 0 10 A=malloc(100) B=clone(A) free(A) #=> 0 30 A=malloc(100) B=malloc(10) A=clone(A) B=clone(B) free(B) free(A) #=> 10 30 A=malloc(100) B=malloc(50) A=clone(A) B=clone(B) free(B) free(A) #=> 0 100 clone(B=clone(clone(D=malloc(10)))) #=>20 10 A=B #=>0 10 clone(A) #=> Error