SRM 464 DIV 2 - div1に上がりたいkeitanxkeitanの日記

久々に挑戦！

[250 ColorfulBoxesAndBalls]
numRed個の赤箱と赤ボール、numBlue個の青箱と青ボールがある。
赤箱に赤ボール、青箱に青ボールを入れるとそれぞれonlyRedポイント、onlyBlueポイントが得られる。
赤箱に青ボール、青箱に赤ボールを入れるとbothColorsポイントが得られる。

numRed、numBlue、onlyRed、onlyBlue、bothColorsが与えられたとき、得られるポイントの最大値を求める問題。

全通り試そうとすると？？となってしまう（気がする）が、あることに気がつくと簡単に解けた。

numRed <= numBlueのとき、(numBlue-numRed)個は必ず青箱-青ボールのペアができる。
numRed個の赤ボールの内、赤箱に入れる個数をrとすると、対となってr個の青箱-青ボールのペアができる。
そして(numRed-r)個の赤ボールは青箱に入り、対となって(numRed-r)個の青ボールが赤箱に入る。
よって0 <= r <= numRedの範囲で、ポイントの最大値を求めればよい。

numBlue > numRedのときも同様。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class ColorfulBoxesAndBalls {
public:
    int getMaximum(int numRed, int numBlue, int onlyRed, int onlyBlue, int bothColors) {
	int result = INT_MIN;
	if (numRed <= numBlue) {
	    for (int r = 0; r <= numRed; ++r) {
		int tmp = onlyRed * r + onlyBlue * r + 2 * bothColors * (numRed - r) + onlyBlue * (numBlue - numRed);
		result = max(result, tmp);
	    }
	} else {
	    for (int b = 0; b <= numBlue; ++b) {
		int tmp = onlyRed * b + onlyBlue * b + 2 * bothColors * (numBlue - b) + onlyRed * (numRed - numBlue);
		result = max(result, tmp);
	    }
	}
	return result;
    }
};

[500 ColorfulStrings]
提出したけど撃墜されたorz

[1000 ColorfulMazeTwo]
DFSで実装してみたけどTLEでシステムテスト全部通らない＼(＾o＾)／
せっかくメモしたprb[r][c]を使いこなせてない。。。
というかDFSでいいのか？？

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

int H, W;
double maxprb;
bool visited[51][51], used[7];
vector<string> maze2;
vector<int> trap2;
double prb[51][51];

int dr[4] = {0, -1, 0, 1};
int dc[4] = {1, 0, -1, 0};

bool ok(int r, int c) {
    return r >= 0 && r < H && c >= 0 && c < W && maze2[r][c] != '#' && !visited[r][c];
}
    
double dfs(int r, int c, double prob) {
    if (maze2[r][c] == '!') {
	maxprb = max(maxprb, prob);
	return prb[r][c] = prob;
    }
    visited[r][c] = true;
    bool flag = false;
    if (maze2[r][c] >= 'A' && maze2[r][c] <= 'G' && !used[maze2[r][c]-'A']) {
	prob *= (double)(100 - trap2[maze2[r][c]-'A']) * 0.01;
	used[maze2[r][c]-'A'] = true;
	flag = true;
    }
    double maxprob = 0.0;
    for (int i = 0; i < 4; ++i) {
	int nr = r + dr[i];
	int nc = c + dc[i];
	double tmp;
	if (ok(nr, nc) && maxprb < prob && prob > prb[nr][nc]) {
	    tmp = dfs(nr, nc, prob);
	    maxprob = max(maxprob, tmp);
	}
    }
    visited[r][c] = false;
    if (flag) {
	used[maze2[r][c]-'A'] = false;
    }
    return prb[r][c] = max(prb[r][c], maxprob);
}

class ColorfulMazeTwo {
public:
    double getProbability(vector <string> maze, vector <int> trap) {
	H = maze.size();
	W = maze[0].size();
	maxprb = 0.0;
	for (int i = 0; i < H; ++i) {
	    maze2.push_back(maze[i]);
	}
	for (int i = 0; i < trap.size(); ++i) {
	    trap2.push_back(trap[i]);
	}
	double result = 0.0;
	for (int r = 0; r < H; ++r) {
	    for (int c = 0; c < W; ++c) {
		if (maze[r][c] == '$') {
		    result = dfs(r, c, 1.0);
		}
	    }
	}
	return result;
    }
};

[追記]
バイト中とランニング中考えて通したぞー！
ランニング中に考えてて転倒して割と大けがしたのも報われるってもんだ。

問題の捉え方というのが本当に大事であると実感した。
これまでのやり方はアルファベットのタイルに来たら、初めてのアルファベットなら確率を操作して、
通過済みフラグを立たせる。これをDFSでやってたけどなんかうまくいかなかった。。。

でもこの問題、通過できるタイルを始めに決めてしまえば、確率はその場で求められるんだねぇ。。。
その上でゴールできるか判定をして、できればmaxprob = max(maxprob, prob)っていう風にすればいいわけ。
タイルは'A'から'G'まで７種類しかないから2^7=128通りのタイルの組み合わせについて、それぞれゴールできるか判定すればいい。
ゴール判定は１つでもゴールできるルートが見つかればいいからBFSで。

これまでだったら簡単に投げ出してググって終わりだったかもしれないけど、
昨日の今日でSRMの解答なんてないから自力で頑張れて良かった・゜゜・(/□＼*)・゜゜・

[ちょっと詰まったメモ]
BFSでvisited[r][c]をtrueにするのは、キューから取り出した時じゃなくて、キューにプッシュする時にすべき。
これをやらなくてシステムテストでuncaught exception（謎。メモリ不足？）を出した。
どう違うかというと、下の図ような場合、○を現在地とすると、○から１ステップで移動可能な□と△をキューにプッシュする。
次に□を取り出して１ステップで移動可能な×をキューにプッシュする。ここで後者の場合ではvisited[1][1]をtrueにしてしまうので、次の△のとき×はプッシュされない。一方、前者の場合では、×を取り出すまでvisited[1][1]はtrueにならないので、
△のときも×がプッシュされてしまい、メモリを無駄に食ってしまう。



　０１

０○□

１△×

PKUでも似たような教訓を得た気がするけど忘れてた！

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

int H, W;
vector<string> maze2;
bool tile[7];
bool visited[50][50];

int dr[4] = {0, -1, 0, 1};
int dc[4] = {1, 0, -1, 0};

bool ok(int r, int c) {
    return r >= 0 && r < H && c >= 0 && c < W && maze2[r][c] != '#' && !visited[r][c]
	&& (!(maze2[r][c] >= 'A' && maze2[r][c] <= 'G') || tile[maze2[r][c]-'A']);
}

bool bfs(int r, int c) {
    queue<pair<int, int> > Q;
    memset(visited, false, sizeof(visited));
    Q.push(make_pair(r, c));
    visited[r][c] = true;
    while (!Q.empty()) {
	int tmp_r = Q.front().first;
	int tmp_c = Q.front().second;
	Q.pop();
	if (maze2[tmp_r][tmp_c] == '!') return true;
	if (maze2[tmp_r][tmp_c] >= 'A' && maze2[tmp_r][tmp_c] <= 'G') {
	    if (!tile[maze2[tmp_r][tmp_c]-'A']) continue;
	}
	for (int i = 0; i < 4; ++i) {
	    int nr = tmp_r + dr[i];
	    int nc = tmp_c + dc[i];
	    if (ok(nr, nc)) {
		Q.push(make_pair(nr, nc));
		visited[nr][nc] = true;  // ここでvisitedを操作してしまう
	    }
	}
    }
    return false;
}

class ColorfulMazeTwo {
public:
    double getProbability(vector <string> maze, vector <int> trap) {
	H = maze.size();
	W = maze[0].size();
	for (int i = 0; i < H; ++i) {
	    maze2.push_back(maze[i]);
	}
	int sr, sc;
	for (int r = 0; r < H; ++r) {
	    for (int c = 0; c < W; ++c) {
		if (maze[r][c] == '$') {
		    sr = r, sc = c;
		    break;
		}
	    }
	}
	double maxprob = 0.0;
	for (int ia = 0; ia < 2; ++ia) {
	    for (int ib = 0; ib < 2; ++ib) {
		for (int ic = 0; ic < 2; ++ic) {
		    for (int id = 0; id < 2; ++id) {
			for (int ie = 0; ie < 2; ++ie) {
			    for (int iff = 0; iff < 2; ++iff) {
				for (int ig = 0; ig < 2; ++ig) {
				    tile[0] = ia==0?false:true;
				    tile[1] = ib==0?false:true;
				    tile[2] = ic==0?false:true;
				    tile[3] = id==0?false:true;
				    tile[4] = ie==0?false:true;
				    tile[5] = iff==0?false:true;
				    tile[6] = ig==0?false:true;
				    if (bfs(sr, sc)) {
					double prob = 
					    1.0
					    * (100 - trap[0] * ia) * 0.01
					    * (100 - trap[1] * ib) * 0.01
					    * (100 - trap[2] * ic) * 0.01
					    * (100 - trap[3] * id) * 0.01
					    * (100 - trap[4] * ie) * 0.01
					    * (100 - trap[5] * iff) * 0.01
					    * (100 - trap[6] * ig) * 0.01;
					maxprob = max(maxprob, prob);
				    }
				}
			    }
			}
		    }
		}
	    }
	}
	return maxprob;
    }
};

for7連発のところはfor (mask = 0; mask < 1 << 7; ++mask)とかやったらかっこよくなりそう…！