第3回 ドワンゴからの挑戦状 本選 : A - 計算ドリル

予選解ききってないけど先に本選解いた。リアルタイムではオープン含め参加してないです。
http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_a

問題

1桁の整数と加減算の二項演算子で構成された逆ポーランド記法の式が与えられる。
途中の要素をいくつか書き換え、式を計算すると最後スタックに単一の整数が残るようにしたい。

• 書き換える要素の最小数を求めよ。
• 得られる数値の最大値を求めよ。

解法

ある数式の部分列S[L...R]が計算後単一要素になる条件を考え、メモ化再帰で解いていく。

• L=R、すなわち要素数1の場合
  • S[L]は整数でなければならない。
• L＜R、すなわち要素数2以上の場合
  • 末尾のS[N]は演算子でなければならない。
  • また、末尾を除いたS[1..(N-1)]を計算すると2つの要素が残らなければならない。

後者の場合、S[L...R]をS[L...X]、S[(X+1)...(R-1)]、S[R]の3つに分解したとき、前2つが単一の整数値、最後の要素が演算子となるようにしよう。
あとは分割位置Xを総当たりしつつ、条件を満たす最小書き換え回数と、計算結果の最大値・最小値を求めていけばよい。

int K,N;
string S;

bool vis[60][60][60];
bool res[60][60][60];

int dp[60][60][60][2];

bool dpdp(int L,int R,int K) {
	if(vis[L][R][K]) return res[L][R][K];
	if((R-L)%2==1) return false;
	vis[L][R][K]=true;
	dp[L][R][K][0]=1<<20;
	dp[L][R][K][1]=-1<<20;
	
	
	if(L==R) {
		if(K) {
			res[L][R][K]=true;
			dp[L][R][K][0]=0;
			dp[L][R][K][1]=9;
		}
		else {
			if(S[L]>='0' && S[L]<='9') {
				res[L][R][K]=true;
				dp[L][R][K][0]=dp[L][R][K][1]=S[L]-'0';
			}
		}
	}
	else {
		int left=K-(S[R]!='+');
		if(left>=0) {
			for(int M=L;M<R-1;M++) for(int LL=0;LL<=left;LL++) {
				if(dpdp(L,M,LL) && dpdp(M+1,R-1,left-LL)) {
					res[L][R][K]=true;
					dp[L][R][K][0]=min(dp[L][R][K][0],dp[L][M][LL][0]+dp[M+1][R-1][left-LL][0]);
					dp[L][R][K][1]=max(dp[L][R][K][1],dp[L][M][LL][1]+dp[M+1][R-1][left-LL][1]);
				}
			}
		}
		left=K-(S[R]!='-');
		if(left>=0) {
			for(int M=L;M<R-1;M++) for(int LL=0;LL<=left;LL++) {
				if(dpdp(L,M,LL) && dpdp(M+1,R-1,left-LL)) {
					res[L][R][K]=true;
					dp[L][R][K][0]=min(dp[L][R][K][0],dp[L][M][LL][0]-dp[M+1][R-1][left-LL][1]);
					dp[L][R][K][1]=max(dp[L][R][K][1],dp[L][M][LL][1]-dp[M+1][R-1][left-LL][0]);
				}
			}
		}
	}
	return res[L][R][K];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>S;
	N=S.size();
	
	int ma=-10000;
	FOR(i,K+1) if(dpdp(0,N-1,i)) ma=max(ma,dp[0][N-1][i][1]);
	
	if(ma==-10000) _P("NG\n");
	else _P("OK\n%d\n",ma);
	
}

まとめ

500ptなのにさっくり解けなかった…。