第11回情オリ本選対策5日目

なんとなく開始前にダラダラしてしまった。だって眠いしこのカフェ異常に暑いんだもん。あとラーメンで舌火傷したし。

今日の目標

  • DPの巡回セールスマン問題を理解
  • あとはひたすら問題を解く

18:00-21:35

  • 実はSegment Tree書ける気がしないというかどうやればうまく実装できるか分からない。アリ本のコードは理解できてない。
  • 強連結成分分解は一応趣旨は理解して使い所をまだ理解していないのでそのうち
  • AOJ 0120 Patisserie解けた!だが個人的にはこれは重いに入ってしまう。絶対的コーディング速度不足を感じる。いやまあ実際は訳わからんデバッグでそこそこ時間費した。
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

class TheCakeIsALie {
private:
	int width;
	vector<int> r;
	vector<vector<double> > dp;
	int endPoint;

	double distance(int c, int d) {
		return sqrt(pow(r[c] + r[d], 2.0) - pow(r[c] - r[d], 2.0));
	}
	double search(int cur, int rem) {
		// curからあとremの頂点を訪問してendPointに戻る時の最短の経路
		if (dp[cur][rem] != -1.0)
			return dp[cur][rem];

		double res = INT_MAX;
		if (cur == endPoint && rem == 0)
			return dp[cur][rem] = 0;
		if (rem == 0)
			return dp[cur][rem] = INT_MAX;

		for (int i = 0; i < r.size(); ++i) {
			if (!(rem & (1 << i)))
				continue;
			res = min(res, distance(cur, i) + search(i, rem ^ (1 << i)));
		}
		return dp[cur][rem] = res;
	}

	double startImpl(int startPoint) {
		return search(startPoint, ((1 << r.size()) - 1) ^ (1 << startPoint)) + r[startPoint] + r[endPoint];
	}
public:
	TheCakeIsALie(int width, vector<int>& r, int endPoint)
		: width(width), r(r), dp(r.size(), vector<double>(1 << r.size(), -1.0)), endPoint(endPoint) {}

	double start() {
		double res = INT_MAX;
		for (int i = 0; i < r.size(); ++i) {
			res = min(res, startImpl(i));
		}
		return res;
	}
};

int main()
{
	string line;
	while (getline(cin, line)) {
		stringstream ss(line);
		int width;
		ss>>width;

		int t;
		vector<int> r;
		while (ss>>t)
			r.push_back(t);

		double res = INT_MAX;
		for (int i = 0; i < r.size(); ++i) {
			TheCakeIsALie cake(width, r, i);
			res = min(res, cake.start());
		}
		if (res <= (double)width) {
			cout<<"OK"<<endl;
		} else {
			cout<<"NA"<<endl;
		}
	}
	return 0;
}
  • AOJ 0146 Lupin The 4thが、DPの経路復元とかやった事なかったので、経路復元部限定でトンチンカンな事をしており解けていない。修正すれば通るが修正する元気がもうないので今日は投げたい。
  • 少し何かをしたいが為にAOJ0207 Blockとかいう解く価値のない問題を解く。でも1WAさせたのでダメである。
#include <cstdio>
#include <vector>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;

class BlockMaze {
private:
	vector<vector<int> > maze;
	vector<vector<int> > d;

	void fill(int x, int y, int w, int h, int c)
	{
		for (int i = x; i < x + w; ++i)
		for (int j = y; j < y + h; ++j) {
			maze[i][j] = c;
		}
		return;
	}

	class Coord {
	public:
		int x, y;
		Coord(int x, int y) : x(x), y(y) {}
	};

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

	void bfs(int sx, int sy) {
		int cx = sx, cy = sy;
		const int color = maze[cx][cy];

		queue<Coord> qu;
		qu.push(Coord(cx, cy));
		d[cx][cy] = 0;

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

		while(!qu.empty()) {
			Coord co = qu.front(); qu.pop();
			for (int i = 0; i < 4; ++i) {
				const int nx = co.x + dx[i], ny = co.y + dy[i];
				if (!valid(nx, ny))
					continue;
				if (d[nx][ny] != INT_MAX || color != maze[nx][ny])
					continue;

				d[nx][ny] = d[cx][cy] + 1;
				qu.push(Coord(nx, ny));
			}
		}

		return;
	}
public:
	BlockMaze(int w, int h) : maze(w, vector<int>(h, 0)), d(w, vector<int>(h, INT_MAX)){}

	void placeBlock(int c, int d, int x, int y) {
		if (d == 0) {
			fill(x, y, 4, 2, c);
		} else if (d == 1) {
			fill(x, y, 2, 4, c);
		}
		return;
	}

	bool isReachable(int sx, int sy, int gx, int gy) {
		bfs(sx, sy);
		return d[gx][gy] != INT_MAX;
	}
};

int main()
{
	int w, h;
	while (scanf("%d %d\n", &w, &h), w || h) {
		int sx, sy, gx, gy, n;
		scanf("%d %d %d %d %d\n", &sx, &sy, &gx, &gy, &n);
		sx--, sy--, gx--, gy--;

		BlockMaze bm(w, h);

		for (int i = 0; i < n; ++i) {
			int c, d, x, y;
			scanf("%d %d %d %d\n", &c, &d, &x, &y);
			x--, y--;
			bm.placeBlock(c, d, x, y);
		}

		bool res = bm.isReachable(sx, sy, gx, gy);
		printf("%s\n", res ? "OK" : "NG");

	}
	return 0;
}

3問しか解いてないし(1問まだWAだし)遅いけど、まあ重い問題をがんばって残りの期間解いてみたりとかしてどんどん腕を上げていきたい。
明日明後日は諸般の事情により練習ができないので、なるべく用事を明日明後日中に片付けて、来週は全面的に練習に使えるようにしよう。