ICPCOOC 2016 - A Rearranging a Sequence｜AOJ

ICPCOOC2016 - A Rearranging a Sequence を解きました。

＜題意＞
・N個の整数の中から、M個の整数を移動(TOPに積む)する。
・移動する整数M個は e[ i ] で与えられる。
・移動後の並びを出力する。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(x) begin(x),end(x)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, M;
    cin >> N >> M;
     
    vector<int> A( M );
    for( auto &&x : A )
    {
        cin >> x;
    }
    vector<int> num;
    REP( i, N )
    {
        num.emplace_back( i + 1 );
    }
    REP( i, M )
    {
        auto index = distance( begin( num ), find( ALL( num ), A[ i ] ) );
        num.erase( begin( num ) + index );
        num.insert( begin( num ), A[ i ] );
    }
    for( const auto &x : num )
    {
        cout << x << endl;
    }
    return 0;
}

↑ 一番初めに提出したコード、TLE...
計算量考えてちゃんと実装しようね、って事で、計算量の勉強をしつつ考察をし直しました。
この問題をTLEしない為には O( 1 ) か O( log ) にする必要があるのですが、
std::vector で insert, erase の処理をしてしまうと、それぞれ O( n ) になってしまい間に合いません...。なので insert, erase での実装は諦めました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(x) begin(x),end(x)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, M;
    cin >> N >> M;
     
    vector<int> e( M );
    for( auto &x : e )
    {
        cin >> x;
    }
     
    reverse( ALL( e ) );

    vector<int> vc;
    REP( i, M )
    {
        if( count( ALL(  vc ), e[ i ] ) < 1 )
        {
            vc.emplace_back( e[ i ]  );
        }
    }
     
    for( const auto &x : vc )
    {
        cout << x << endl;
    }
     
    sort( ALL( vc ) );

    REP2( i, 1, N )
    {
        if( count( ALL(  vc ), i ) == 1 )
        {
            continue;
        }
        cout << i << endl;
    }
     
    return 0;
}

↑ 2回目の提出！色々計算量を調べて書きました！！...TLE...
？？？？？となったのですが、計算量の調べ方が悪かった様です...。
algorithm ヘッダの count *1 ではなくて、 set::count *2 の計算量を参照していました...。
( 以前も同様の参照ミスをした事があって気を付けてはいたのですが... )

そんな訳でまた考え直し ➡︎ 計算量 O( 1 ) ってもう配列参照ぐらいしか出来ないと知る...。

配列参照で何が出来るんですか、となった ➡︎ 出来るっぽい

if の中の count がしていた事は、重複がある値を除く事。
なので、重複する値をもう1つ別の配列で持って管理＆参照する方針でコード書きました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(x) begin(x),end(x)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, M;
    cin >> N >> M;
 
    vector<int> e( M );
    for( auto &x : e )
    {
        cin >> x;
    }
 
    reverse( ALL( e ) );
	
    //move
    vector<int>  flag( N + 1 );
    REP( i, M )
    {
        if( !flag[ e[ i ] ] )
        {
            cout << e[ i ] << endl;
            flag[ e[ i ] ] = 1;
        }
    }
 
    //not move
    REP2( i, 1, N + 1 )
    {
        if( !flag[ i ] )
        {
            cout << i << endl;
        }        
    }
    return 0;
}

↑ 3回目の提出で 計算量の問題をクリアして AC できました。
計算量を落とす作業がかなり大変でした...(普段全く意識した事がなかったので)
これからは制約関係なく、計算量を意識してコード書こうと思いました。

注）記事の中の計算量違っていたらこっそり教えて下さい。

*1:count - cpprefjp C++日本語リファレンス

*2:set::count - cpprefjp C++日本語リファレンス