TopCoder SRM 640 Div2 参加記


前回に引き続き、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になります。そこの変換を忘れると失敗します。

コード

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)まであるので、1から初めて全ての2x,2x+1を繰り返し計算していると間に合いません。

この時、禁止リストの数字について考えると、あるtable[i]の数値から作られる2x,2x+1の数は、2^(table[i]をrootとする2分木の深さ)-1 となります。
この数値を合計((2^k)-1)から引いていくことで最終的な総数を求めることができます。

ただ注意する点として、その禁止リストの数字が親となる2分木で共通する、すなわちすでにその箇所の数値を合計から引いている箇所を再び探索する可能性があります。そのため、数値を最初に昇順でソートして、その数値の親をたどった時すでに探索済みか否かを判定します。親はi/2を繰り返すことでたどることができるので、その全ての数値が禁止リストの数字でなければ、その数値以降の木の数値は未処理のため、その木の数値を削除します。

コード

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;
}
};

view raw
NumberGameAgain.cpp
hosted with ❤ by GitHub

1000 : BoardFoldingDiv2

コンテスト中に問題把握すらしきれなかったでしたので、後日追記します。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください