Slava and tanks [Codeforces Round #442 C]

http://codeforces.com/contest/877/problem/C

縦1, 横Nの盤面がある。
各盤面には戦車がある。
戦車がダメージを1度うけると隣接するセルに移動し、もう1度ダメージを受けると壊れる。
(どちらに移動するかはランダム)
(端の戦車は行ける方にしか行かない)
各ターン、ある1つのセルにいる戦車にダメージを与える。
最小何ターンで全ての戦車を壊せるか、各ターンにどのセルにダメージを与えたかも合わせて答えよ。
N≦10^5

解法

http://codeforces.com/contest/877/submission/31642423

実験してみると、戦法があることに気づく。
　
1. 偶数セルにダメージを与える(全ての戦車がこれで奇数セルに行く)
2. 奇数セルにダメージを与える(全ての戦車がこれで偶数セルに行くが、最初に偶数セルにいた戦車はここで壊れる)
3. 偶数セルにダメージを与える(偶数セルにいるのは1ダメージ加えられた戦車だけなので、ここで全部壊れる)
　
下の実装ではそうなっていないが、これをやればよい。
（最短である証明は無理）

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<int> ans;
    rep(i, 0, N / 2) {
        ans.push_back(i * 2 + 1);
        ans.push_back(i * 2);
    }

    if (N % 2 == 1) ans.push_back(N - 1);

    rep(i, 0, N / 2) ans.push_back(i * 2 + 1);

    int m = ans.size();

    printf("%d\n", m);
    rep(i, 0, m) {
        if (i) printf(" ");
        printf("%d", ans[i] + 1);
    } printf("\n");
}