kmjp's blog

競技プログラミング参加記です

UTPC 2013: A - UTPC、B - 13月

UTPC2013に参加。100点問題や部分点稼ぎはできたものの、200点クラスの問題が自力で解けず微妙な順位。
このあたり、自分の実力不足を感じるな…。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_01
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_02

A - UTPC

4文字のアルファベットで構成された文字列が与えられる。
"UTPC"と各文字の穴の数が一致するか答えよ。
実装するだけ。

void solve() {
	int f,i,j,k,l,x,y;
	char hoge[27]="12010000000000111100000000";
	y=1;
	string S;
	cin>>S;
	if(hoge[S[0]-'A']!='0') y=0;
	if(hoge[S[1]-'A']!='0') y=0;
	if(hoge[S[2]-'A']!='1') y=0;
	if(hoge[S[3]-'A']!='0') y=0;
	
	if(y==1) _P("yes\n");
	else _P("no\n");
}

B - 13月

ある暦では、2000+X年はXか月ある。
一般的な暦のY年Z月は、この暦の何年何月か答えよ。

ある年までの合計月数はYの二次式として簡単に求められる。
よって二次方程式を解くか二分探索で何年か求めればよい。

ll tot(ll Y) {
	return (13+Y-2000)*(Y-2013+1)/2;
}

void solve() {
	int f,i,j,k,l,x,y,z;
	ll Y,M;
	cin>>Y>>M;
	M=(Y-2013)*12+M-1;
	
	ll L=2013,R=1LL<<31;
	FOR(i,60) {
		ll p=(L+R)/2;
		if(tot(p)<M) L=p;
		else R=p-1;
	}
	for(L=max(L-3,2013LL);L;L++) {
		if(M-tot(L-1)<L-2000) return _P("%lld %lld\n",L,M-tot(L-1)+1);
	}
}

まとめ

ここまではまだ準備運動で簡単。

広告を非表示にする