問題
https://codeforces.com/contest/1352/problem/G
問題概要
整数nが与えられる。隣り合う項の差の絶対値が2以上4以下となるような、長さnの順列を作れ。無理な場合は-1を出力せよ。
考察
これは気づいてしまえばおしまいという問題で、以下の手順でできてしまいます。
- n以下の奇数を降順でならべる（
... 9 7 5 3 1） 4 2と並べる（... 9 7 5 3 1 4 2）- 6以上n以下の偶数を昇順に並べる（
... 9 7 5 3 1 4 2 6 8 10 ...）
なお、nが3以下の場合は無理です。n=2は1 2または2 1の二通りしかないので無理ですし、n=3でも2が1か3のどちらかには必ず隣接するので無理です。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; if (n < 4) { cout << -1 << endl; continue; } int m = n + (n % 2 - 1); for (int i = m; i > 0; i -= 2) cout << i << " "; cout << "4 2" << (n < 6 ? '\n' : ' '); for (int i = 6; i <= n; i += 2) cout << i << (i >= n - 1 ? '\n' : ' '); } }
まとめ
初のDiv. 4は、個人的には思ったより考察難易度が高かったことに驚いたのですが、難易度の傾斜はゆるくてたしかにたくさんの問題に挑戦できるようにという意図は満たしているように思いました。
今後もDiv. 4の記事は優先的に書いていきたいですね。
って、実はまだCの解説を書いてないんですけどね。なぜなら通せてないから。on_
