Codeforces #177 Div2 E "Polo the Penguin and XOR operation"
問題
http://codeforces.com/contest/289/problem/E
訳
0~Nの数値が含まれている順列について考える。
順列P = P(0), P(1),... P(N)の美しさを
( (0 xor P(1) ) + ( (1 xor P(1) ) + ... + ( (N xor P(N) )と定義する。
0からNの数値を1つずつ持つ順列のなかで、最も美しい順列の美しさの値と、
その内容を表示せよ。
制約
1 <= N <= 10^6
紙に書いたこと
うむ・・
うむうむ・・
おおう?
おおお!!
何か知らんが・・・
1を1つも失うことのない順列を必ず作れそうだ
解法
大きいインデックスから貪欲にベストな数値を見つけてけばOK!
ソースコード
int a[1000010]; // 美しすぎる順列 int main() { int N; cin >> N; // 美しさを1つも失うことない順列が必ず作れる long long ans = (long long)N * (N+1); for( int i = N; i >= 0; ){ // 111...111を作る int p = 1; int t = i; while( t ){ t >>= 1; p <<= 1; } p -= 1; // 111...111 int j = p ^ i; // iにとってベストなペア int nextI = j - 1; // j - iの間でベストなペアを探していく for( ; j < i; j++, i-- ){ a[i] = j; a[j] = i; } i = nextI; } printf( "%I64d\n", ans ); for( int i = 0; i <= N; i++ ){ printf( "%d ", a[i] ); } }