UVa - 7th Contest of Newbies

年越しコンテスト(12/31 21:00 ~ 01/01 1:00)参加してきました。

どこがNewbiesやねん・・・。

蕎麦食ったりしつつも真面目に参加していて、結果としては5位/114人でした。とりあえず３時間だと思ったら４時間で、残り１問解けそうで解けない感じだったのでぼーっとしていた。


問題

こちら(UVaに接続できない場合はいろいろブラウザ変えてみると良いかも。)

A Roman Numerals

  • A読む。なんかローマ数字がかいてある・・・。
  • ローマ数字ってルールよく分からないし自分で実装したこと実はないんだよね・・・でDに逃げる。
  • ↑をするも20分くらい考えて良い方法が思いつかなかったので戻ってくる。
  • ローマ数字のルールをWikipedia等で見つつ実装してみる→ただの貪欲やん。となる。
  • 書けた。提出してみる。→WA
  • なんでだろうと思いつつ、制約を見てみるとICという表記は駄目らしい。ルールをもっかい見てみると何やら僕は90とかをICだと思っていたらしい(本当はXC)。偶然気づけたからよかったけど、常識ないにもほどがある。
  • その後提出。→AC(1WA)

B NumPuzz I

  • 題意がよく分からないけど一見ライツアウトっぽいやつかな？と思ったら全然違った。サンプルから推測するに十字に足していくシミュレーションするだけっぽい？
  • 書けた。提出してみる。→WA
  • え・・・題意理解できてない？あ、10でmod取るのか。
  • 提出→AC(1WA)

C NumPuzz II

  • さっきの逆バージョン。盤面を0にする最適解を見つけるらしい。ああなるほど、こっちがライツアウトもどきか。
  • とりあえず上３列を１０＾３で探索したらあとは一意に定まるので書く。実装だるい。
  • これ合ってて最短ならどんな解出してもいいんだよね？とか思いながら提出。→すんなりAC

D 3, 2, 1, 0

  • 「2,3を使って、2進表現でleading-zeroがk個以上になるような最小のk桁の10進数を作りなさい。」という問題。
  • 開幕見るも解けそうで解けない感じ。
  • 全部列挙してみて法則性を見るも不規則なように見える。悩む。
  • 例えば10進表現で4桁の数字(abcd)は1000a+100b+10c+dと表せることが使えそうだと思いつつも、やっぱりあまり役立たなさそうだったので、実験と思考をしまくって1時間くらい経過。
  • 再度さっきの式で考えてみる。
例えば、4桁の数字abcdがあったとして、1000a+100b+10c+dで表せるとすると、

1桁目であるd=2でないといけない。(自明)

2桁目について同様に考えてみると、

d=2なら、先ほどの式は2でくくれるので、
2 * (500a+50b+5c+d/2)
で表すことができて、
さらに、5c以外は偶数で、括弧の中を偶数にするには5c+d/2を偶数にしなければいけないので、2か3を上手く割り振る。
(この時はc=3の時だけ5c(奇数)+d/2(奇数) = (偶数)で成り立つ。)

同様に操作を繰り返していくと、割とよさそうな戦略となる。

あとそれで作った値が達成できれば桁数以上には確実に出来る。
  • だけど、"k以上のleading-zeroで最小の数を出力しろ"なのでこれが最適な戦略とは限らないし、2^5=32みたいに、2桁なのに5回leading-zeroするような数があったら(=その桁で条件を達成できる出力が一意でない場合)、WAしてしまう・・・。
  • とりあえずその場合どうしようもなくて僕の解法は破綻するので、一意に定まることを仮定してみることにした。
  • とりあえず途中計算(5^n計算する)に多倍長が必要なのでjavaで書いていたものを提出。→ＴＬＥ
  • おうふ・・・。ＴＬＥか。ＷＡじゃないだけ良かった。
  • n桁での最適解は(n-1)桁での最適解に2か3を頭に加えたものなので、予め文字列にして埋め込んでおけばよいか。→Ｃ＋＋で書き直す。
  • 提出。→ＡＣ

  • めっちゃびっくり。思わずＴＬで叫んでしまう。

E Metal Powers

  • なんか３つ数式のn乗の整数部を求めて変な出力形式で出すの？
  • めんどくさそう・・・。
  • 下３桁は蟻本で見た！・・・それだけ。
  • とりあえず解く体力が無い上に、上３桁ってどうやって求めるんだろうなあと思いつつ悲しむ。数学力がない。

F Parallel Missions

  • あきらめ

結果

[A]00:27:33 (1)

[B]00:37:43 (1)

[C]00:56:32 (0)

[D]02:35:42 (2)

[E] -

[F] -

5位/114人(4完 ペナ05:57:30)

感想

5位わぁい。しかし残りの１時間は誰かに抜かされないことを祈るだけの時間だったのでよろしくない。

ソース

ローマ数字って難しいですネ。

A

string c[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int    v[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

string get(int n){
	string ans;
	while(n){
		for(int i = 0 ; ; i++){
			if(n >= v[i]){
				ans += c[i];
				n -= v[i];
				break;
			}
		}
	}
	return ans;
}
int table[128];
int main(){
	table['I'] = 1; table['V'] = 2;
	table['X'] = 2;	table['L'] = 2;
	table['C'] = 2;	table['D'] = 3;
	table['M'] = 4;
	int n;
	while(cin >> n){
		int ans = 0;
		string l = get(n);
		for(int i = 0 ; i < l.size() ; i++)
			ans += table[l[i]];
		cout << ans << endl;
	}
}

B

番兵とCR+LFに一応対応した。(ていうかローカルがCRLFなので不快)

int main(){
	int T = 0;
	string l;
	while(getline(cin,l)){
		T++;
		if(l[l.size()-1] == '\r') l = l.substr(0,l.size()-1);
		int w[5][5] = {};
		for(int i = 0 ; i < l.size() ; i++){
			int x = (l[i] - 'a');
			int y = 1 + x / 3;
			x = 1 + x%3;
			int dx[] = {-1,0,0,1,0};
			int dy[] = {0,-1,1,0,0};
			for(int d = 0 ; d < 5 ; d++){
				w[y+dy[d]][x+dx[d]]++;
			}
		}
		cout << "Case #" << T << ":" << endl;
		for(int Y = 1 ; Y <= 3 ; Y++)
			for(int X = 1 ; X <= 3 ; X++)
				cout << w[Y][X]%10 << (X==3?"\n":" ");
	}
}

C

急いで書いた(ただし20分くらいかかった)ので、すごく汚い。

int o[5][5];

int dx[] = {-1,0,0,1,0};
int dy[] = {0,-1,1,0,0};

int go(int a[5][5],int x,int y){
	for(int d = 0 ; d < 5 ; d++){
		a[y+dy[d]][x+dx[d]] = (a[y+dy[d]][x+dx[d]]+9)%10;
	}
}

string f(string ans,int p,int q,int r){
	int t[5][5];
	for(int i = 0 ; i < 5 ; i++)
		for(int j = 0 ; j < 5 ; j++) t[i][j] = o[i][j];
	rep(___,p)go(t,1,1);
	rep(___,q)go(t,2,1);
	rep(___,r)go(t,3,1);
	
	string ooo[] = {""," abc"," def"," ghi"};
	for(int i = 2 ; i <= 3 ; i++){
		for(int j = 1 ; j <= 3 ; j++){
			int need = t[i-1][j];
			rep(___,need) go(t,j,i);
			ans += string(need,ooo[i][j]);
		}
	}
	for(int i = 1 ; i <= 3 ; i++)
		for(int j = 1 ; j <= 3 ; j++)
			if(t[i][j]) return string(10000,'~');
	return ans;
}

int main(){
	int T = 0;
	while(1){
		string s; 
		if(!(cin >> s))break;
		cin >> s;
		for(int i = 1 ; i <= 3 ; i++){
			for(int j = 1 ; j <= 3 ; j++)
				cin >> o[i][j];
				
		}
		string answer = string(10000,'~');
		for(int p = 0 ; p < 10 ; p++){
			for(int q = 0 ; q < 10 ; q++){
				for(int r = 0 ; r < 10 ; r++){
					
					string get = f(string(p,'a')+string(q,'b')+string(r,'c'),p,q,r);
					if(get.size() < answer.size()){
						answer = get;
					}
				}
			}
		}
		if(answer.size() == 10000){
			cout << "No solution." << endl;
		}else{
			cout << answer << endl;
		}
	}
}

D

Dの答え求める部分ところ。あとはこれで出てきた結果を埋め込むだけなので。

BigInteger cur = new BigInteger("0");
BigInteger get = new BigInteger("0");
for(int i = 0 ; i < 1100 ; i++){
	BigInteger p = new BigInteger("5").pow(i);
	if(cur.mod(new BigInteger("2")).equals(new BigInteger("0"))){
		get = get.add(new BigInteger("2").multiply(new BigInteger("10").pow(i) ));
		cur = cur.add(p.multiply(new BigInteger("2")));
		cur = cur.divide(new BigInteger("2"));
	}else{
		get = get.add(new BigInteger("3").multiply(new BigInteger("10").pow(i) ));
		cur = cur.add(p.multiply(new BigInteger("3")));
		cur = cur.divide(new BigInteger("2"));
	}
}
System.out.println(get.toString());