ALDS1_2_D: Shell Sort

AOJ AOJ本

この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造（渡部有隆著，Ozy・秋葉拓哉協力）』を読んで解きました．

　

問題

　

ソースコード

#include <iostream>
#include <utility>
#include <cstdio>
using namespace std;

void insertionSort(int A[], const int n, const int g, int *cnt)
{
    for( int i = g; i < n; ++i ){
        int tmp = A[i];
        int j = i - g;
        while( -1 < j && tmp < A[j] ){
            //cout << A[j+g] << "<-->" << A[j] << endl;
            A[j+g] = A[j];
            j = j - g;
            ++*cnt;
        }
        A[j+g] = tmp;
    }
}

void shellSort(int A[], const int n)
{
    int cnt = 0;
    int m;
    int G[100];
    for( int i = 0; i < 100; ++i ){
        if( i == 0 ) G[i] = n / 2 + 1;
        else G[i] = G[i-1] / 2 - 1;
        if( G[i] < 0 ){
            G[i-1] = 1;
            G[i] = 0;
            m = i;
            break;
        }
    }

    for( int i = 0; i < m; ++i )
        insertionSort(A, n, G[i], &cnt);

    //出力
    printf("%d\n", m);
    for( int i = 0; i < m; ++i ){
        if( i ) printf(" ");
        printf("%d", G[i]);
    }
    printf("\n%d\n", cnt);
    for( int i = 0; i < n; ++i )
        printf("%d\n", A[i]);
}

int main()
{
    //入力
    int n;
    scanf("%d", &n);
    int A[n];
    for( int i = 0; i < n; ++i )
        scanf("%d", &A[i]);

    //シェルソート
    shellSort(A, n);

    return 0;
}

　

反省点

  • 思うままに書く
  • 入出力例と違う
  • が，問題文には

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

  • 見逃してた
  • 問題文はちゃんと読む
  • （上記に気付かないまま）入出力例に合わせた間隔の数列（G）を求めることに成功するもRE
  • 解説を読む
  • Gの選び方は様々云々という文章と解答例を眺めて，G[]の指定を確認しに問題文を再読
  • 上記に気付く
  • 最初とほぼ同じものを書く
  • 一発AC
  • 問題文はちゃんと読む
  • 本では高速化のためにscanf, printfを採用しているが，すべて入出力演算子で行なってもTLEしなかった:
    AIZU ONLINE JUDGE: Code Review
  • vector: 配列のようにメモリは隣り合っている
  • push_back(hoge): vectorの最後に要素hogeを追加
  • back(): 最後尾の要素を返す
  • at(pos): 先頭からpos番目の要素を返す