Sum of Integers｜AOJ｜深さ優先探索(DFS)

深さ優先探索(DFS)を勉強中で、DFSを使って解ける優しめ問題という事で、
整数の和 | Aizu Online Judge を解きました。

＜題意＞
0 〜 9 の数字から異なる数をN個取り出して、和がSとなる組み合わせが何個あるか出力する

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
// i --> 0 - 9までの数字
// sum --> 合計値
// cnt --> 和がSとなる組み合わせの数
// total --> 足す数(N個まで足す)
int N, S, cnt;
void dfs( int i, int sum, int total )
{
    //N回を満たしている 且つ 合計がSに達したものをcountする
    if( total == N && sum == S )
    {
        cnt++;
        return;
    }
    //0-9まで探索したら or 足す回数がN回に達したら 終わり
    if( i == 10 || total == N ) return;
    
    //合計に i を足す場合 -> 足す回数を +1 する
    dfs( i + 1, sum + i, total + 1 );
    //合計に i を足さない場合
    dfs( i + 1, sum, total );
}
int main()
{
    while( cin >> N >> S )
    {
        if( N == 0 && S == 0 ) break;
        //合計値の初期化
        cnt = 0;
        //dfs( 数字の0から, 合計値0から, 足す数字0から)
        dfs( 0, 0, 0 );
        cout << cnt << endl;
    }
    return 0;
}

DFSを本で勉強したのですが、さっぱり実装出来る気がしなくて、
処理をいくつかに分割して書いてやっとまとまりました。
手順としては下記の工程を経ています。

1）足し算部分の再帰を書く
2）合計を取る部分を書く
3）合計がSとなったものをcountする部分を書く
4）合計に足す場合と、足さない場合を書く
5）N個だけ選んで和を取る部分を書く

個々の処理がどうなっているか良く解ったので理解が進みました。

この問題を解く際、グローバル変数に count と云う変数名を使ったら gccに怒られました。
std::count と区別がつかないよって事らしいです。
それから、returnで何も返さない関数はvoidで宣言する様で、そこも新たに覚えました。
(何も返さない関数を初めて書きました...！)

次はstack編も覚えなくてはみたいな感じです。

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++日本語リファレンス

cpp macro template - 2 -

型で事故り、マクロtemplateを修正したのでメモ。

out  #define SORT(x) sort((x).begin(),(x).end(),greater<int>())
out  #define SORTP(x) sort((x).begin(),(x).end(),greater<pair<int,int>>());

in    #define SORTR(x) {sort(begin(x),end(x));reverse(begin(x),end(x));}

TopCoder 提出編

過去問を解きました。
...が、問題を解いた時間 ＜ 提出にかかった時間 となったので記録に残します。

まず、任意の過去問に移動して解く問題をselectするとGreedによって提出用ファイルがローカルに勝手に生成されます↓
※要 Java applet の option で default言語指定(cpp)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define SORTR(x) {sort((x).begin(),(x).end());reverse((x).begin(),(x).end());}
#define ALL(x) begin(x),end(x)
#define rALL(x) rbegin(x),rend(x)
#define D(x) for_each((x).begin(),(x).end(),[](auto& x){cout<<x<<" ";});
using LL=long long;
using ULL=unsigned long long;
using PII=pair<int,int>;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = numeric_limits<int>::max();

struct LiveConcert {
  vector<int> h;
  vector<string> s;
  int maxHappiness(vector<int> _h, vector<string> _s) {
    h = _h, s = _s;
    return 0;
  }
};

// CUT begin
ifstream data("LiveConcert.sample");

string next_line() {
    string s;
    getline(data, s);
    return s;
}

template <typename T> void from_stream(T &t) {
    stringstream ss(next_line());
    ss >> t;
}

void from_stream(string &s) {
    s = next_line();
}

template <typename T> void from_stream(vector<T> &ts) {
    int len;
    from_stream(len);
    ts.clear();
    for (int i = 0; i < len; ++i) {
        T t;
        from_stream(t);
        ts.push_back(t);
    }
}

template <typename T>
string to_string(T t) {
    stringstream s;
    s << t;
    return s.str();
}

string to_string(string t) {
    return "\"" + t + "\"";
}

bool do_test(vector<int> h, vector<string> s, int __expected) {
    time_t startClock = clock();
    LiveConcert *instance = new LiveConcert();
    int __result = instance->maxHappiness(h, s);
    double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC;
    delete instance;

    if (__result == __expected) {
        cout << "PASSED!" << " (" << elapsed << " seconds)" << endl;
        return true;
    }
    else {
        cout << "FAILED!" << " (" << elapsed << " seconds)" << endl;
        cout << "           Expected: " << to_string(__expected) << endl;
        cout << "           Received: " << to_string(__result) << endl;
        return false;
    }
}

int run_test(bool mainProcess, const set<int> &case_set, const string command) {
    int cases = 0, passed = 0;
    while (true) {
        if (next_line().find("--") != 0)
            break;
        vector<int> h;
        from_stream(h);
        vector<string> s;
        from_stream(s);
        next_line();
        int __answer;
        from_stream(__answer);

        cases++;
        if (case_set.size() > 0 && case_set.find(cases - 1) == case_set.end())
            continue;

        cout << "  Testcase #" << cases - 1 << " ... ";
        if ( do_test(h, s, __answer)) {
            passed++;
        }
    }
    if (mainProcess) {
        cout << endl << "Passed : " << passed << "/" << cases << " cases" << endl;
        int T = time(NULL) - 1476520950;
        double PT = T / 60.0, TT = 75.0;
        cout << "Time   : " << T / 60 << " minutes " << T % 60 << " secs" << endl;
        cout << "Score  : " << 250 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(2);
    set<int> cases;
    bool mainProcess = true;
    for (int i = 1; i < argc; ++i) {
        if ( string(argv[i]) == "-") {
            mainProcess = false;
        } else {
            cases.insert(atoi(argv[i]));
        }
    }
    if (mainProcess) {
        cout << "LiveConcert (250 Points)" << endl << endl;
    }
    return run_test(mainProcess, cases, argv[0]);
}
// CUT end

なにこれ状態だったんですが、まず最初にCUTの部分は不要なんだろうと思って削除しました←
でもこれ、実はtestやローカルで出力する為のコードで大変有り難いコードでした...。
仕様が分からないのですが、ARENAでsubmitする時には残っていても影響がないようです。
(もちろん削除してsubmitしても特に影響は無かったです(試した))

因みに...プロに教えて頂いたのですが、
ifstream data("LiveConcert.sample");　の部分を
auto &data = cin;　とするとWandBoxで sample test 出来るんですよ！！！
(※WandBoxでなくても出来ます)

struct LiveConcert {
    vector<int> h;
    vector<string> s;
    int maxHappiness(vector<int> _h, vector<string> _s) {
        h = _h, s = _s;
        return 0;
    }
};

解答を書いていく部分はここ↑
TopCoderは使用するclass名,関数名,変数名,型など(？)が決められているようです。
問題の解答を return させるように書くっぽい。
AtCoder育ち初心者なのでかなり戸惑いました...。

struct LiveConcert {
    vector<int> h;
    vector<string> s;
    int maxHappiness(vector<int> h, vector<string> s)
    {
        vector<pair<int,string>> P;
        REP( i, (int)h.size() )
        {
            P.emplace_back( h[i], s[i] );
        }
        SORTP( P );
        map<string,int> mp;
        REP( i, (int)h.size() )
        {
            mp.insert( make_pair( P[i].second, P[i].first ) );
        }
        int res{};
        for( auto x : mp )
        {
            res += x.second;
        }
        return res;
    }
};

↑なんか良く解らないけれど、取り敢えず自分の解答を生成されたコードにmixした。
そしてローカルfileを保存して、java applet でcompileが通った事を確認して、
sample testして合ってそうだったらsubmit。
(他の機能はまだ解らないです)

ACとか出ない....

自分で java applet の Practice options の Run System test っていう所を見に行く
ケースが全部 Passed してたら多分ACしてるっぽい...(？)

まだかなり手探りなので、違う箇所あったら随時記事を修正します...(おしまい)

std::unique｜続・重複要素チェック｜C++

std::unique *1 の挙動にハマったので覚え書き📝

#include <bits/stdc++.h>
using namespace std;
bool check( vector<int> A ){
    sort( begin( A ), end( A ) );
    return unique( begin( A ), end( A ) ) == end( A );
}
int main()
{
    vector<int> vc1{ 1,1,1,2,3,3,3,1,1,1 };
    vector<int> vc2{ 1,2,3 };
    
    cout << "重複：" << ( check( vc1 ) ? "無し" : "有り" ) << endl;
    for( auto &x : vc1 ) cout << x << " ";
    
    cout << endl;
    
    cout << "重複：" << ( check( vc2 ) ? "無し" : "有り" ) << endl;
    for( auto &x : vc2 ) cout << x << " ";
    
    return 0;
}

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

std::uniqueを使っても関数に投げてcheckする分には元の要素に変化はない
➡︎ vectorのコピーを関数に渡しているから

#include <bits/stdc++.h>
using namespace std;
bool check( vector<int> A ){
    return unique( begin( A ), end( A ) ) == end( A );
}
int main()
{
    vector<int> vc1{ 1,1,1,2,3,3,3,1,1 };
    vector<int> vc2{ 1,1,1,2,3,3,3,1,1 };
    vector<int> vc3{ 3,2,1 };
    
    sort( begin( vc2 ), end( vc2 ) );
    sort( begin( vc3 ), end( vc3 ) );
    
    cout << check( vc1 ) << endl;
    cout << check( vc2 ) << endl;
    cout << check( vc3 ) << endl;
    
    vector<int> res1, res2, res3;
    
    unique_copy( begin( vc1 ), end( vc1 ), back_inserter( res1 ) );
    unique_copy( begin( vc2 ), end( vc2 ), back_inserter( res2 ) );
    unique_copy( begin( vc3 ), end( vc3 ), back_inserter( res3 ) );
    
    for( auto &x : res1 ) cout << x << " ";
    cout << endl;
    for( auto &x : res2 ) cout << x << " ";
    cout << endl;
    for( auto &x : res3 ) cout << x << " ";
    
    return 0;
}

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

重複を除いた値だけを参照したい場合は std::unique_copy *2 を使って
back_inserter *3してあげると確認できました。

std::uniqueは隣り合った要素の重複しか除けない為、sort が必須 (おしまい)

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

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

*3:back_inserter - C++ Reference