kmjp's blog

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

April Fools Day Contest 2016 : A. Da Vinci Powers、B. Scrambled、C. Without Text、D. Rosetta Problem

今回余り楽しめなかった…。問題の詳細は省いて、解答だけさらっと書きます。
http://codeforces.com/contest/656

A. Da Vinci Powers

Googleで検索しても良くわからないが、OEISでda vinciで調べると以下のエントリが出てくる。
A221180 - OEIS
2の累乗を並べた数列だが、1か所誤りがあるようだ。これを答えればよい。

ll L[] = {
1,
2,
4,
8,
16,
32,
64,
128,
256,
512,
1024,
2048,
4096,
8092,
16184,
32368,
64736,
129472,
258944,
517888,
1035776,
2071552,
4143104,
8286208,
16572416,
33144832,
66289664,
132579328,
265158656,
530317312,
1060634624,
2121269248,
4242538496,
8485076992,
16970153984,
33940307968,
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>i;
	cout<<L[i]<<endl;
}

B. Scrambled

単語内のアルファベットの並び順が1単語1文字対入れ替わっているので、推測で戻しながら読んで行こう。
2つの数列M[i],R[i]がある。任意の非負整数Dを等確率で選ぶとき、D mod M[i] = R[i]となるiの存在確率を求める。
M[i]の上限が16なので、Dに対するiの存在有無は最大でも(1~16の最小公倍数)の周期でループするので、1周分総当たりすればよい。

int N;
int R[16],M[16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll a=1;
	for(i=1;i<=16;i++) {
		ll g=__gcd(a,(ll)i);
		a=a/g*i;
	}
	
	cin>>N;
	FOR(i,N) cin>>M[i];
	FOR(i,N) cin>>R[i];
	
	int is=0;
	FOR(i,a) {
		int ok=0;
		FOR(j,N) if(i%M[j]==R[j]) ok=1;
		is+=ok;
	}
	_P("%.12lf\n",is*1.0/a);
	
}

C. Without Text

図を読み解くと、アルファベット大文字に対してアルファベットの番号を足し、小文字に対しては引く事を繰り返せばよいことがわかる。

string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int res=0;
	cin>>S;
	FORR(c,S) {
		if(c>='A'&&c<='Z') res+=c-'A'+1;
		if(c>='a'&&c<='z') res-=c-'a'+1;
	}
	cout<<res<<endl;
}

D. Rosetta Problem

問題文が難読言語で書かれているので、以下の記載を参考にインタープリタを探し、問題文を読み解こう。
http://Esoteric programming language
絵となっている部分は、実行環境によっては1/5に縮小する必要があるので注意。
問題文は「入力を8進数表記したとき1は何個あるか」である。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>i;
	j=0;
	while(i) {
		if(i%8==1) j++;
		i/=8;
	}
	cout<<j<<endl;
}

まとめ

うーん。

広告を非表示にする