日記 - binzume.net

int calc(int a,int b, int c) {
	for (int i=1;i<=c;i++) {
		mm[0][i] = a%i;
	}
	int aa = a;
	for (int i=1;i<=b;i++) {
		for (int tc=1;tc<=c;tc++) {
			int ta = mm[i-1][tc];
			auto cc = n(ta,tc);
			int r = mm[i-1][cc.second];
			r = (r-cc.first + cc.second) % cc.second + cc.first;

			if (aa < tc) r = aa;
			mm[i][tc] = modpow(ta,r,tc);
		}
		
		if (aa <= 1000) {
			int td = aa;
			aa = 1;
			for (int tt=0;tt<td;tt++) {
				if (aa > 1000) break;
				aa*=td;
			}
		}
	}
	return mm[b][c];
}

A(small+large),B(small+large),C(small),D(small)あたりが出来れば良かったんだけどなぁ．

Dのlargeもよく考えたらクローゼットのサイズ2x1だしマップは5列かないし， 2行ずつ決めてけば大丈夫だな…．

2011-10-08

12時半くらいに起きて，コンビニ行ってcode jam．

掃除とか洗濯とかしておく．

眠いので夕方寝たら今日が終わっていた．

LenovoでノートPC買おうと思ったのだけど，最後の注文ボタンを押すとエラーになってしまって買えない……． Javaの例外クラス名がそのまま出るのってどうなんだろ？

Google Code Jam Japan 2011

http://code.google.com/codejam/japan/

眠い．そして微妙． 69位なので一応Tシャツはもらえる？

Aをやる→なぜか答え合わない
Bをやる→意外と面倒で嵌る
Aをやる→通った
Bのデバッグ＞どこ間違ってるのか分からず
順位が200位ギリギリな事に気づいてCのsmallだけやる
Bを書き直してみる…が残り時間が無いのでDに
Dのsmallだけ解こうとする＞あとちょっとのところで終了

問題Bに3時間中1時間半以上使ってしまった． Dはたぶん解けると思ったのに，ぜんぜん時間が足りなかった．

何かやろうとする度に，自分の想像以上にプログラム書けなくなってるのがとても気がかり．分かっていたけど，仕事してコード書いた気になっているのがいけない気がする……．

A

最初， t1>=t2 の条件を間違っていていた．面積の差とかを比較してたけど，よく考えたら大きい三角形を順番に作っていくだけで良かった．

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
	int T;
	cin >> T;
	
	for (int i=0;i<T;i++) {
		int k;
		cin >> k;
		
		vector<int> ee;
		for (int j=0;j<k;j++) {
			int e;
			cin >> e;
			ee.push_back(e);
		}
		
		sort(ee.begin(),ee.end());

		double a = 0.0;
		
		int t1 = ee.back();
		int t2 = ee.back();
		ee.pop_back();

		double sindeg = sin(2* 3.141592653589793 / k);
		while (ee.size()) {
			if (t1>=t2) {
				a += t1*ee.back()*sindeg /2;
				t1 = ee.back();
			} else {
				a += t2*ee.back()*sindeg /2;
				t2 = ee.back();
			}
			ee.pop_back();
		}
		a += t1*t2*sindeg /2;
		

		cout << "Case #" << (i+1) << ": "<< setprecision(10) << a << endl;
	}

	return 0;
}

B

3時間中2時間使ってしまった…．そして，結局出来なかった．

A^x mod C の周期を計算すれば簡単に解けると思ったけど，意外と面倒なことに．

最初C++で書いていたけど，rubyならsmallは多倍長整数仕えれば楽だなと思ってちょっと書いたけど，smallだけやっても仕方ない気がして途中で引き返す．

終了後に，試しにsmallだけ解けるように書き直してみたけど，まだどこか怪しい．他の人のプログラムの出力とのdiff取ったら，なぜか500個中1個だけ出力が違ったので，何か特殊な場合を見逃してたっぽいなぁ．

一応書きかけのコード貼り付けておくけど，正しい答えが出ないです．

#include <iostream>
#include <map>
using namespace std;

typedef pair<int,int> CC;

CC n(int a,int m) {
	int cycle[1024]={0};
	int p=0;
	int t = 1;
	for(;;) {
		if (cycle[t]) return CC(cycle[t]-1,p-cycle[t]+1);
		cycle[t] = p + 1;
		t = t*a%m;
		p++;
	}
}

int modpow(int a,int p,int m) {
	int t = 1;
	// fixme
	for (int i=0;i<p;i++) {
		t = t * a % m;
	}
	return t;
}

int mm[1024][1024];

int calc(int a,int b, int c) {
	if (b == 1) return modpow(a,a,c);
	if (b == 2) {
		// bug...
		int tt = modpow(a,a,c);
		auto cc = n(tt,c);
		int r = modpow(a,a,cc.second);
		r = (r+cc.second-cc.first) % cc.second + cc.first;
		//int p = modpow(tt,cc.first,c);
		//cout << p  << ","<< cc.first << "," << cc.second << endl;
		//cout << r1 << a << endl;

		return modpow(tt,r,c);
	}
	
	for (int i=0;i<1024;i++) {
		for (int j=0;j<1024;j++) {
			mm[i][j]=-999;
		}
	}
		
	return mm[b][c];
}

int main() {
	int T;
	cin >> T;

	for (int i=0;i<T;i++) {
		int a,b,c;
		cin >> a >> b >> c;

		int ans = calc(a,b,c);;
		cout << "Case #" << (i+1) << ": " << ans << endl;
	}

	return 0;
}

C

smallだけ．largeは実装に時間かかりそうなのであきらめて無心で．

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

bool match(const char *a,const char *b,long long mask) {
	if (*a == 0 && *b == 0) return true;

	if (mask&1) { // *
		mask >>= 1;
		a++;
		if (match(a,b,mask)) return true;
		while(*b) {
			b++;
			if (match(a,b,mask)) return true;
		}
		return false;
	}
	if (*a == *b) {
		return match(a+1,b+1,mask>>1);
	}

	return false;
}

int count(long long mask){
	int c = 0;
	while (mask) {
		if (mask&1) {
			c++;
			mask >>= 1;
			while(mask&1) {
				mask >>= 1;
			}
		} else {
			mask>>=1;
		}
	}
	return c;
}

string mk(string a,long long mask) {
	string s;
	auto p = a.begin();
	while (p != a.end()) {
		if (mask&1) {
			s.push_back('*');
			++p;
			mask >>= 1;
			while(mask&1 && p != a.end()) {
				mask >>= 1;
				++p;
			}
		} else {
			s.push_back(*p);
			mask>>=1;
			++p;
		}

	}
	return s;
}

// a:old b:new
bool comp(string a,string b) {
	if (a.size() < b.size()) return false;
	if (a.size() > b.size()) return true;
	
	int ca=0,cb=0;
	for (auto p = a.begin();p!=a.end();++p) {
		if (*p == '*') {
			ca++;
		} 
	}
	for (auto p = b.begin();p!=b.end();++p) {
		if (*p == '*') {
			cb++;
		} 
	}
	if (cb>ca) return false;
	if (cb<ca) return true;
	
	auto ap = a.begin();
	auto bp = b.begin();
	while(ap!=a.end()) {
		if (*ap > *bp) return true;
		if (*ap < *bp) return false;
		++ap; ++bp;
	}
	return true;
}

int main() {
	int T;
	cin >> T;
	
	for (int i=0;i<T;i++) {
		string a,b;
		cin >> a >> b;
		
		int n = 1 << a.length();
		string s = a;
		for (long long mask=0;mask<n;mask++) {
			if (!match(a.c_str(),b.c_str(),mask)) {
				string t = mk(a,mask);
				if (comp(s,t)) {
					s = t ;
					//cout << mask << " " << s << endl;
				}
			}
		}

		cout << "Case #" << (i+1) << ": " << s << endl;
	}

	return 0;
}

D

smallだけならギリギリ書けると思ったけど，提出する前に時間切れに…．もう10分早くBを諦めるべきだった．

smallだけなら，総当りで簡単に解けるサイズなので問題ない． largeは一生懸命枝を刈ればどうにかなるのか，頭の良いアルゴリズムがあるのかよく分からない．

#include <iostream>
using namespace std;

int w,h;
char map[40][10];
char map2[40][10];

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

int check_rest = 0;

bool check_(int x,int y) {
	char t=map2[y][x];

	if (t=='D') check_rest--;
	map2[y][x] = 'X';
	if (check_rest==0) return true;
	
	for (int i=0;i<4;i++) {
		if (map2[y+dy[i]][x+dx[i]]=='X') continue;
		check_(x+dx[i],y+dy[i]);
	}
	return check_rest==0;
}

bool check() {
	int xx=0, yy=0, rest=0;
	for (int y = 0; y<= h+1; y++ ) {
		for (int x = 0; x<= w+1; x++ ) {
			map2[y][x] = map[y][x];
			if (map[y][x]=='D') {
				yy=y;xx=x;
				rest++;
			}
		}
	}
	check_rest = rest;
	return check_(xx,yy);
}

int solv(int x, int y) {
	x++;
	if (x>w) {x=1;y++;}
	if (y>h) return 0;

	int max = 0;
	if (map[y][x] == '.') {
		map[y][x] = 'X';
		for (int i=0;i<4;i++) {
			if (map[y+dy[i]][x+dx[i]] != '.') continue;
			char tt = map[y+dy2[i]][x+dx2[i]];
			if (tt == 'X') continue;
			map[y+dy[i]][x+dx[i]] = 'X';
			map[y+dy2[i]][x+dx2[i]] = 'D';
			if(check()) {
				int t = solv(x,y) + 1;
				if (t>max) {
					max = t;
				}
			}
			map[y+dy[i]][x+dx[i]] = '.';
			map[y+dy2[i]][x+dx2[i]] = tt;
		}
		map[y][x] = '.';
	}

	int t = solv(x,y);
	if (t > max) {
		max = t;
	}
	return max;
}

int main() {
	int T;
	cin >> T;
	
	for (int i=0;i<T;i++) {
		cin >> h >> w;

		for (int y = 0; y<= h+1; y++ ) {
			for (int x = 0; x<= w+1; x++ ) {
				map[y][x] = 'X';
			}
		}
		for (int y = 1; y<= h; y++ ) {
			for (int x = 1; x<= w; x++ ) {
				cin >> map[y][x];
			}
		}
		int a = solv(0,1);

		cout << "Case #" << (i+1) << ": " << a << endl;
	}

	return 0;
}

E

無限平面を埋め尽くすパターンといえばヒルベルト曲線が有名で，説明の図もヒルベルト曲線の一部に見えないことも無いけれど，問題読んだだけで考えてない．

条件と雰囲気からフラクタル的な図形になるのは間違い無さそうなので，うまくすれば長さが一気に出せそう．

2011-10-07

明日から三連休だけど予定が埋まってて憂鬱になる．べつに嫌なことをするわけでもないのに，予定表に何か書かれていると憂鬱になる病気なのかも．

2011-10-06

会社いったら，もうほとんど人がいなかったので神保町へ．

カレー食べる．

会社に戻る帰りに，秋葉原寄ってスーツ受け取る．

2011-10-05

雨．

色々忙しい．

2011-10-04

cssとHTML書いたりした．

スマートフォン用のcssに切り替えるのは，max-widthの値とかじゃなくて，ポインティングデバイスが何なのかで切り替えたい．一応，Firefoxには -moz-system-metric(touch-enabled) みたいなのがあるみたいだけど，他のブラウザもやってくれないかなぁ．

2011-10-03

眠い…．

2011-10-02

最近，休みはいつも秋葉原にいる気がするけど，気のせいだと思いたい．

夜はgotoと秋葉原のルノアールに行って，コード書いたりする．

ルンバで遊ぶ予定だったけど，結局触れなかった…．

2011-10-01

Code Jamやったり，服買ったりする日．

Google Code Jam Japan 2011 予選

Tシャツ欲しいのでやりました．

https://code.google.com/codejam/japan/

この日記読んでも雰囲気が伝わるかすら怪しいので，気になる人は自分で問題読むことをお勧めします．問題はcode jamのサイトで誰でも見れます．

13時開始だったけど，目が覚めて時計を見ると14時過ぎ……．まだ眠かったけど，14:20くらいに問題読み始める．

予選なので問題は簡単．しかも日本語だし楽勝．と思ったけど，Bで結構時間かかってしまった．

終わったのが15:48．

コンテスト終了後にスコア見たけど，全問大丈夫だった．始めたのが遅かったので順位は56位．来週も頑張れば一応Tシャツもらえそうだな．

A イカサマシャッフル

カードを指定された通りにシャッフルした場合，ある場所のカードが元々どこにあったかを答える問題．

カードの枚数が，10億(10^9)枚まであり得るので，実際にカードに番号を振って操作するのは危険．ただ，答えるのは指定された１枚なので，シャッフルが終わった状態から逆順に辿れば簡単．

最初に1引いておいて最後に1足しているのは，カードの番号が1から始まるのが気持ち悪かったからってだけです．

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

int main() {
	int T;
	cin >> T;
	
	for (int i=0;i<T;i++) {
		int m,c,w;
		cin >> m >> c >> w;
		
		vector<int> aa,bb;
		for (int j=0;j<c;j++) {
			int a,b;
			cin >> a >> b;
			aa.push_back(a-1);
			bb.push_back(b);
		}
		
		w -= 1;
		while (aa.size()) {
			int a = aa.back();
			int b =  bb.back();
			aa.pop_back();
			bb.pop_back();

			if (w<b) {
				w += a;
			} else if (w < a+b) {
				w -= b;
			}
		}

		cout << "Case #" << (i+1) << ": " << w+1 << endl;
	}

	return 0;
}

B 不老不死な人のコーヒーの悩み

複数種類のコーヒーについて，賞味期限と満足度と何杯分飲めるかが与えられて，１日一杯ずつ飲んだときの，満足度の合計の最大値を求める問題．

しかし，２兆(=2*10^12)日くらいコーヒーを飲み続ける不老不死な人が抱える問題のようなので32ビット整数に収まらないし， 1日ごとに計算してたら間に合わない気がします．

２兆日っていうと，そろそろ太陽が燃え尽きて地球が無くなってるころですね．確かにたとえ不老不死であっても地球が無いとコーヒー飲んでる場合ではない……．

特に方針を決めないまま書き始めたら，少し面倒なプログラムになってしまった．コーヒーを飲むことが出来なくなる最期の日から，まだ飲めるコーヒーのうち満足度が最大なものを調べて，その前に賞味期限が切れるコーヒーと比べつつ，どの期間にどのコーヒーを飲むか決めるだけのプログラム．

事前に賞味期限と満足度でソートしたほうが多少短くなったかも．

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

int main() {
	int T;
	cin >> T;
	
	for (int i=0;i<T;i++) {
		unsigned long long n,k;
		cin >> n >> k;
		
		struct Coffee {
			unsigned long long c,t;
			int s;
		};
		vector<Coffee> cc;
		for (int j=0;j<n;j++) {
			Coffee c;
			cin >> c.c >> c.t >> c.s;
			cc.push_back(c);
		}
		
		unsigned long long d = k;
		long long ss = 0;
		while (d>0) {
			int ms = 0;
			int pos = 0;
			for (int j=0;j<n;j++) {
				if (cc[j].c > 0 && cc[j].t>=d && cc[j].s > ms) {
					ms = cc[j].s;
					pos = j;
				}
			}

			if (ms==0) {
				unsigned long long  md = 0;
				for (int j=0;j<n;j++) {
					if (cc[j].c > 0 && cc[j].t < d && cc[j].t>md ) md = cc[j].t;
				}
				d = md;
				continue;
			}

			unsigned long long dd = d ,md = 0;
			for (int j=0;j<n;j++) {
				if (cc[j].c > 0 && cc[j].t<d && cc[j].t> md) {
					dd = d-cc[j].t;
					md = cc[j].t;
				}
			}
			
			if (dd > cc[pos].c) {
				dd = cc[pos].c;
			}
			if (dd > d) {
				dd = d;
			}
			
			ss += cc[pos].s * dd;
			cc[pos].c -= dd;
			d-=dd;
		}
		
		cout << "Case #" << (i+1) << ": " << ss << endl;
	}

	return 0;
}

C 64ビット整数扱えない言語とかもう使ってないよね？

整数 N が与えられて，a+b=N を満たす 0 以上の整数 a,b を選んで， aとbを２進表記した場合に1がたくさん含まれるようにする問題．

二進法の計算できるかというだけ？

A～Cの中で妙に簡単というか，本当にこれで良いのか疑って問題を何度も見直してしまった．

#include <iostream>
using namespace std;

int main() {
	int T;
	cin >> T;
	
	for (int i=0;i<T;i++) {
		int b = 0;
		unsigned long long n;
		for (cin>>n;n;n >>=1) {
			if ((n&1) == 0) {
				n--;
				b++;
				if (n&1) b++;
			} else {
				b++;
			}
		}
		cout << "Case #" << (i+1) << ": " << b << endl;
	}

	return 0;
}

秋葉原

結婚式に着ていく礼服を買うために，秋葉原のAOKIに．

よく分からないので，店員に薦められるまま一式買う．結局８万くらいかかってしまったけど，どうなんだろ？

木曜日に出来るらしいので，取りに行かないと．

肉食べた．

Sun	Mon	Tue	Wed	Thu	Fri	Sat
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31