torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #183, Division 2, C : Lucky Permutation Triple

概要

整数 n が与えられる。
[ 0, n ) の整数の順列の組 a, b, c について、次の条件を満たすものを一つ出力せよ。

  • 全ての i ( 0 \leq i < n ) について a_i + b_i \equiv c_i ( mod \quad n )

存在しない場合は -1 で示せ。

解法

小さいケースについて手元で表を書いて法則性を探して解きました。
例えば n = 5 のときはこのようになります。

0 0 0 1 4 2 3 3 2 4 1
1 0 1 1 0 2 4 3 3 4 2
2 0 2 1 1 2 0 3 4 4 3
3 0 3 1 2 2 1 3 0 4 4
4 0 4 1 3 2 2 3 1 4 0

これを見ると、副対角線に沿って選ぶのがよさそうだとわかります。
また、n が偶数の場合について同じ表を書くと、どう選んでもできないこともわかります。

完全な証明はせずに……もとい、できずにこれで出しました。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

void printAry( const VI &ary )
{
	const int N = ary.size();

	REP( i, 0, N )
	{
		if ( i )
		{
			cout << ' ';
		}
		cout << ary[i];
	}
	cout << endl;

	return;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	if ( !( n % 2 ) )
	{
		cout << -1 << endl;
		return 0;
	}

	VI nums( n );
	REP( i, 0, n )
	{
		nums[i] = i;
	}

	VI as( n ), bs( n ), cs( n );
	int pos = 1 % n;
	REP( i, 0, n )
	{
		as[i] = n - 1 - i;
		bs[i] = nums[ pos ];
		cs[i] = i;

		pos = ( pos + 2 ) % n;
	}

	printAry( as );
	printAry( bs );
	printAry( cs );

	return 0;
}