yukicoder : No.282 おもりと天秤(2)

クエリ回数O(logN)でも行けるんだろうなと思いながら、クエリをO(N)回投げてしまった。
http://yukicoder.me/problems/721

問題

N個の異なる重さの重りと、N個の天秤がある。
各天秤の両皿には重りを0個または1個乗せることができる。

この問題はリアクティブであり、１回のクエリで各天秤に乗せる重りを指定すると、まとめて重さの大小判定結果を得られる。
(ただし１回のクエリでは同じ重りを複数天秤で判定することはできない)

上記天秤群を駆使して、N個の重りを重い順に並べよ。

解法

Editorialに色々解法がある。
自分の解法はクエリ回数が(N-1)回なのでさほど効率は良くないが、せっかくなので紹介。

この問題は２人競技を総当たり戦するときに、効率のよい対戦順を考え、そこから順位を決める問題と見なすことができる。
対戦競技のリーグ戦に関わったことがあると、試合順を決める単純なアルゴリズムがあることに気づくのでそれを適用すればよい。

Nが偶数の場合を考え、N/2個のコートで1～N番の選手が試合をすると考える。
1番の選手は左端のコートに固定する。残りの選手は時計回りなり反時計回りで１試合ずつ動いていくと良い。
あとは負け回数の少ない順にソートすれば答え。

１２３　→　１３６　→　１６５　→　１５４　→　１４２　→　１２３
４５６　　　２４５　　　３２４　　　６３２　　　５６３　　　４５６

Nが奇数の場合は(N+1)番の選手をダミーで作り、ダミー選手と対戦する選手は休憩と見なせばよい。

int N;
int id[501];
char res[501][10];
pair<int,int> H[501];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int ON;
	
	cin>>N;
	
	ON=N;
	if(N%2) N++;
	FOR(i,N) H[i].second=i+1;
	
	FOR(x,N-1) {
		id[N-1]=N-1;
		FOR(j,N-1) {
			if(j<N/2) id[j]=(x+j)%(N-1);
			else id[N-2-(j-N/2)]=(x+j)%(N-1);
		}
		_P("?");
		FOR(i,ON) {
			if(i+N/2<ON) _P(" %d %d",id[i]+1,id[i+N/2]+1);
			else _P(" 0 0");
		}
		_P("\n");
		fflush(stdout);
		FOR(i,ON) cin>>res[i];
		
		FOR(i,N/2-ON%2) {
			if(res[i][0]=='<') H[id[i+N/2]].first++;
			if(res[i][0]=='>') H[id[i]].first++;
		}
	}
	sort(H,H+ON);
	_P("!");
	FOR(i,ON) _P(" %d",H[i].second);
	_P("\n");
	fflush(stdout);
}

まとめ

競プロ始めるよりずっと昔に感動したアルゴリズムがこんなところで役立つとは。