Div.1Easy100問修行始めました

先輩にアドバイスいただいたので即実行。
まだ1ACしかしてないけど・・・

SRM233 PipeCuts

問題文に比較的苦しまされた方。
longer than〜ってところを等号つけて考えちゃってめんどくさいことになってた。
とりあえず1ミスAC

class PipeCuts {
public:
  double probability( vector <int> weldLocations, int L ) {
    double result = 0;
	double cnt = 0;
	for (int i=0; i+1<weldLocations.size(); i++) {
		for (int j=i+1; j<weldLocations.size(); j++) {
			cnt++;
			int a = weldLocations[i], b = weldLocations[j];
			if (a > b) swap(a, b);
			if (a > L || b - a > L || 100 - b > L) result++;
		}
	}
	result /= cnt;
    return result;
  }
};

SRM306

挑戦するだけしたので感想だけでも。
要素を一番前にやるか一番後にやるかの操作だけでもっとも短い手順でソートしたとき、その手数を答える問題。
シュミレーションしてたらTLEしそうと勝手に予想をつけて大小比較で色々とやってみましたが、結局どこかで落ちる。
シュミレーションなのかなぁ・・・ちょっとサイトでこの問題の分野を要チェック

AOJ

ひたすらDFSやってた。

0067

池の数答えるやつ。蟻本にPKUのほうの問題がのってたっけ。
こういうときにstringはべんり。

#include <iostream>
#include <vector>
using namespace std;
typedef vector<string> vs;

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

vs dfs(vs map, int nx, int ny) {
	map[nx][ny] = '0';
	for (int i=0; i<4; i++) {
		if (nx+dx[i]>=0&&nx+dx[i]<12&&
				ny+dy[i]>=0&&ny+dy[i]<12&&map[nx+dx[i]][ny+dy[i]]=='1') {
			map = dfs(map, nx+dx[i], ny+dy[i]);
		}
	}
	return map;
}

int main() {
	vs map;
	string buff;
	while (cin >> buff) {
		map.push_back(buff);
		for (int i=0; i<11; i++) {
			cin >> buff;
			map.push_back(buff);
		}
		int res = 0;
		for (int i=0; i<12; i++) {
			for (int j=0; j<12; j++) {
				if (map[i][j] == '1') {
					res++;
					map = dfs(map, i, j);
				}
			}
		}
		cout << res << endl;
		map.clear();
	}
}

0071

上の類似問題。
ちょっと応用。dfs内のループ数間違えてなんども弾かれたり。

#include <iostream>
#include <vector>
using namespace std;
typedef vector<string> vs;

int dx[] = {-3,-2,-1,0,0,0,0,0,0,1,2,3};
int dy[] = {0,0,0,-3,-2,-1,1,2,3,0,0,0};

vs dfs(vs map, int nx, int ny) {
	map[nx][ny] = '0';
	for (int i=0; i<12; i++) {
		if (nx+dx[i]>=0&&nx+dx[i]<8&&
				ny+dy[i]>=0&&ny+dy[i]<8&&
				map[nx+dx[i]][ny+dy[i]]=='1') {
			map = dfs(map, nx+dx[i], ny+dy[i]);
		}
	}
	return map;
}

int main() {
	int n; cin >> n;
	for (int i=0; i<n; i++) {
		vs map(8);
		for (int j=0; j<8; j++) cin >> map[j];
		int x, y;
		cin >> x >> y;
		map = dfs(map, y-1, x-1);
		cout << "Data " << i+1 << ":" << endl;
		for (int j=0; j<8; j++) cout << map[j] << endl;
	}
}