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

日本情報オリンピック 第8回本選

Programming Algorithm JOI AOJ

JOI 2008-2009 本選 問題・データ

1. IOIOI

404 Not Found

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
	long long n;
	while(cin>>n, n){
		long long m;
		string s;
		cin>>m>>s;
		n = 2 * n + 1;
		vector<long long> v;
		int len = 0;
		bool is_seq = 0;
		char expect = 0;
		for(long long i = 0; i < m; i++){
			if(is_seq){
				if(s[i] == expect){
					expect = (expect == 'I' ? 'O' : 'I');
					len++;
				}else{
					is_seq = 0;
					if(len >= n){
						if(!(len % 2)) len--;
						v.push_back(len);
					}
				}
			}
			if(!is_seq && s[i] == 'I'){
				is_seq = 1;
				expect = 'O';
				len = 1;
			}
		}
		if(len >= n) v.push_back(len);
		long long dst = 0;
		for(int i = 0; i < v.size(); i++){
			dst += 1 + ((v[i] - n) / 2);
		}
		cout<<dst<<endl;
	}
	return 0;
}

久々にAcceptされた…泣きたい。
というかまともに問題を解く時間がないし死にそう、自分の時間の使い方が下手だっていうのは認めますけれども。

2. ピザ

404 Not Found

#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main()
{
	unsigned int d;
	while(scanf("%u\n", &d), d){
		int n, m;
		scanf("%d\n%d\n", &n, &m);

		vector<unsigned int> v(n);
		v[0] = 0;
		for(int i = 1; i < n; i++)
			scanf("%u\n", &v[i]);

		sort(v.begin(), v.end());

		unsigned int dst = 0;
		for(int i = 0; i < m; i++){
			long long k;
			scanf("%lld\n", &k);
			long long shortest = LLONG_MAX;

			vector<unsigned int>::iterator it = lower_bound(v.begin(), v.end(), k);
			if(it != v.end()) shortest = min(shortest, abs(*it - k));
			if(--it >= v.begin()) shortest = min(shortest, abs(*it - k));
			k += d;
			it = lower_bound(v.begin(), v.end(), k);
			if(it != v.end()) shortest = min(shortest, abs(*it - k));
			if(--it >= v.begin()) shortest = min(shortest, abs(*it - k));
			k -= d; k -= d;
			it = lower_bound(v.begin(), v.end(), k);
			if(it != v.end()) shortest = min(shortest, abs(*it - k));
			if(--it >= v.begin()) shortest = min(shortest, abs(*it - k));
			dst += shortest;
		}
		printf("%d\n", dst);

	}
	return 0;
}

3.

4.

5.

are not solved.