スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Beta Round #78

2011/07/23 0:00~2:00 (JST)
Codeforces Beta Round #78 (Div.1 Only) の参加記録

Tags : プログラミング Codeforces 未解決

結果

A. AC (00:20)
B. 4WA (pretest)
C. -
D. -
E. -
Hacks : +-0 (0/0)
Standing : 83/394
Unrated

問題

問題セットの原文はここを参照。

A. Help Victoria the Wise
6 色の色が与えられるので、これらの色を 1 回ずつ使って立方体の面を彩色する方法は何通りあるかを答えよ。
回転で一致するものは同一視する。

B. Help King
表と裏が等確率で出るコインが 1 枚ある。
これを使って、n 人の中から 1 人を選びたい。
ただし、どの人も等確率で選ばれるような選び方でないといけない。

最適な戦略をとるとき、コインを投げる回数の期待値の最小値を求めよ。

1 ≦ n ≦ 1017

C. Help Greg the Dwarf
問題中の図 を見れば一目瞭然。

片方の幅 a, もう片方の幅 b の L 字路がある。
l × w の長方形がこの道を通過できるような w (≧ l) の最大値を求めよ。
どんな w でも通過できないときはそのことを報告せよ。

1 ≦ a, b, l ≦ 104

D.

E.

解答

言語は C++。テンプレはここを参照。

A.
void rotx(string &s){
string t=s;
t[0]=s[1];
t[1]=s[5];
t[5]=s[3];
t[3]=s[0];
s=t;
}

void roty(string &s){
string t=s;
t[0]=s[4];
t[2]=s[0];
t[5]=s[2];
t[4]=s[5];
s=t;
}

void rotz(string &s){
string t=s;
t[1]=s[4];
t[2]=s[1];
t[3]=s[2];
t[4]=s[3];
s=t;
}

string lexmin(string s){
string ans=s;
rep(i,6){
rep(j,4){
ans=min(ans,s);
rotz(s);
}
if(i&1) rotx(s); else roty(s);
}

return ans;
}

int main(){
string s; cin>>s;
sort(s.begin(),s.end());

set<string> S;
do{
S.insert(lexmin(s));
}while(next_permutation(s.begin(),s.end()));

cout<<S.size()<<endl;

return 0;
}

やるだけ。
全パターン回転させてみて、辞書式最小のものを set につっこんだ。

B.


C.


D.


E.


感想

A が簡単で、B~E がすべて難しい (難易度は同じくらい) という 変態 珍しいセットだった。

A.
この手の問題はたまに出てくるので、さいころクラスは持っておいてもいいかもしれない。

B.
この問題の想定解が間違っていた (さらに良い解があった) ため、no contest になった。
その想定解にすらたどり着けなかった自分は論外だけど。

C.
がんばれば、w は x 軸との角度 θ の関数として書ける(?)
それを微分してごにょごにょやるのかなぁ...と思った。
思っただけ。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。