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

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI 予選2013 - 2014 参加記

この発言は開始1 時間で裏切られることになりました.

開始20 分前くらいまで

がんばってSPL の処理系を入れようとするが, Makefile が壊れているらしくインストールできず諦める.
というか入れてたところで使いこなせる気がまったくしなかった.

1 問目

ということでMisa で挑戦してみることにした. そもそもBrainf*ck での整数の入力がわからないので撃沈...
仕方ないのでScratch で解くことに.

ソースコード :
http://gyazo.com/caa5b484469e70380549caa715d2ec2e

2 問目

Scratch を早くも使い果たしてしまい激しく動揺し, Misa も使えなくて死にかけていた. そこでJ をインストールする. 9.6MB とかガチヤバ...

... 1 時間近くリファレンスを読んでもよくわからないし, 某J のフロンティアの人のブログを読んでも何をしているかわからないので諦める.

3 問目

Ruby で解くことにした. しかし授業レベルでしかRuby を触ったことがないので, ひどいコードになってしまった.
(X_1, Y_1) から旅行スタート! を(1, 1) からと勘違いして, サンプルと一致せずにつらくなる.
今年のJOI 予選1 完説までありえて死にたくなってきた(後に色々間違っていることに気づく.)

4 問目

窮地に陥り, とりあえず4 のDP で気休めをしようと考えたがめっちゃ変なミスで時間を使う.
python で解こうと思ったがこの時は4 次元配列の作り方がわからずあえなく撃沈.
一旦C++ でといて, 後で何かに移植しようと決意.

(このソースは終わった後にすぐ直したもので, 実際は[8] を[2][2][2] に分けていました.)
ソースコード :

#include <cstdio>

using namespace std;

int dp[1001][8];

int main()
{
	char s[1024];
	int n;
	
	scanf("%d", &n);
	scanf("%s", s);
	
	dp[0][4] = 1;
	int sum;
	for (int i = 0; s[i]; i++){
		sum = 0;
		int b = (s[i] == 'J' ? 2 : (s[i] == 'O' ? 1 : 0));
		for (int j = 1; j < 8; j++){
			for (int k = 1; k < 8; k++){
				if ((k >> b & 1) && (j & k) != 0){
					dp[i + 1][k] += dp[i][j];
					dp[i + 1][k] %= 10007;
				}
			}
		}
		for (int j = 1; j < 8; j++){
			sum = (sum + dp[i + 1][j]) % 10007;
		}
	}
	
	printf("%d\n", sum);
	
	return (0);
}

問 3

戻ってきて, 誤読に気づいたのでパパっと直して終わる.

def min(x, y)
	return (x) if x < y
	y
end

s = gets.split(' ')
w, h, n = s[0].to_i, s[1].to_i, s[2].to_i

tx = -1
ty = -1
sum = 0

n.times {
	s = gets.split(' ')
	nx, ny = s[0].to_i, s[1].to_i
	if (tx < 0)
		tx = nx
		ty = ny
	end
	dx = nx - tx
	dy = ny - ty
	
	if (dx * dy >= 0)
		dx = -dx if (dx < 0)
		dy = -dy if (dy < 0)
		m = min(dx, dy)
		sum = sum + dx + dy - m
	else 
		dx = -dx if (dx < 0)
		dy = -dy if (dy < 0)
		sum = sum + dx + dy
	end
	tx = nx
	ty = ny
}

puts sum

問 2

もうpython の使いドコロがなくなったのでここで使うことにした. 急いで書く.

n, m = raw_input().strip().split(' ')

n = int(n)
m = int(m)

a = [0] * n
b = [0] * m
c = [0] * n
ans = 1
ansv = 0

for i in range(n) :
	a[i] = input()

for i in range(m) :
	b = input()
	for j in range(n) :
		if (a[j] <= b) :
			c[j] += 1;
			if (c[j] > ansv) :
				ansv = c[j]
				ans = j + 1
			break

print ans

問 5

変なDFS を思いついたので書く. 時間が無く焦っていたのでこれもC++. グラフを変形してDijkstra なのは分かったが, 自分が考えたアルゴリズムが何故間違っているのかを証明できていない... (嘘解法が何故嘘なのかをちゃんと分かるようにしたい.)

#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
#include <vector>
#include <cstring>

using namespace std;

vector<int> G[5000];
vector<int> list;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

int N;
int cost[5000], rep[5000], tot[5000];
bool vis[5000], done[5000];

int visit(int v, int left, int needed)
{
	vis[v] = true;
	if (done[v] && tot[v] > needed) printf("dededon\n");
	tot[v] = min(tot[v], needed);
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]] && left){
			visit(G[v][i], left - 1, needed);
		}
	}
	
	if (!done[v]){
		pq.push(make_pair(tot[v], v));
	}
}

int main()
{
	int M;
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d", cost + i, rep + i);
	}
	
	for (int i = 0; i < M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		G[--x].push_back(--y);
		G[y].push_back(x);
	}
	
	for (int i = 0; i < N; i++) tot[i] = INT_MAX;
	
	tot[0] = 0;
	pq.push(make_pair(0, 0));
	while (pq.size()){
		memset(vis, 0, sizeof(vis));
		pair<int, int> x = pq.top(); pq.pop();
		if (done[x.second]) continue;
		done[x.second] = true;
		visit(x.second, rep[x.second], x.first + cost[x.second]);
	}
	
	printf("%d\n", tot[N - 1]);
	
	return (0);
}

問 6

20 点を一番安心して得れるので良い. やはりC++.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int main()
{
	int n;
	int d[1024], a[1024];
	int taste[1024] = {0};
	
	vector<int> v;
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) scanf("%d", d + i);
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	for (int i = 0; i < n; i++) v.push_back(i);
	
	int ans = 0;
	do {
		int tmp = 0;
		memset(taste, 0, sizeof(taste));
		for (int i = 0; i < v.size(); i++){
			tmp += taste[v[i]];
			for (int _a = max(0, v[i] - d[v[i]]); _a <= min(n - 1, v[i] + d[v[i]]); _a++){
				taste[_a] += a[v[i]];
			}
		}
		ans = max(ans, tmp);
	} while (next_permutation(v.begin(), v.end()));
	
	printf("%d\n", ans);
	
	return (0);
}

予選終了後

@potetisensei からpython での多次元配列の作り方を習えたのと, そもそも2 次元配列で行けることが判明したのでpython で4 を書いた.

dp = [range(8) for i in range(1001)]

for i in range(1001) :
	for j in range(8) :
		dp[i][j] = 0

dp[0][1] = 1

n = input()
s = raw_input().strip()

for i in range(n) :
	b = 0
	if s[i] != 'J' :
		b += 1
		if s[i] != 'O' :
			b += 1
	
	for j in range(8) :
		for k in range(8) :
			if (((k >> b) & 1) and (j & k) != 0) :
				dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % 10007

sum = 0
for i in range(8) :
	sum = (sum + dp[n][i]) % 10007

print sum

まとめ

  • 来年も6 色コーディングに挑戦したいので, Esolang だったり普通の言語にもう少し触る
  • 変なアルゴリズムを思いついたら正当性をきちんと証明できるようにする. あまり自信が無いなら証明済みの(既知の) アルゴリズムで解けるかきちんと考察する.
  • 本選いける人は頑張ってください. 僕は今年のボーダーは340 点 ~ 360 点だと思います.