JOI予選過去問解けなかった物(2010/12/16 12:00時点)

Programming Algorithm AOJ JOI

(Total Progress: 4 / 10)

第9回

6. 方向音痴のトナカイ AOJ 0548 Reindeer with no sense of direction

404 Not Found

どこから手をつけていいかすら分からない。
実際ヒント見るとそんなに難しくはない。けど何故かTLE→Runtime Error。えーそんなー。

ところでqのIOI体験記じゃないが、凝った探索問題の場合には盤面の大きさから、その問題は深さ優先探索か、またその引数に盤ごと引き渡す事を想定しているかしてないかが分かるのでちゃんと注意しておいたほうがいいと思った。

第8回

3. 連鎖 AOJ 0534 Chain

404 Not Found

TLEする。計算量減らせず。
厳密に変化するパターンだけを試すようにしたらTLEしなくなった。

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int changecolour(char *c, int N, int pos, int colour){
	char d[N];
	for(int i = 0; i < N; i++)
		d[i] = c [i];
	d[pos] = colour;

	bool changed = true;
	while(changed){
		int last = 0, cnt = 1;
		changed = false;
		for(int i = 0; i <= N; i++){
			if(last == (i != N ? d[i] : 0)){
				cnt++;
			}else{
				if(cnt > 3){
					for(int j = i - cnt; j < N - cnt; j++){
						d[j] = d[j + cnt];
					}
					N -= cnt;
					changed = true;
					break;
				}
				last = d[i];
				cnt = 1;
			}
		}
	}
	return N;
}
inline char shouldchange(int x, char *c, int N){
	// There are following patterns which should  be changed:
	/* x??? */ if((N - x - 1) >= 3) if(c[x + 1] == c[x + 2] && c[x + 1] == c[x + 3]) return c[x + 1];
	/* ?x?? */ if((N - x - 1) >= 2 && (x >= 1)) if(c[x - 1] == c[x + 1] && c[x - 1] == c[x + 2]) return c[x - 1];
	/* ??x? */ if((N - x - 1) >= 1 && (x >= 2)) if(c[x - 2] == c[x - 1] && c[x - 2] == c[x + 1]) return c[x - 2];
	/* ???x */ if(x >= 3) if(c[x - 3] == c[x - 2] && c[x - 3] == c[x - 1]) return c[x - 3];
	return 0;
	
}
int main()
{
	int N;
	while(scanf("%d\n", &N), N){
		int M = N;
		char c[10000];
		for(int i = 0; i < N; i++)
			scanf("%hhd\n", &c[i]);
		if(N > 3){
			for(int i = 0, colour = 0; i < N; i++)
				if((colour = shouldchange(i, c, N)) != 0)
					M = min(M, changecolour(c, N, i, colour));

		}
		printf("%d\n", M);
	}
	return 0;
}
4. 薄氷渡り AOJ 0535 Crossing Black Ice

404 Not Found

WAする。幅優先探索で最初書いたけれども、解説読んだら普通に再帰ごとに盤面を引数に渡すような深さ優先探索でよかったっぽい。それ最初頭よぎったけどそんなんで大丈夫なのか。
というかそれで書きなおしたら謎の答えを吐いたままでデバッグしてない。

5. シャッフル AOJ 0536 Shuffle

404 Not Found

何故Runtime Errorなんだ。多分バグ。
そもそも解法がまずい。非常にでかい値を渡されるので束で管理しなければいけない。
薄々は気付いてたけど…
さらに束解法のコードもerase使ったりコピーコンストラクタ働きまくったりしてるのがマズいのか未だ解けず…

6. ビンゴ AOJ 0537 Bingo

404 Not Found
解法分からず。

第7回

3. カードゲーム AOJ 0523 Card Game

404 Not Found

バグとれず。何故か止まらない。
デバッグコードが残ってただけだった！
こういうありえないポカミスは極力減らしていきたい。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	while(scanf("%d\n", &n), n){
		vector<int> tcards(n), hcards;
		for(int i = 0; i < n; i++)
			scanf("%d\n", &tcards[i]);
		sort(tcards.begin(), tcards.end());
		for(int i = 1, p = 0; i <= 2*n; i++){
			if(p < tcards.size()){
				if(tcards[p] == i){
					p++;
				}else{
					hcards.push_back(i);
				}
			}else{
				hcards.push_back(i);
			}
		}

		int ba = 0;
		int turn = 0;
		while(!tcards.empty() && !hcards.empty()){
			if(turn == 0){/* taro */
				int put = 0;
				for(int i = 0; i < tcards.size(); i++){
					if(tcards[i] > ba){
						ba = tcards[i];
						tcards.erase(remove(tcards.begin(), tcards.end(), ba), tcards.end());
						put = 1;
						break;
					}
				}
				if(!put) ba = 0;
				turn = 1;
			}else{
				int put = 0;
				for(int i = 0; i < hcards.size(); i++){
					if(hcards[i] > ba){
						ba = hcards[i];
						hcards.erase(remove(hcards.begin(), hcards.end(), ba), hcards.end());
						put = 1;
						break;
					}
				}
				if(!put) ba = 0;
				turn = 0;
			}
		}
		int tscore = hcards.size(), hscore = tcards.size();
		printf("%d\n%d\n", tscore, hscore);
	}
	return 0;
}
5. おせんべい AOJ 0525 Osenbei

404 Not Found
どうやって解いていいかも分からず。
行だけに対して総当たりするのがミソ。こういう所でも与えられる値の幅を観察したほうがいいですね…

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
	int R, C;
	while(scanf("%d %d\n", &R, &C), R || C){
		vector<vector<int> > v(R, vector<int>(C));
		for(int i = 0; i < R; i++)
			for(int j = 0; j < C; j++)
				scanf("%d", &v[i][j]);
		int dst = 0;
		for(int i = 0; i < (1 << R); i++){
			vector<vector<int> > w = v;
			for(int j = 0; j < R; j++)
				if(i & (1 << j))
					for(int k = 0; k < C; k++)
						w[j][k] = !w[j][k];

			for(int k = 0; k < C; k++){
				int rtotal = 0;
				for(int j = 0; j < R; j++) rtotal += w[j][k];
				if(rtotal < (R / 2))
					for(int j = 0; j < R; j++) w[j][k] = !w[j][k];
			}
			int total = 0;
			for(int j = 0; j < R; j++)
				for(int k = 0; k < C; k++)
					total += w[j][k];
			dst = max(dst, total);
		}
		printf("%d\n", dst);

	}
	return 0;
}

第6回

5. 品質検査 AOJ 0514 Quality Checking

404 Not Found
とりあえず手はつけてみたもののどうすればサンプル通りの回答が得られるか分からず。
プロコンチャレンジブックとかTopCoderでもこの手の問題みたけどこういう論理的思考力を求められる問題は苦手だ。
=を==って書いてただけだった!ひどい。

#include <cstdio>
#include <vector>
using namespace std;
class test {
public:
	int i, j, k, r;
};
int main(){
	int a, b, c;
	while(scanf("%d %d %d\n", &a, &b, &c), a || b || c){
		vector<int> v(a + b + c + 1, 2);
		int N;
		scanf("%d\n", &N);
		vector<test> w(N);
		for(int _i = 0; _i < N; _i++){
			int i, j, k, r;
			scanf("%d %d %d %d\n", &i, &j, &k, &r);
			w[_i].i = i; w[_i].j = j;
			w[_i].k = k; w[_i].r = r;
		}
		for(int i = 0; i < w.size(); i++){
			if(w[i].r){
				v[w[i].i] = 1; v[w[i].j] = 1; v[w[i].k] = 1;
			}
		}
		for(int i = 0; i < w.size(); i++){
			if(!(w[i].r)){
				if(v[w[i].i] == 1 && v[w[i].j] == 1) v[w[i].k] = 0;
				if(v[w[i].i] == 1 && v[w[i].k] == 1) v[w[i].j] = 0;
				if(v[w[i].j] == 1 && v[w[i].k] == 1) v[w[i].i] = 0;
			}
		}
		for(int i = 1; i < v.size(); i++)
			printf("%d\n", v[i]);
	}
	return 0;
}

第5回

4. AOJ 0503 Cup

404 Not Found
ハノイの塔のアレンジみたいな奴？なの？解法分からず。
そもそもハノイの塔解いた事ない。これ解けないというのはまずいと思う。

5. AOJ 0504 Card Game II

404 Not Found
解法分からず。最後まで読んだらシミュレーション問題じゃなくて確率問題だった。
確率とか俺を殺す気か！