TCO Round1A
結果報告
エイプリルフール午前一時回．
参加する予定だったのにさっそうと寝ブッチをかました．
250-500-1000回でした。
| Level | ProblemName | Status | Point |
| Easy | EllysJuice | PassedSystemTest(Practice) | ---- |
| Medium | EllysFractions | PassedSystemTest(Practice) | ---- |
| Hard | EllysLights | PassedSystemTest(Practice) | ---- |
Easy EllysJuice
問題
1ガロンのりんごジュースとオレンジジュースがある．
何人かでこれを飲み回す時，奇数回目に飲む人はりんごジュースの残りの半分を，偶数回目に飲む人はオレンジジュースの半分を飲むとする．
今，誰が何回飲んだかのデータが文字列ベクタで与えられる．
一番ジュースを飲んだ可能性のある人を列挙せよ．
但し，「一番ジュースを飲む」とは他のどんな人よりも大きい（以上ではない）量飲んでいる事を指す．
考えたこと
「太郎，次郎，三郎，太郎，次郎」というベクトルが入力の時に，
太郎，次郎，三郎が一回飲むまでは太郎の二回目が回ってこないのではないか，なんて勘違いして色々手こずるなどした．
実際は入力データサイズが8以下であることから，
next_permutationで全列挙調べあげるだけで良い．
コード
vector <string> getWinners(vector <string> players) {
vector <string> result;
set<string> member;
double val[8] = {1,1,0.5,0.5,0.25,0.25,0.125,0.125};
for( int i = 0 ; i < players.size(); i++ ){
member.insert( players[i] );
}
int n_member = member.size();
vector<string> memlist = players;
sort( memlist.begin(), memlist.end() );
memlist.erase( unique(memlist.begin(),memlist.end() ), memlist.end() );
sort( players.begin(), players.end() );
do{
map<string, double> map;
double maxval = 0;
for( int i = 0 ; i < players.size(); i++ ){
map[players[i]]+= val[i];
maxval = max( maxval, map[players[i]] );
}
int maxnum = 0;
bool addflag = true;
string candidate ="";
for( int i = 0 ; i <memlist.size(); i++ ){
if( map[memlist[i]] == maxval ){
if( candidate != "" ){
addflag = false;
break;
}
candidate = memlist[i];
}
}
if( addflag ) result.push_back( candidate );
}while( next_permutation(players.begin(), players.end() ));
sort( result.begin() , result.end() );
result.erase( unique(result.begin(), result.end() ) , result.end() );
return result;
なんか明らかに無駄な処理とか多い気がするのだけれど，イマイチ上手い方法が思い浮かばなかった．実際は計算量はとかだと思う．
Medium EllysFractions
問題
ある分数がfractionであるとは，その分数が既約分数であり，分母と分子の積が，ある自然数の階乗であることをいう．
与えられる自然数Nに対して，分母と分子がN以下の自然数の階乗となるような，0と1の間にあるfractionの数を返せ．
考えたこと．
分母と分子の積がMの階乗になっていたとすると，
分母と分子にM,M-1,M-2...のどれかが約数として入っていることになる．
しかも，既約分数であるという制約により，実際には分母と分子のどちらかにしか約数になり得ない．
更に既約分数であるという制約から，例えば，M以下のとある素数pが分母の約数出会ったとするならば，M以下の任意のpの倍数は分母の約数とならねばならない．
以上のことより，分母と分子の積がMの階乗となるようなfractionの数は，
M以下の素数それぞれについて「分母の約数になるか，分子の約数になるか？」を割り当てたパターン数に等しい．（分数が１より小さいという制約により，割り当てが完了した時点でどちらが分母でどちらが分子かは自動的に決まる，ということにも注意する）
このcountingを2からNまで順々に繰り返せば良いだろう．
コード
long long getCount(int N) { long long result=0; bool isprime[251]; memset( isprime , true, sizeof( isprime ) ); isprime[0] =false; isprime[1] = false; for( int i = 2 ; i < 251; i++ ){ if( isprime[i] ){ for( int j = i+i; j < 251 ; j+= i ){ isprime[j] =false; } } } int n_prime = 0; long long num = 1; if( N >= 2 )result = 1; for( int n =3 ; n <= N ; n++ ){ if( isprime[n] ){ n_prime++; num *= 2; } result +=num; } return result; }
計算量は入力の値Nに対して．
あれこれEasyより簡単じゃね…
Hard EllysLights
問題
Ellysさんの家には沢山のライトがあって，それぞれが現在，ついてたり消えていたりする．
Ellysさんの家にはそれらのON-OFFを切り替えるスイッチがあるが，
一つのスイッチを押すと，複数のライトのON-OFFが切り替わったりする．
（あるライトに対応するスイッチは高々二つであるということはわかっている）
いま，ライトの状況と夫々のスイッチに対応するライトの表が入力として与えられるので，ライトをすべて消灯する為に必要なスイッチの切替数の最小値を返せ．
考えたこと
多分全部消灯の状態から逆に遡っていって現在の状態に持ってくる最短パス的なものを考えればよさそうである．
しかし，ライトのON-OFFを愚直に考えたのでは，ライトの個数が最大５０個ある異常，2^50位のノード数が必要なのできっと終わらないだろう．
ライトに対して二つまでしかスイッチが対応しないということは，かなり選択肢は制限されそうであるが…
ライトの初めから順に眺めつつ
注目しているライトは現在の状態から切替が必要である時
- > 切り替えスイッチをどちらか一つ押す．そのスイッチを使用不能にするフラグを立てる
注目しているライトは現在の状態から切り替えが不要である時
- > 切り替えスイッチを二つ共に押すor何も押さない，２つとも押した場合はそのスイッチを使用不能にするフラグを立てる
みたいな深さ優先探索で間に合うのなら書くけど，間に合うんですかね？
こんな感じで試しに書いてみたけど，途中で出かける時間になったのでストップ中．
こういう深さ優先探索で通るの？ってなったときの正しい評価方法が解らないなあ
解答を読んで
Editorial(http://p.tl/lJm8)を読んだ．
2SAT問題とか書いてあるじゃないですかやだー
確かに，あるライトがinitialにおいて"Y"であるとは，
対応スイッチが1個のばあい：それが必ず使われる
対応スイッチが2つのばあい：どちらか一方が使われる
なのだから，「スイッチSが使われる」を命題P(S)とすると，
S1とS2が対応スイッチならば，(P(S1) and !P(S2)) or (P(S2) and !P(S1))が真だ．
スイッチSに対してP(S)と!P(S)がノードになるような2*スイッチ数のグラフを考え，
「このスイッチを使うならこのスイッチは使わない」みたいな状態を表したグラフを作れば，
後はそのグラフに矛盾がないことを調べ，
必ず使うor使わないスイッチの条件から，確実に処遇の決まるスイッチを調べた後
処遇の決まらないものについて，極力スイッチを使わない組合せを選ぶ．
という処理をすれば良いようだ．
確かにこの方法ならばフロイド・ワーシャルとか使っても間に合う程度には余裕である．
という訳でガリガリ書いた．時間もかかったしデバッグも大変だったしコードもめちゃ長い…
1000が解けるレベルになるにはこのあたりの能力をもっと洗練する必要がありそう．
コード
int getMinimum(string initial, vector <string> switches) { bool graph[205][205]; int result; memset(graph,false,sizeof(graph) ); int lumpsize = initial.size(); int swsize = switches.size(); vector< vector<int> > lump_to_switch; for( int i = 0 ; i < lumpsize; i++ ){ vector<int> tmpvec; for( int j = 0 ; j < swsize; j++ ){ if( switches[j][i] == 'Y' ){ tmpvec.push_back( j ); } } lump_to_switch.push_back( tmpvec ); } for( int i = 0 ; i < lumpsize; i++ ){ if( initial[i] == 'Y' ){ if( lump_to_switch[i].size() == 0 ) return -1; else if( lump_to_switch[i].size() == 1 ){ int num = lump_to_switch[i][0]; graph[0][(num+1)*2] = true; graph[(num+1)*2][0] = true; } else{ int num = lump_to_switch[i][0]; int num2 =lump_to_switch[i][1]; //either of the lump can be used graph[(num+1)*2][(num2+1)*2+1] = true; graph[(num2+1)*2+1][(num+1)*2] = true; graph[(num2+1)*2][(num+1)*2+1] = true; graph[(num+1)*2+1][(num2+1)*2] = true; } } else{ if( lump_to_switch[i].size() == 0 ){ // do nothing } else if( lump_to_switch[i].size() == 1 ){ int num = lump_to_switch[i][0]; graph[0][(num+1)*2+1] = true; graph[(num+1)*2+1][0] = true; } else{ int num = lump_to_switch[i][0]; int num2 = lump_to_switch[i][1]; graph[(num+1)*2][(num2+1)*2] = true; graph[(num2+1)*2][(num+1)*2] = true; graph[(num+1)*2+1][(num2+1)*2+1] = true; graph[(num2+1)*2+1][(num+1)*2+1] = true; } } } for( int j = 0 ; j < 2*swsize+2 ; j++ ){ for( int x = 0 ; x < 2*swsize+2; x++ ){ for( int y = 0 ; y < 2*swsize+2; y++ ){ graph[x][y] |= (graph[x][j]&&graph[j][y]); } } } // check whether it is considered /*for( int i = 0 ; i < swsize*2+2; i++ ){ for( int j = 0 ; j < swsize*2+2 ; j++ ){ cout << graph[i][j]; } cout << endl; }*/ for( int i = 1 ; i <= swsize; i++ ){ if( graph[i*2+1][i*2] ) return -1; } //deal with the switch which must be used bool checked[101]; result =0; memset( checked, false, sizeof(checked) ); for( int i = 1 ; i <= swsize; i++ ){ if( graph[0][2*i] ){ checked[i-1] = true; result++; } if( graph[0][2*i+1]){ checked[i-1] = true; } } //find the way to minimize the switch to be operated for( int i = 1; i <= swsize; i++ ){ if( checked[i-1] == false ){ int onnum = 1; int offnum = 0; vector<int> operated; operated.push_back( i ); for( int j = 1 ; j <= swsize; j++ ){ if( i==j) continue; if( checked[j-1]== false ){ if( graph[i*2][j*2] ){ onnum++; operated.push_back( j ); } if( graph[i*2][j*2+1] ){ offnum++; operated.push_back( j ); } } } result+= min( onnum, offnum ); for( int k = 0 ; k < (int)operated.size(); k++ ){ if( checked[operated[k]-1] == true ){ cout << "Error!:" << operated[k]-1 << endl; } checked[operated[k]-1] = true; } } } return result; }
計算量の見積もりはスイッチの数をNとしてフロイド・ワーシャルの
が効いてると思われ．
