JOI 本選 2013 - 2014 オンライン参加記

目標 : 後輩ズに勝つ /\_/\

で参加する予定で, 2 まででいいだろ～と思っていたらハマって4 の考察までして, 試験前の貴重な4 時間を失いました(たのしかったです)

1. JOI 紋章

JOI 旗が取り上げられるのは今回で4 回目なはず. 間違いない.
straight-forward. $O(mn)$

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

using namespace std;

int n, m;
char flag[1024][1024];
char emblem[2][3];

bool check(int i, int j)
{
	if (i < 0 || i + 1 >= m) return (false);
	if (j < 0 || j + 1 >= n) return (false);
	return (strncmp(flag[i] + j, emblem[0], 2) == 0 && strncmp(flag[i + 1] + j, emblem[1], 2) == 0);
}

int main()
{
	scanf("%d %d", &m, &n);
	
	for (int i = 0; i < m; i++){
		scanf("%s", flag[i]);
	}
	
	scanf("%s", emblem[0]); scanf("%s", emblem[1]);
	
	int ans = 0;
	for (int i = 0; i <= m - 2; i++){
		for (int j = 0; j <= n - 2; j++){
			if (check(i, j)){
				ans++;
			}
		}
	}
	
	int base = ans;
	char rot[] = "JOI";
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			char bef = flag[i][j];
			int ct = 0;
			
			if (check(i - 1, j)) ct++;
			if (check(i - 1, j - 1)) ct++;
			if (check(i, j - 1)) ct++;
			if (check(i, j)) ct++;
			
			for (int k = 0; k < 3; k++){
				int tmp = base - ct;
				flag[i][j] = rot[k];
				
				if (check(i - 1, j)) tmp++;
				if (check(i - 1, j - 1)) tmp++;
				if (check(i, j - 1)) tmp++;
				if (check(i, j)) tmp++;
				
				flag[i][j] = bef;
				ans = max(ans, tmp);
			}
		}
	}
	
	printf("%d\n", ans);
}

2. JOI 饅頭

例年の2番DP 枠よりは易化してると思った.
ところでみなさん2*10^4 まで見ると言ってますがそれはいったい...

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;


int main()
{
	int m, n;
	int a[10000];
	int sum[10001];
	
	scanf("%d %d", &m, &n);
	
	for (int i = 0; i < m; i++){
		scanf("%d", a + i);
	}
	
	sort(a, a + m);
	reverse(a, a + m);
	
	sum[0] = 0;
	
	for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + a[i - 1];
	
	int dp[100001];
	fill(dp, dp + 100000, INT_MAX / 2);
	
	dp[0] = 0;
	for (int i = 0; i < n; i++){
		int t, v;
		scanf("%d %d", &t, &v);
		for (int j = 10000; j - t >= 0; j--){
			dp[j] = min(dp[j], dp[j - t] + v);
		}
		for (int j = 10000; j >= 1; j--){
			dp[j - 1] = min(dp[j], dp[j - 1]);
		}
	}
	
	int ans = 0;
	for (int i = 0; i <= m; i++) ans = max(ans, sum[i] - dp[i]);
	printf("%d\n", ans);
	
	return (0);
}

3. バームクーヘン

春はねむぽよなので, 頭が眠っていて, ある地点X から和がS になる区間を高速にもとめるのむずいなあ, どうしようと悩んでいて, 僕なりに出た結論が巡回スケジューリングでした(絶望).
ソートがボトルネックでバケットソートする程度には時間を潰しましたね...w

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

using namespace std;

typedef long long lint;

int main()
{
	int n;
	static int a[100000];
	static int s[200000], t[200000], next[2][200000];
	static pair<int, int> p[400000];
	static vector<int> bucket[300000];
	
	lint sum = 0;
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		scanf("%d", a + i);
		sum += a[i];
	}
	
	lint left = 0, right = sum / 3;
	
	while (left != right){
		lint mid = (left + right + 1) >> 1;
		lint sum2 = 0;
		int head = 0, tail = 0;
		bool ng = false;
		
		for (; head < n; head++){
			while (sum2 < mid){
				sum2 += a[tail++];
				if (tail >= n) tail -= n;
			}
			int i = head;
			s[i] = head, t[i] = tail;
			if (s[i] == t[i]) ng = true;
			if (t[i] < s[i]) t[i] += n;
			s[n + i] = s[i] + n, t[n + i] = t[i] + n;
			sum2 -= a[head];
		}
		if (ng){
			right = mid - 1;
			continue;
		}
		for (int i = 0; i < n * 3; i++) bucket[i].clear();
		
		for (int i = 0; i < n * 2; i++){
			bucket[t[i]].push_back(i);
			bucket[s[i]].push_back(n * 2 + i);
		}
		int ctr = 0;
		for (int i = 0; i < n * 3; i++){
			for (int j = 0; j < bucket[i].size(); j++){
				p[ctr++] = make_pair(i, bucket[i][j]);
			}
		}
		
		int last = -1;
		for (int i = n * 4 - 1; i >= 0; i--){
			int id = p[i].second;
			if (id < n * 2) next[0][id] = last;
			else {
				id -= n * 2;
				if (last < 0 || t[last] > t[id]) last = id;
			}
		}
		
		for (int k = 0; k + 1 < 2; k++){
			for (int i = 0; i < n * 2; i++){
				if (next[k][i] < 0) next[k + 1][i] = -1;
				else next[k + 1][i] = next[k][next[k][i]];
			}
		}
		
		int res = 0;
		for (int i = 0; i < n; i++){
			int tmp = 0, j = i;
			for (int k = 1; k >= 0; k--){
				int j2 = next[k][j];
				if (j2 >= 0 && t[j2] <= s[i] + n){
					j = j2;
					tmp |= 1 << k;
				}
			}
			if (res >= 3) break;
			res = max(res, tmp + 1);
		}
		if (res >= 3) left = mid;
		else right = mid - 1;
	}
	
	printf("%lld\n", left);
	
	return (0);
}

4. フクロモモンガ
25 点欲しかったけど貰えなかった. ちょっとこれはフィードバックをみないとデバッグできない.

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

using namespace std;

typedef long long lint;

vector<pair<int, int> > G[1000 * 101];
int h[1024];
int a, b, t;

int main()
{
	int n, m, x;
	
	scanf("%d %d %d", &n, &m, &x);
	
	if (n > 1024) return ((int)"あたしのいくじなし～><");
	
	for (int i = 0; i < n; i++){
		scanf("%d", h + i);
		for (int j = 0; j < h[i]; j++){
			G[i * 101 + j].push_back(make_pair(i * 101 + j + 1, 1));
			G[i * 101 + j + 1].push_back(make_pair(i * 101 + j, 1));
		}
	}
	
	for (int i = 0; i < m; i++){
		scanf("%d %d %d", &a, &b, &t);
		--a; --b;
		for (int j = t; j <= h[a] && j - t <= h[b]; j++){
			G[a * 101 + j].push_back(make_pair(b * 101 + j - t, t));
		}
		for (int j = t; j <= h[b] && j - t <= h[a]; j++){
			G[b * 101 + j].push_back(make_pair(a * 101 + j - t, t));
		}
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	
	
	bool done[1000 * 101] = {0};
	
	for (pq.push(make_pair(0, x)); pq.size(); pq.pop()){
		pair<int, int> tmp = pq.top();
		if (done[tmp.second]) continue;
		done[tmp.second] = true;
		if (tmp.second == (n - 1) * 101 + h[n - 1]) return (!printf("%d\n", tmp.first));
		
		for (int i = 0; i < G[tmp.second].size(); i++){
			pair<int, int> next = G[tmp.second][i];
			if (done[next.first]) continue;
			pq.push(make_pair(tmp.first + next.second, next.first));
		}
	}
	
	return (!printf("-1\n"));
}

5. 切り取り線
Ω＼ζ°)ﾁｰﾝ

6. まとめ
たのしかったよ～～