読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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;
	}
}

感想

今日サイトでJOIの特集番組を見て、アルゴリズムの知識の重要さも改めて実感した。
今までこの世界結局は経験値なんじゃないかとか思ったりして、練習ばかりやってたけど、簡単な方に逃げるからあんまり身についてなかったかも。
蟻本でパソコン触れないときは勉強もしようかなとか思い始めました。

というよりまず学校の勉強もしなきゃね、うん。特に英語と数学は影響あるだろうし・・・

広告を非表示にする