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

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

1. 碁石ならべ

何故かWAする。たしかにテストケースに対する答え見ると違う。なんでだろう。問題を理解できてないのかなあ…見た通り実装した筈なんだが…

2. 共通部分文字列

Longest Common Subsequenceではない。Longest Common Substring。
つまるところDPでもなんでもない。まあDPっぽくも書けるらしいが。
本当に書いてて頭こんがらがりそうになるし、どうしようもなかったので、
より長いほうを決めて、forループ3分割にしたらなんとか書けた。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	string s, t;
	while(cin>>s>>t){
		int dst = 0;
		if(s.size() < t.size()) swap(s, t);

		for(int i = t.size() - 1; 0 < i; i--)
			for(int j = i, k = 0, f = 0; j < t.size(); j++, k++)
				if(t[j] == s[k]) dst = max(dst, ++f); else f = 0;
		
		for(int i = 0; i < s.size() - t.size(); i++)
			for(int j = 0, k = i, f = 0; j < t.size(); j++, k++)
				if(t[j] == s[k]) dst = max(dst, ++f); else f = 0;

		for(int i = t.size() - 1; 0 < i; i--)
			for(int j = 0, k = s.size() - i, f = 0; j < i; j++, k++)
				if(t[j] == s[k]) dst = max(dst, ++f); else f = 0;

		cout<<dst<<endl;
	}
	return 0;
}

3. ダーツ

個数制限なしナップザック? DP解けないんですけど!
→DPじゃなかったっぽい。半分全列挙と言うらしい。Pi * Pjの全ての組を覚えてO(n^4)をO(n^2 + n log n^2)におさえこむ…？

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

int main()
{
	int N, M;
	while(scanf("%d %d\n", &N, &M), N || M){
		vector<int> P(N + 1), Pd;
		for(int i = 0; i < N; i++)
			scanf("%d\n", &P[i]);
		P[N] = 0;

		for(int i = 0; i < P.size(); i++)
		for(int j = 0; j < P.size(); j++)
			Pd.push_back(P[i] + P[j]);

		int res = 0;
		sort(Pd.begin(), Pd.end());
		for(int i = 0, t; i < Pd.size(); i++){
			if((t = M - Pd[i]) < 0) continue;
			res = max(res, Pd[i] + *(lower_bound(Pd.begin(), Pd.end(), t) - 1));
		}

		printf("%d\n", res);
	}
	return 0;
}

4. ぴょんぴょん川渡り

Dijkstraかな？たまにあるn回まで飛ばし可能な〜とかいう類のDijkstraってどうやって解くんだろう。

5. ペンキの色

座標圧縮？こういう場合ってどうやって入力を圧縮するのだろう。