Codeforces Beta Round #65 (Div. 2) - kyuridenamidaのブログ

Dashboard - Codeforces Beta Round #65 (Div. 2) - Codeforces

今回はHackしまくって遊ぶ暇はありませんでした。全くといっていいほど。

まあパープルなのでいつものようにUnratedなわけですが。

まあ、Eが落ちて3完。

開始前

自分のライブラリに繋がらなかったりする。まあいいやと思いながら開始。

[00:00] A読む。

サンプルをまず見る。

「abcdefghijk」みたいなのを「a9k」とかにする。やるだけじゃね。

→書く。文字が10以下ならそのままか・・・

→って、いやいや、これは間が2桁になるならそのままって意味だな！(謎の解釈)

→ログインしてねえ！急いでログインだ重い！！

[00:02] A Wrong answer on pretest 2

ありゃ。やっぱり駄目か。

→修正。

[00:03]A passed pretest(1WA)

-50痛い。

→とりあえずB読む。変な数式とかある。分からない。

→D読む。分からずにBに戻ってくる。

→とにかく分からない。

→サンプルインプットから想像。

→適当に書く。

→サンプル通った。提出。

[00:13]B passed pretest

もう一度D読もう。

→"Output any of them"が輝いているがソリティア嫌い。

→C見る。

→んー、円周上に均等に人が並んでる。機嫌の良い人だけ使って正n角形を作れればいいのかな？

→どう判定すればいいんだろう。幾何学？違うな。

→とりあえず点をほどいてみて、例えばn=6なら「*-*-*-」「******」の*の部分が全部機嫌良かったらいいんじゃね。(「*--*--」はむすんでみると三角形以上にならないので例外)

→とりあえず愚直にクソ汚いソースを実装。

[00:35]C Wrong answer on pretest 5

あれ、なんでだろ。

→考える。

→ああ、「-*-*-*」とかもありうる。回転考慮してなかった。

→修正して提出。

[00:39]C passed pretest

ふぅ・・・。通った。

→あれ？でも、n=100000なんとなく通る気がしていたけど、通らない気がしてきた。

→手元で最悪ケース試してみたら案の定通らない。

→どろどろした改善を試みるも死亡。

→なんか「*-*-*-」とかの間につかってる数は固定で、しかも少ない。

→じゃあ先に計算してそれだけ使えばいいんじゃね。ということでメモる。

→ぐちゃぐちゃになっているけど提出。

[01:04]C passed pretest(Resubmit+1WA)

なぜ通ったし。これテスト落ちそうだなー。まあいいやもう修正する気ない。

→Lockして他人のCの解法見る。

→あ、俺が先に計算してたアレって約数だったのか・・・・。(その時はじめて気づく)

→D読む。やっぱりわからないしソリティア嫌いとつぶやく。

→E読む。あ、ただのパズルだ解けそう。でも周期表・・・。

→仕方ないのでWikipediaから周期表を手動で丸写す。

[01:23]周期表うつしおわったー！

→とりあえず実装していく。

→bitとか使うと楽そう。

→かけた。サンプル通った。提出。

[01:37] E Wrong answer on pretest 1

あれ、落ちた？うそん。(pretest1=サンプルであることに気づいていない)

→もしかして周期表ミスってる？そんなはずは・・・。

→細部を修正するふりをして再提出。

[01:39] E Wrong answer on pretest 1

→いろいろよくわからない細部を修正してpretest1で弾かれる。(気づいていない)

[02:45] E Wrong answer on pretest 1

→くっそー、、、辛い。

→10分くらい放心状態になってから、"YES"という出力をしなければいけないことに気づく。

→うわああああああああああ。修正。

[01:54] E passed pretest(3WA)

やっとだよ・・・。

[03:00] お　わ　り

ぬわぁぁぁ、ちかれたもぉん(迫真)。Dが良く分からなかったし未だに分からないよ。

システムテスト

A,B,Cがなぜか通る。Cとかなんで通った。が、あんなにがんばったEが落ちる。

まあTLEだったので順当。(枝狩が足りなかった)

Eの状態数を2^17 * 17 まで減らせたはずなのにしなかったのが原因。

結果

ooo-x

A:444(00:03,-50)

B:948(00:13)

C:1016(01:04,-100)

=2408Pt.で

全体:162位/805

1696→1696

感想

Div2でこれは駄目だなあ。

まあレートは変わらず(といっても前のレート変動でまた少し下がった)

かなしい。明日のtcはなんとかしたいね。

ソース(Eに関してはきちんとしたソース)

今回はまとも?なのをご用意しました。前回Div1が0完だったので。

A

int main(){
	int n; cin >> n;
	string s;
	while(cin >> s){
		if(s.size() >= 10)cout << s[0] << s.size()-2 << s[s.size()-1] << endl;
		else cout << s << endl;
	}
}

B

int main(){
	int n,k,t,s=0;
	cin >> n >> k >> t;
	int ta = (n*k) * (t/100.0);
	for(int i=0;i<n;i++){
		cout << min(ta,k) << " ";
		ta -= min(ta,k);
	}
	cout << endl;
}

C

最高に汚いし何やってるか謎。よくこれで通ったと思う。

int main(){
	ios_base::sync_with_stdio(false);
	int n,ans;
	cin >> n;
	vector<int> d(n);
	rep(i,n)cin >> d[i];
	vector<int> lst;
	for(int i=3;i<=n;i++) if( n%((n-i)+1) || n/((n-i)+1) < 3){ } else lst.push_back(i);
		
	for(int x=0;x<n-1;x++){
		rep(k,lst.size()){
			int i = lst[k];
			int lp = n/((n-i)+1);
			bool ok = true;
			for(int j=0;j<lp;j++){
				if(!d[(x+j*((n-i)+1) )%n]){ok=false;break;}
			}
			if(ok){
				cout << "YES" << endl;
				return 0;
			}
		}
	}
	cout << "NO" << endl;
}

D

知らない。

E

役に立たないコメントをつけました。

アルゴリズムの手順としては、

全ての生成したいもの(ゴールと呼ぶ)に対して、それぞれ和がゴールになるような原子の組み合わせのものをあらかじめつくっておく。(ビット使って)
それを使って探索。詳しくはソース。(分かりづらいけど)
メモ化というか、状態で枝狩すると通る。しないとなかなか通らない。

string table[119] = {
"-","H","He","Li","Be","B","C","N","O","F","Ne",
"Na","Mg","Al","Si","P","S","Cl","Ar","K","Ca",
"Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn",
"Ga","Ge","As","Se","Br","Kr","Rb","Sr","Y","Zr","Nb","Mo",
"Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te","I","Xe",
"Cs","Ba","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm","Yb","Lu",
"Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn","Fr","Ra",
"Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm","Md","No","Lr",
"Rf","Db","Sg","Bh","Hs","Mt","Ds","Rg","Cn","Uut","Uuq","Uup","Uuh","Uus","Uuo"
};

vector<int> item , goal , able[17];
int n,m;


void output(int bit,int num){
	vector<string> ans;
	rep(i,n)if(bit & (1<<i) )ans.push_back(table[item[i]]);
	rep(i,ans.size())cout << (i?"+":"") << ans[i];
	cout << "->" << table[goal[num]] << endl;
}

vector<int> currentUsing;
bool done[1<<17][17];

bool dfs(int pos,int bit){
	
	//最後まで埋めることに成功した。
	if(pos == m){
		// 全部使っているか判定
		if(bit == (1<<n)-1){
			cout << "YES" << endl;
			rep(i,pos) output(currentUsing[i],i);
			// return true することで現在行っている再帰が全て終了する仕組み。
			return true;
		}else{
			return false;
		}
	}
	
	// (bit)の使用状況でpos番目まで既に来たことがあったら、return falseする。
	if(done[bit][pos]) return false;
	else done[bit][pos] = 1;
	
	rep(i,able[pos].size()){
		
		// 使おうとしているパターンと今までに使っているものが被っていたら、continue
		if(bit & able[pos][i]) continue;
		
		currentUsing.push_back(able[pos][i]);
		if( dfs( pos+1 , bit|able[pos][i] ) ) return true;
		currentUsing.pop_back();
	}
	return false;
}
int main(){
	cin >> n >> m;
	
	string tmp;
	
	rep(i,n)cin >> tmp , item.push_back(find(table,table+119,tmp)-table);
	rep(i,m)cin >> tmp , goal.push_back(find(table,table+119,tmp)-table);
	
	rep(i,m){
		for(int bit = 0 ; bit < (1<<n) ; bit++){
			int sum = 0;
			rep(j,n)if(bit & (1<<j) )sum += item[j];
			if(sum == goal[i]) able[i].push_back(bit);
		}
	}
	if(!dfs(0,0))cout << "NO" << endl;
}

開始前