概要
整数 n が与えられる。
[ 0, n ) の整数の順列の組 a, b, c について、次の条件を満たすものを一つ出力せよ。
- 全ての について
存在しない場合は -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; }