JAPLJ Contest B Banksia
例えば問題文中の図1のトーナメントだと、4より確実に強いのは4に勝った1と4に勝った1に勝った5。トーナメント表を辿っていて出てくる人は自分よりも強い。そのような人がK人未満なら上位K人の可能性がある。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, K; cin >> N >> K; vector<vector<int> > result; for ( int n=N; ; n=(n+1)/2 ) { result.push_back( vector<int>( n ) ); for ( int i=0; i<n; i++ ) cin >> result.back()[i]; if ( n == 1 ) break; } vector<int> ans; for ( int i=0; i<N; i++ ) { int t = i; int c = 0; for ( int j=0; j<(int)result.size()-1; j++ ) { if ( result[j][t] != result[j+1][t/2] ) c++; t /= 2; } if ( c < K ) ans.push_back( result[0][i] ); } sort( ans.begin(), ans.end() ); for ( int i=0; i<(int)ans.size(); i++ ) cout << ans[i] << endl; }