第11回情オリ本選対策6日目(あと使えるのは12日!)

アリ本2版買った。

きゅうりの頻出典型アルゴリズムまとめを上から解いた事ないやつ埋めていった。
正直実力足りなすぎていて、普通に合宿落ちそうでつらい。明日から三日間自由に使える時間があるので、そこで過去問にある程度入れないと爆死する事は確定的に明らか。でも過去問解けないんすよね…問1、2、3対策をひたすらやるか。あとBIT覚えたので去年の本選5?を解きたい。

19:00-22:00

  • AOJ 0235 Sergeant Rian、深さ優先探索らしいが普通にWAった。解法何が間違ってるんだろう、反例があまり思いつかない。ぐぐったらDP解法とかやったらめったら複雑に考えてるのばっかひっかかったのでパス。以下WAソース。
#include <cstdio>
#include <vector>
using namespace std;
class SergRian {
public:
	class Edge {
	public:
		int to, len;
		Edge(int to, int len) : to(to), len(len) {}
	};
private:
	vector<vector<Edge> > edges;
	vector<bool> visited;

	bool isVisitNec(int cur) {
		for (int i = 0; i < edges[cur].size(); ++i) {
			if (!visited[edges[cur][i].to])
				return true;
		}
		return false;
	}
	int search(int cur) {
		int res = 0;
		int lastEdge = 0;
		visited[cur] = true;
		for (int i = 0; i < edges[cur].size(); ++i) {
			const Edge e = edges[cur][i];
			if (visited[e.to])
				continue;
			if (!isVisitNec(e.to))
				continue;
			res += lastEdge;
			res += search(e.to) + e.len;
			lastEdge = e.len;
		}
		return res;
	}
public:
	SergRian(int N) : edges(N), visited(N, false) {}
	void addEdge(int from, int to, int len) {
		edges[from].push_back(Edge(to, len));
		edges[to].push_back(Edge(from, len));
		return;
	}
	int start() {
		return search(0);
	}
};

int main()
{
	int N;
	while (scanf("%d\n", &N), N) {
		SergRian sr(N);

		for (int i = 0; i < N - 1; ++i) {
			int a, b, t;
			scanf("%d %d %d\n", &a, &b, &t);
			a--, b--;
			sr.addEdge(a, b, t);
		}
		printf("%d\n", sr.start());
	}
	return 0;
}
  • AOJ 0118 Property Distribution、こんな問題を解いて時間をつぶしてはいけないが、サクッと解けないのも問題だしどこからが解けないかの線引きムズい。
#include <vector>
#include <string>
#include <iostream>
using namespace std;

class Garden {
private:
	vector<string> garden;

	bool valid(int x, int y) {
		return 0 <= x && x < garden.size() && 0 <= y && y < garden[0].size();

	}
	void bfs(int x, int y, char c) {
		const int dx[] = {1, 0, -1, 0};
		const int dy[] = {0, 1, 0, -1};
		for (int i = 0; i < 4; ++i) {
			const int cx = x + dx[i], cy = y + dy[i];
			if (!valid(cx, cy))
				continue;
			if (garden[cx][cy] != c)
				continue;
			garden[cx][cy] = ' ';
			bfs(cx, cy, c);
		}
		return;
	}
public:
	Garden(vector<string>& garden) : garden(garden) {}
	int start() {
		int res = 0;
		for (int i = 0 ; i < garden.size(); ++i) {
			for (int j = 0; j < garden[i].size(); ++j) {
				if (garden[i][j] == ' ')
					continue;
				res++;
				const char c = garden[i][j];
				garden[i][j] = ' ';
				bfs(i, j, c);
			}
		}
		return res;
	}
};
int main()
{

	int H, W;
	while ((cin>>H>>W), H || W) {
		vector<string> garden(H);
		for (int i = 0; i < H; ++i) {
			cin>>garden[i];
		}

		Garden g(garden);
		cout<<g.start()<<endl;
	}
	return 0;
}
  • AOJ 0179 Mysterious Worm、状態を覚えておいて幅優先というのを今日まで知らなかったので処刑確定。
#include <string>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <map>
using namespace std;

inline char getOther(char a, char b)
{
	if(a > b) swap(a, b);
	if (a == 'b' && b == 'g') return 'r';
	if (a == 'b' && b == 'r') return 'g';
	if (a == 'g' && b == 'r') return 'b';
}


int solve(string s)
{
	const char colors[] = {'r', 'g', 'b'};

	map<char, string> goals;
	for (int i = 0; i < 3; ++i)
		goals[colors[i]] = string(s.size(), colors[i]);

	set<string> se;
	queue<pair<string, int> > qu;

	qu.push(make_pair(s, 0));
	se.insert(s);

	while (!qu.empty()) {
		const pair<string, int> cur = qu.front(); qu.pop();
		if (goals[cur.first[0]] == cur.first)
			return cur.second;

		for (int i = 0; i < cur.first.size() - 1; ++i) {
			if (cur.first[i] != cur.first[i + 1]) {
				string next = cur.first;
				next[i] = next[i + 1] = getOther(next[i], next[i + 1]);
				if (se.find(next) == se.end()) {
					se.insert(next);
					qu.push(make_pair(next, cur.second + 1));
				}
			}
		}
	}
	return -1;
}

int main()
{
	string s;
	while ((cin>>s), s != "0") {
		const int res = solve(s);
		if(res != -1)
			cout<<res<<endl;
		else
			cout<<"NA"<<endl;
	}
	return 0;
}
  • AOJ0121 Seven Puzzle、こういうのはTLE回避法とかぐぐってしまうと萎える。
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
using namespace std;

class Puzzle {
private:
	class State {
	public:
		int step;
		vector<char> v;
		char zero;
		State(int step, vector<char>& v) : step(step), v(v) {
			for (char i = 0; i < (char)v.size(); ++i) {
				if (v[i] == 0) {
					zero = i;
					break;
				}
			}
		}
		State(int step, vector<char>& v, char zero) : step(step), v(v), zero(zero) {}
	};
	vector<int> steps;
private:
	inline int encode(const vector<int>& v) {
		vector<char> t(v.size());
		for (int i = 0; i < v.size(); ++i) {
			t[i] = (char)v[i];
		}
		return encode(t);
	}
	inline int encode(const vector<char>& v) {
		int res = 0;
		for (int i = 0; i < v.size(); ++i) {
			res *= 8; 
			res += (int)v[i];
		}
		return res;
	}
	inline static int epower() {
		int res = 1;
		for (int i = 0; i < 8; ++i)
			res *= 8;
		return res;
	}
public:
	void createTable()
	{
		const int dx[] = {1, 0, -1, 0};
		const int dy[] = {0, 1, 0, -1};

		vector<char> start(8);
		for (char i = 0; i < (char)start.size(); ++i)
			start[i] = i;

		set<vector<char> > se;
		queue<State> qu;

		qu.push(State(0, start));
		se.insert(start);

		while (!qu.empty()) {
			const State st = qu.front(); qu.pop();
			steps[encode(st.v)] = st.step;

			const int place = (int)st.zero;
			const int cx = (place >= 4 ? place - 4 : place), cy = (place >= 4 ? 1 : 0);
			for (int i = 0; i < 4; ++i) {
				const int nx = cx + dx[i], ny = cy + dy[i];
				if (!(0 <= nx && nx < 4 && 0 <= ny && ny < 2))
					continue;

				const int flat = nx + ny * 4;

				vector<char> next(st.v);
				swap(next[place], next[flat]);

				if (se.find(next) == se.end()) {
					se.insert(next);
					qu.push(State(st.step + 1, next, (char)flat));
				}
			}
		}
	}
	Puzzle() : steps(epower()) {}

	int get(vector<int>& input) {
		return steps[encode(input)];
	}
};
int main()
{
	vector<int> in(8);
	Puzzle pu;
	pu.createTable();
	while (~scanf("%d %d %d %d "
			"%d %d %d %d\n", 
			&in[0], &in[1], &in[2], &in[3],
			&in[4], &in[5], &in[6], &in[7])) {
		const int res = pu.get(in);
		printf("%d\n", res);
	}AOJ0223.cpp


	return 0;
}
  • AOJ0223、そもそもローカルで答えがあわないしどうやって解くのが正解なんすかこれぐぐろう。

本選までがんばろう!負けるにしても心残りな負け方はしたくない!