前回に引き続き、SRM参加したので、簡易解説もどきと一緒にコードを貼っていきます。
今回は、システムの不具合か本来日曜開催だったのが水曜に延期の上、延期された時間から更に1時間遅延しての開始という状態でした。
250 : ChristmasTreeDecorationDiv2
問題概要
飾り付けの星とリボンがあり、リボンiはx[i]とy[i]の星をつなぐ。
この時、違う色の星を結ぶリボンが何本あるか答える。
COL[i]は星の色を表し、{x,y}[i]はその星の色がcol[{x,y}[i]]の色であることを表している。
解法
星の数は最大50なので、全てのx,yについて色が等しいか否かの数を数えればOKです。
ただ、x[i]で表しているcolの位置は1-indexedに対して、colはvectorで与えられるので、o-indexedになります。そこの変換を忘れると失敗します。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class ChristmasTreeDecorationDiv2 { | |
| public: | |
| int solve(vector<int> col, vector<int> x, vector<int> y) { | |
| int cnt=0; | |
| for(int i=0;i<x.size();i++) | |
| { | |
| if(col[x[i]-1]!=col[y[i]-1]) | |
| cnt++; | |
| } | |
| return cnt; | |
| } | |
| }; |
600 : NumberGameAgain
問題概要
xという数字に対して、2x,2x+1 となる数値をx=1から初めて、(2^k-1)まで繰り返し数える。
ただし、tableで与えられる禁止数字のリストがあり、そのリストの数値および
その数値から始まる2x,2x+1はカウントしない。
kとtableが与えられるので、作ることのできる数の総数を答える。
解法
kは最大40、すなわち2^40(>10^12)まであるので、１から初めて全ての2x,2x+1を繰り返し計算していると間に合いません。
この時、禁止リストの数字について考えると、あるtable[i]の数値から作られる2x,2x+1の数は、2^(table[i]をrootとする2分木の深さ)-1 となります。
この数値を合計((2^k)-1)から引いていくことで最終的な総数を求めることができます。
ただ注意する点として、その禁止リストの数字が親となる2分木で共通する、すなわちすでにその箇所の数値を合計から引いている箇所を再び探索する可能性があります。そのため、数値を最初に昇順でソートして、その数値の親をたどった時すでに探索済みか否かを判定します。親はi/2を繰り返すことでたどることができるので、その全ての数値が禁止リストの数字でなければ、その数値以降の木の数値は未処理のため、その木の数値を削除します。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class NumberGameAgain { | |
| public: | |
| long long solve(int k, vector<long long> table) { | |
| const long long int MAX=((long long)2<<(k-1)); | |
| sort(table.begin(), table.end()); | |
| long long int cnt=MAX-2; | |
| for(int i=0;i<table.size();i++) | |
| { | |
| long long int ii=table[i]/2; | |
| int tree=1; | |
| bool flag=false; | |
| while(ii>1) | |
| { | |
| if(binary_search(table.begin(), table.end(), ii)) | |
| { | |
| flag=true; | |
| break; | |
| } | |
| ii=ii/2; | |
| tree++; | |
| } | |
| if(flag) | |
| continue; | |
| cnt-=((long long)1<<(k-tree))-1; | |
| } | |
| return cnt; | |
| } | |
| }; |
1000 : BoardFoldingDiv2
コンテスト中に問題把握すらしきれなかったでしたので、後日追記します。