APIO 2013 参加記 - Lilliput Steps

むずかしかったです(感想)
まわりの出来を聞いた感じ, うまくいけば銅メダルくらいはとれているかも...?
あまり高望みはしないことにします.

それぞれの問題の概要とか.

5/16 追記 : 銅メダルGot でした. わーい!

(1) Robots(ロボット)

[問題概要]
$W \times H$ のグリッドに $n$ 体ロボットがいる. ロボットは$1$ から$n$ までの番号がついている.
$i$ 番目のロボットは$i - 1$ 番目のロボットがくっついているロボットの集合か, $i + 1$ 番目のロボットがくっついている集合にくっつける. ($3$ 番目のロボットと$4$ 番目のロボットがくっつくと$[3, 4]$ロボットになり, $[1, 2]$ロボットと$3$番目のロボットがくっつくと$[1, 3]$ロボットになる.)
合体したロボットの集合は行動をともにする.

ロボットは障害物にぶつかるか壁にぶつかるまで一直線上に($90^{\circ} / 270^{\circ}$ 回転できる装置が置かれていなければ)すすむ. $[1, n]$ロボットになるまでにロボットを移動させないといけない回数の最小値を求めよ.

$W, H \leqq 500, n \leqq 9$

[思考]
問題文の読解ができないので(2), (3) を読んで実装していたらまったく触れていなかった.
30 点解法はBFS を前もって両方のロボットについてしておいて, マスx にたどりつくまでの時間の合計の最小値を答えとすればよさそう.
満点解法にするにはdp[x][y] : ロボット[x, y]を作るための最小手数みたいな区間dp だろうか...(あまり考えていない)

[コード] たぶん30 点解法.

#include <cstdio>
#include <deque>

using namespace std;

const int INF = 100000000;

int n, w, h;
int mini[512][512][10];
int memo[512][512][4];
char mp[512][512];
int sy[9], sx[9];

struct Event {
	int ny, nx, dir, time;
	Event(int ny, int nx, int dir, int time) : 
		ny(ny), nx(nx), dir(dir), time(time) {}
};

int dy[] = {0, -1, 0, 1}, dx[] = {1, 0, -1, 0};
//A...dir = (dir + 1) % 4
//C...dir = (dir + 3) % 4

bool valid(int y, int x)
{
	return (0 <= y && y < h && 0 <= x && x < w && mp[y][x] != 'x');
}

void doBFS(int k)
{
	for (int i = 0; i < 512; i++){
		for (int j = 0; j < 512; j++){
			for (int dir = 0; dir < 4; dir++){
				memo[i][j][dir] = INF;
			}
		}
	}
	
	deque<Event> q;
	
	for (int i = 0; i < 4; i++){
		q.push_front(Event(sy[k], sx[k], i, 1));
		memo[sy[k]][sx[k]][i] = 0;
	}
	
	for (; q.size();){
		Event x = q[0]; q.pop_front();
		
		int nexty = x.ny + dy[x.dir], nextx = x.nx + dx[x.dir];
		if (valid(nexty, nextx)){
			if (mp[nexty][nextx] == '.'){
				//if (memo[nexty][nextx][x.dir] == INF){
					q.push_front(Event(nexty, nextx, x.dir, x.time));
					//memo[nexty][nextx][x.dir] = x.time;
				//}
			}
			else {
				int nextdir = (x.dir + 1 + 2 * (mp[nexty][nextx] == 'C')) % 3;
				//if (memo[nexty][nextx][nextdir] == INF){
					q.push_front(Event(nexty, nextx, nextdir, x.time));
					//memo[nexty][nextx][x.dir] = x.time;
				//}
			}
		}
		else {
			for (int i = 0; i < 4; i++){
				if (memo[x.ny][x.nx][i] == INF){
					q.push_back(Event(x.ny, x.nx, i, x.time + 1));
					memo[x.ny][x.nx][i] = x.time;
				}
			}
		}
	}
	
	for (int i = 0; i < 512; i++){
		for (int j = 0; j < 512; j++){
			mini[i][j][k] = min(min(memo[i][j][0], memo[i][j][1]),
								min(memo[i][j][2], memo[i][j][3]));
		}
	}
}

int main()
{
	scanf("%d %d %d", &n, &w, &h);
	
	for (int i = 0; i < h; i++){
		scanf("%s", mp[i]);
		for (int j = 0; j < w; j++){
			if ('1' <= mp[i][j] && mp[i][j] <= '9'){
				sy[mp[i][j] - '1'] = i;
				sx[mp[i][j] - '1'] = j;
				mp[i][j] = '.';
			}
		}
	}
	
	for (int nn = 0; nn < 10; nn++){
		for (int i = 0; i < 512; i++){
			for (int j = 0; j < 512; j++){
				mini[i][j][nn] = INF;
			}
		}
	}
	
	for (int i = 0; i < n; i++){
		doBFS(i);
	}
	
	int ans = -1;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			int tsum = 0;
			bool ng = false;
			for (int nnum = 0; nnum < n; nnum++){
				if (mini[i][j][nnum] == INF) ng = true;
				tsum += mini[i][j][nnum];
				if (i == 0 && j == 0) printf("%d\n", mini[i][j][nnum]);
			}
			if (ng == true) continue;
			if (ans == -1) ans = tsum;
			else ans = min(ans, tsum);
		}
	}
	
	printf("%d\n", g);
	
	return (0);
}

(2) Toll (通行料金)
[問題概要]
頂点数$N$, 辺数$M$ のグラフが与えられる. 頂点には$1$ から $N$ までの番号がついている.
$M$ 本の辺にはそれぞれ異なる重みがついていて, それぞれの頂点には$c[i]$ 人の人が住んでいる.
今, $M$ 本の辺とは別の頂点対を結ぶ$K$ 本の辺をもっている.今, 自由にこの$K$ 本の辺にコストをつけれたとして, $M + K$ 本の辺で最小全域木を構成することを考える.
すべての頂点から頂点$1$ に向かうとして, 重み$p$ の辺に対して支払われる通行料金とは, $\displaystyle \sum_{k \in その辺を通った頂点}c[k] \times p$ で計算される.
$K$ 本の辺で稼げる通行料金の最大値を求めよ.

$N \leqq 10^5,\ M \leqq 3 \times 10^5,\ K \leqq 20$

[思考]
K = 1のケースでは, クラスカルの途中で, 自分のもっている辺の成分がつながりそうになったら自分の辺で置き換えればOK.
K ≧ 2 のケースってどうするんだろう.
56 点までは使う・使わないでビットを遷移させていけばおなじ方法でできそうだけど...

[コード]
回収し損ねた...

(3) Tasksauthor (作問者)
[問題概要]
8 つの小課題が与えられる(下記参照). 問題$P$ について, コード$A$ ではTLE が起こらず, コード$B$ ではTLE が起こる様なテストケースを作成せよ. ただし, それぞれの小課題について, 作成されるテストケースに含まれていても良い整数の個数が決まっている. (output-only)

(コード$A$, コード$B$ に登場するコードは大会側から与えられ, ここでのTLE するとは1000000 回より多い回数の主要な演算を行うことと定義されている.)

#	問題$P$	コード$A$	コード$B$
1	最短経路問題	Dijkstra	Warshall-Floyd
2	最短経路問題	Warshall-Floyd	Bellman-Ford
3	最短経路問題	Bellman-Ford	Warshall-Floyd
4	最短経路問題	Warshall-Floyd	Dijkstra
5	最短経路問題	Dijkstra	Bellman-Ford
6	最短経路問題	Bellman-Ford	Dijkstra
7	頂点彩色問題	絶対TLEしないコード	Recursive-Backtrack
8	頂点彩色問題	Recursive-Backtrack	絶対TLEするコード

[思考]
頂点彩色のRecursive-Backtrack は, 直線の形のグラフ (疎グラフ)につよくて, 密グラフにはものすごく弱いアルゴリズムなので, 簡単に点数が得れる.
最短経路のWarshall-Floyd を落とすには頂点数を101にすればよくて, Bellman-Fordは負の辺のあるDAGにすると落ちてくれる.
Dijkstra を落とすのは闇だったが, でぐわーくんからヒントを得たのでもうすこし考えてみる.

[出力ファイル]
tasksauthor.out1.1
tasksauthor.out2.1
tasksauthor.out3.1
tasksauthor.out5.1
tasksauthor.out7.1
tasksauthor.out8.1

まとめ.

めっちゃおもろいコンテストでした. (2) 番とか激アツな問題で好きになりました(解けてないけど).
APIO でOutput-only がでたの始めてな気がするけど気のせいだろうか. 良い思い出になりました.