ACM-ICPC

ICPC Domestic 2010 Problem A: 角角画伯，かく悩みき

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1165&lang=jp

説明

入力と同時に下端・上端・左端・右端を更新していき，過去のタイル情報はtable[id]に入れるといいです．

Thanks: @mitsuchie

ソース

#include <iostream>
#include <cstring>
#include <set>
using namespace std;
 
typedef pair<int,int> pii;
 
#define N 400
pii table[N];
int l, r, t, bo;
int main(){
	int n;
	while(cin >> n && n){
		r = bo = N/2;
		l = t = N/2;
		table[0] = pii(N/2, N/2);
		for(int i=1; i<n; i++){
			int id, an;
			cin >> id >> an;
			int x = table[id].first;
			int y = table[id].second;
			if(an == 0){
				table[i] = pii(x-1, y);
				if(x-1 < l){
					l = x-1;
				}
			}
			if(an == 1){
				table[i] = pii(x, y-1);
				if(y-1 < t){
					t = y-1;
				}
			}
			if(an == 2){
				table[i] = pii(x+1, y);
				if(x+1 > r){
					r = x+1;
				}
			}
			if(an == 3){
				table[i] = pii(x, y+1);
				if(y+1 > bo){
					bo = y+1;
				}
			}
		}
		cout << r - l+1 << " " << bo - t +1 << endl;
	}
 
	return 0;
}

ICPC Domestic 2010 Problem B: 迷図と命ず

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp

説明

壁情報を1つのマスに記録するために，迷路を縦横2倍に拡大します． 拡大すると経路の長さがおかしくなりますが，本来床だった場所にマークを付けておいて， そのマークを踏んだ時だけ移動距離をカウントするようにすると楽です． 迷路のテーブルを作り終わった後はBFSするだけです．

Thanks: @mitsuchie

ソース

#include <iostream>
#include <cstring>
#include <set>
using namespace std;
 
#define N 60
int w, h;
 
char table[N][N];
 
void view(){
	for(int y=0; y<2*h; y++){
		for(int x=0; x<2*w; x++){
			cout << table[y][x];
		}
		cout << endl;
	}
	cout << endl;
}
 
int main(){
	while(cin >> w >> h && (w|h)){
		memset(table, '*', N*N*sizeof(char));
		for(int y=0; y<h; y++){
			for(int x=0; x<w; x++){
				table[y*2][x*2] = '0';
			}
		}
		//view();
		for(int y=0; y<h; y++){
			// yoko kabe
			int in;
			for(int x=0; x<w-1; x++){
				cin >> in;
				//table[y][x] = '+';
				table[2*y+0][2*x+1] = in ? '*' : '+';
			}
			// tate kabe
			if(y == h-1){
				table[2*y+1][2*w-2] = '+';
			}else{
				for(int x=0; x<w; x++){
					cin >> in;
					table[2*y+1][2*x+0] = in ? '*' : '+';
				}
			}
		}
		//view();
 
		bool isCleared = false;
		typedef pair<int,pair<int,int> > pii;
		set<pii> s;
		s.insert(pii(1, make_pair(0, 0)));
		while(!s.empty()){
			int c = 0;
			int n = (*s.begin()).first;
			int x = (*s.begin()).second.first;
			int y = (*s.begin()).second.second;
			s.erase(s.begin());
 
			if(x<0 || y<0 || table[y][x]=='*') continue;
			if(x==2*w-2 && y==2*h-2){
				cout << n << endl;
				isCleared = true;
				break;
			}
 
			if(table[y][x] == '0'){
				c++;
			}
			table[y][x] = '*';
			s.insert(pii(n+c, make_pair(x+1, y)));
			s.insert(pii(n+c, make_pair(x-1, y)));
			s.insert(pii(n+c, make_pair(x, y+1)));
			s.insert(pii(n+c, make_pair(x, y-1)));
		}
		if(!isCleared)
			cout << 0 << endl;
	}
 
	return 0;
}

JAG Domestic 2009 Problem A: Luck Manipulator

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2149

説明

リール情報をキューに入れると良いです．

ソース

#include <iostream>
#include <queue>
using namespace std;
 
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)
#define MX 10000
int n, a, b, c;
 
int main(){
	int x;
	while(cin>>n>>a>>b>>c>>x && n){
		queue<int> q;
 
		rep(n){
			int in;
			cin >> in;
			q.push(in);
		}
 
		int i;
		for(i=0; i<=MX; i++){
			if(x == q.front()){
				q.pop();
			}
			if(q.empty()){
				break;
			}
			x = (a*x + b) % c;
		}
 
		if(i > MX){
			cout << -1 << endl;
		}else{
			cout << i << endl;
		}
	}
 
	return 0;
}

JAG Domestic 2009 Problem D: Restrictive Filesystem

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2152

説明

「何これ簡単じゃん！」かと思いきや，記憶媒体をint[10^9]などの配列で表すとメモリ容量は4Gbyte必要なのでどう頑張っても無理です． データ構造を工夫する必要があって，私はデータのセクタ番号（id）とその繰り返し回数(times)を持つDataクラスを作ってlistに入れて実装しました．

ソース

#include <iostream>
#include <list>
using namespace std;
 
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)
#define FOREACH_RANGE(it,s,e) for(typeof(s)it=s;it!=e;++it)
#define FOREACH(it,c) FOREACH_RANGE(it,(c).begin(),(c).end())
#define foreach(c) FOREACH(it,c)
#define foreach_range(s,e) FOREACH_RANGE(it,s,e)
 
#define MAX 1000000000
 
class Data {
public:
	int id, times;
	Data(int id, int times){
		this->id = id;
		this->times = times;
	}
	void put(){
		cout << id << " " << times << endl;
	}
};
int main(){
    int n;
    while(cin>>n&&n){
        list<Data> t;
        t.push_back(Data(-1, MAX+1));
 
        rep(n){
            string in;
            cin >> in;
            if(in == "W"){
                int out, c;
                int p = 0;
                cin >> out >> c;
				for(list<Data>::iterator it = t.begin(); ; it++){
					if((*it).id == -1){
						if(c >= (*it).times){
							(*it).id = out;
							c -= (*it).times;
						}else{
							int space = (*it).times;
							list<Data>::iterator next = it;
							advance(next, 1);
							t.erase(it);
							t.insert(next, Data(out, c));
							if(space-c > 0){
								t.insert(next, Data(-1, space-c));
							}
							it = next;
							c = 0;
						}
						if(c<=0) break;
					}
				}
            }else if(in == "D"){
                int a;
                cin >> a;
				foreach(t){
					if((*it).id == a){
						(*it).id = -1;
					}
				}
            }else if(in == "R"){
                int a;
                cin >> a;
				int pos = 0;
				foreach(t){
					pos += (*it).times;
					if(a < pos){
						cout << (*it).id << endl;
						break;
					}
 
				}
 
            }
        }
        cout << endl;
    }
 
    return 0;
}

JAG Domestic 2011 Problem A: koukyoukoukokukikou

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2252

説明

xor を使うと簡潔になります．

Thanks:@cq_71

ソース

#include <iostream>
#include <string>
using namespace std;
 
#define REP(i,p,n) for(int i=(int)p;i<(int)n;++i)
#define rep(i,n) REP(i,0,n)
 
bool isLeft(char c){
	if(c == 'q' || c == 'w' || c == 'e' || c == 'r' || c == 't' ||
		c == 'a' || c == 's' || c == 'd' || c == 'f' || c == 'g' || 
		c == 'z' || c == 'x' || c == 'c' || c == 'v' || c == 'b'){
		return true;
	}
	return false;
}
 
int main(){
	string in;
	while(cin >> in && in != "#"){
		int count = 0;
		rep(i, in.size()-1){
			count += isLeft(in[i]) ^ isLeft(in[i+1]);
		}
		cout << count << endl;
	}
 
	return 0;
}

JAG Domestic 2011 Problem B: Brave Force Story

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253

説明

難易度の割に正答率が低くて意外に思うかもしれませんが， 「障害物の座標x, yの絶対値が30以下」という文章につられてフィールドを狭く取りがちです． 私は実際の答えよりも少ない数値が出力されるミスの原因になかなか気づけませんでした・・・

ソース

#include <iostream>
#include <algorithm>
#include <limits>
#include <queue>
#include <cstring>
using namespace std;
 
#define D(c) cout<<#c<<" = "<<c<<endl
#define REP(i,p,n) for(int i=(int)p;i<(int)n;++i)
#define rep(i,n) REP(i,0,n)
 
#define N 2000
char table[N][N];
 
 
class Point {
public:
	int x, y, t;
 
	Point(int x, int y, int t){
		this->x = x;
		this->y = y;
		this->t = t;
	}
};
 
queue<Point> q;
 
void tableInit(){
	memset(table, ' ', sizeof(table));
 
	// 番兵
	rep(x, N) {
		table[0][x] = '*';
		table[N-1][x] = '*';
	}
	rep(y, N) {
		table[y][0] = '*';
		table[y][N-1] = '*';
	}
 
	rep(i, N/2){
		table[i][N/2-1+i] = '*';
		table[N/2-1+i][i] = '*';
	}
}
 
void showTable(){
	rep(y, N){
		rep(x, N){
			printf("%c", table[y][x]);
		}
		printf("\n");
	}
	printf("\n");
}
 
char get(int x, int y){
	return table[y+N/2][x+N/2];
}
 
void set(int x, int y, char c){
	table[y+N/2][x+N/2] = c;
}
 
void fill(int x, int y, int t){
	if(get(x, y) == '*') return;
	set(x, y, '.');
	if(t == 0) return;
	fill(x+1, y, t-1);
	fill(x+1, y+1, t-1);
	fill(x, y+1, t-1);
	fill(x-1, y, t-1);
	fill(x-1, y-1, t-1);
	fill(x, y-1, t-1);
}
 
int count(){
	int count = 0;
	rep(y, N){
		rep(x, N){
			if(table[y][x] == '.') count++;
		}
	}
	return count;
}
 
void pushIfOk(int x, int y, int t){
	if(get(x, y) == '*' || get(x, y) == '.') return;
	q.push(Point(x, y, t));
	set(x, y, '.');
}
 
int main(){
	int t, n;
	while(cin >> t >> n){
		if(t == 0 && n == 0) break;
		tableInit();
 
		rep(blockCount, n){
			int x, y;
			cin >> x >> y;
			set(x, y, '*');
		}
		//showTable();
 
		int sx, sy;
		cin >> sx >> sy;
		pushIfOk(sx, sy, t);
 
		while(q.size() > 0){
			Point p = q.front();
			q.pop();
			if(p.t == 0) continue;
 
			pushIfOk(p.x+1, p.y, p.t-1);
			pushIfOk(p.x+1, p.y+1, p.t-1);
			pushIfOk(p.x, p.y+1, p.t-1);
			pushIfOk(p.x-1, p.y, p.t-1);
			pushIfOk(p.x-1, p.y-1, p.t-1);
			pushIfOk(p.x, p.y-1, p.t-1);
 
			//showTable();
		}
 
		//showTable();
		cout << count() << endl;
 
	}
 
	return 0;
}

JAG Domestic 2011 Problem C: 最短ルート

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254

説明

私は最初，愚直に全探査するなかなか計算が終わらないプログラムを書いてしました． ビットDPを使うべきです（詳しくはアリ本や http://www.slideshare.net/iwiwi/ss-3578511 に載っています）．

ソース

#include <iostream>
#include <algorithm>
#include <limits>
#include <cstring>
using namespace std;
 
#define D(c) cout<<#c<<" = "<<c<<endl
#define REP(i,p,n) for(int i=(int)p;i<(int)n;++i)
#define rep(i,n) REP(i,0,n)
#define MAX_N 16
#define INF 1100000000
 
int n;
int d[MAX_N][MAX_N+1];
int dp[1 << MAX_N][MAX_N];
 
int searchMin(int S, int v){
	// 入手可能な装備で一番コストが低いものを探して返す
	if(S == 0 && v == 0) return 0;
	int min = d[v][0];
	rep(i, n){
		if(i == v){
			continue;
		}
		if((S >> i) & 1){
			int cost = d[v][i+1];
			if(cost < min){
				min = cost;
			}
		}
	}
	return min;
}
 
// 既に訪れた点がS, 現在位置がv
// Sの下位からnビット目が1なら，既にステージn+1に訪れた事を意味する
int rec(int S, int v){
	if(dp[S][v] >= 0){
		return dp[S][v];
	}
 
	int nowCost = searchMin(S, v);
 
	// すべての頂点を訪れ終えた
	if(S == (1 << n) - 1){
		return dp[S][v] = nowCost;
	}
 
	int res = INF;
	rep(u, n){
		if(!(S >> u & 1)){
			// 次のuに移動 & 最小コストを更新
			res = min(res, rec(S | 1 << u, u) + nowCost);
		}
	}
	return dp[S][v] = res;
}
 
int main(){
	while(cin>>n&&n){
		memset(dp, -1, sizeof(dp));
		int in;
		rep(y, n){
			rep(x, n+1){
				cin >> in;
				d[y][x] = in;
			}
		}
 
		cout << rec(0, 0) << endl;
	}
 
	return 0;
}