GWに突入しましたね。皆さん10連休どのように過ごしますか？
これだけ大型連休だとどこへ行くにも混みそうなので、僕は何も予定を入れられなかったです（思考停止）。
休日は、ギターの練習と競プロと自分の開発環境の整備にでも当てようと思います。

さて、「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を読み進めていきます。
僕は週頭に買ってしまいましたが、GWセールで半額程度で購入することができます。

ALDS1_2_D: Shell Sort

チャレンジ問題なので、解説を読みつつ実装できる部分は解いていきます。

擬似コード

次のプログラムは、挿入ソートを応用して n 個の整数を含む数列 A を昇順に整列するプログラムです。

1  insertionSort(A, n, g)
2      for i = g to n-1
3          v = A[i]
4          j = i - g
5          while j >= 0 && A[j] > v
6              A[j+g] = A[j]
7              j = j - g
8              cnt++
9          A[j+g] = v
10
11 shellSort(A, n)
12     cnt = 0
13     m = ?
14     G[] = {?, ?,..., ?}
15     for i = 0 to m-1
16         insertionSort(A, n, G[i])

問題

shellSort(A, n) は、一定の間隔 g だけ離れた要素のみを対象とした挿入ソートである insertionSort(A, n, g) を、最初は大きい値から g を狭めながら繰り返します。これをシェルソートと言います。

上の疑似コードの ? を埋めてこのプログラムを完成させてください。n と数列 A が与えられるので、疑似コード中の m、m 個の整数 Gi(i=0,1,...,m－1)、入力 Aを昇順にした列を出力するプログラムを作成してください。ただし、出力は以下の条件を満 たす必要があります。

1≤m≤100
0≤Gi≤n
cnt の値は ⌈n1.5⌉ を超えてはならない

入力

1 行目に整数 n が与えられます。続く n 行目に n 個の整数 Ai(i=0,1,...,n−1) が与えられます。

出力

1 行目に整数 m、2 行目に m 個の整数 Gi(i=0,1,...,m−1) を空白区切りで出力してください。
3 行目に、G を用いた場合のプログラムが終了した直後の cnt　の値を出力してください。
続く n 行に整列した Ai(i=0,1,...,n−1) を出力してください。

この問題では、１つの入力に対して複数の解答があります。条件を満たす出力は全て正解となります。

制約

・1≤n≤1,000,000
・0≤Ai≤109

コード

45分考えて妥当性のある実装を導けなかったので、解説を読みつつ写経しました。
シェルソート内部の挿入ソートについては、実装できましたがそれ以降は頭抱えてました…。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

long long counter = 0;
int A[1000000];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g) {
    for (int i = g; i < n; i++) {
        int v = A[i];
        int j = i - g;
        while (j >= 0 && A[j] > v) {
            A[j + g] = A[j];
            j -= g;
            counter++;
        }
        A[j + g] = v;
    }
}

void shellSort(int A[], int n) {
    for (int h = 1;;) {
        if (h > n) break;
        G.push_back(h);
        h = 3 * h + 1;
    }

    for (int i = G.size() - 1; i >= 0; i--) {
        insertionSort(A, n, G[i]);
    }
}

// TODO: 写経になってしまったので、解説を読み込んで理解に落とし込む
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);

    shellSort(A, n);
    cout << G.size() << endl;
    for (int i = G.size() - 1; i >= 0; i--) {
        printf("%d", G[i]);
        if (i) printf(" ");
    }
    printf("\n");
    printf("%d\n", counter);
    for (int i = 0; i < n; i++) printf("%d\n", A[i]);

    return 0;
}

cin / scanf

競技プログラミングでは、ほぼ必ずと言っていいほど標準入力で入力を受けてから結果を標準出力へと出力します。

C++では、以下の書き方が可能です。

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;

  cout << n << endl;
  return 0;
}

一方Cでは以下の様に記述します（C++はCを内包する為どちらでも可）。

#include <cstdio>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  
  printf("%d\n", n);
  return 0;
}

で、何が違うかというと速度が違います。
iostream読みこむだけで相当時間かかるようなので、scanf / printf使う癖付けた方が良さそうですね。
詳細は… こちらの Qiita記事に詳しく書いてあるのでそちらを参照ください。

普通に途中まで書いてから、同じ様な記事見つけてしまったので丸投げします 🙈🙈🙈

おわりに

僕と同じでゴールデンウィークに何もすることがない人、GWセールで本を買ってぜひアルゴリズムの勉強をしましょう。僕は追加で蟻本も書いました。