読者です 読者をやめる 読者になる 読者になる

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

std::function|C++|STL

STL 未解決

std::function(C++11) の覚書

C++日本語リファレンスによると下記の通り↓

functionクラステンプレートは、パラメータの型リストArgTypes...、戻り値の型Rに合致する、あらゆる関数ポインタ、関数オブジェクト、メンバ関数ポインタ、メンバ変数ポインタを保持できるクラスである。*1

...難しいので理解出来る範囲でまとめると、
std::function< 戻り値の型(引数の型) > で宣言すると、関数オブジェクトを代入出来るっぽい。

#include <bits/stdc++.h>
using namespace std;
int sum( int n )
{
    return n + n;
}
int main()
{
    //関数 sum を変数 f に保存
    function<int(int)> f = sum;
    //保持している sum 関数を呼び出す
    cout << f( 10 ) << endl; //result 20
    
    //ラムダ関数を保存
    function<string(string)> s = [&]( string s ){ return s.substr( 2, 3 ); };
    cout << s( "wwcwwww" ) << endl; //result  cww
    
    return 0;
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

広告を非表示にする

No.7 プライムナンバーゲーム|yukicoder|メモ化再帰

yukicoder コード 深さ優先探索(DFS) 競プロ メモ化再帰 動的計画法 AND/OR木探索

No.7 プライムナンバーゲーム - yukicoder 1ヶ月半 かけて解きました。
(何故 1ヶ月かかったのかは後述)

題意:

・はじめに先攻プレイヤーに自然数 N が与えられます。
・N以下の素数のどれかで減算し相手に渡す、を先攻・後攻で交互に繰り返し、
 N が 0 か 1 になったら負けとなる。
・自分(先攻)が勝つ場合は"Win", 負ける場合は"Lose"を出力します。
・ゲームは互いに最善を尽くすものとする。
・2 ≤ N ≤ 10000

考察①:グラフを描く

まず、N = 7 の場合のプライムナンバーゲームの状態をグラフに描いて考えました。
先攻プレーヤーの持ち点 7とし、子ノードの値となるのは N - ( N 以下の素数 ) です。
N == 0N == 1 作った方が負けという観点から、 01受け取った方が勝ちと考えます。
ピンクの頂点が、先手勝ちとなる選択が存在する局面です。

f:id:chiwawa_star:20161225015416p:plain

この様に、ゲームの状態を頂点にして、遷移可能な状態を辺で結んだグラフを一般に ゲーム木 *1と呼びます。

ゲーム木上の子ノードの局面において、全ての値に対する勝敗のAND/ORを取ると、

先手番時先手勝ちが一つでもあれば先手勝ち(OR)
後手番時全て先手勝ちなら先手の勝ち(AND)

となる事が判ります。
この様に、2人で対戦し勝敗のみを気にするゲームのゲーム木をAND/OR木 *2 と呼びます。

以上を踏まえ、例に挙げた N = 7 の場合の勝敗( Win/Lose )を考えると、
下記図の様に 先手勝ち( Win ) となる事が判ります。

f:id:chiwawa_star:20161226000837p:plain

ここまで判ったら、ゲームに関する考察は終わりで、これをそのまま実装する事となります。*3

考察②:素数の準備

与えられた N から N以下の素数 で引く為、N 以下素数列挙が必要となります。
O( N^2 ) での列挙では TLE する為、O(N^2)より早くする必要があります。

素数列挙方法につきましては長くなる為、以下別記事に O( N√N ) verO( N log log N ) ver の2つを書きました。

O( N√N ) ver
O( N log log N ) ver

考察③:計算量を減らす

考察②までを終えて提出した結果、N = 9299 のケースでTLE してしまいました。
何が無駄かを考える為に、ここでもう一度 グラフ を見ます。

f:id:chiwawa_star:20161211172003p:plain

先手番時に同じ値を持つ部分木(黄色い頂点) が2回出現している事がグラフを見ると判ります。
この図は N = 7 の場合なので同じ値を持つ部分木の数が少ないですが、
N = 10000 の場合を考えると、もっと膨大な同じ値を持つ部分木が出現するのが予想できます。

そこで、一度訪れた頂点の勝敗結果記憶し、既に訪問済みであれば記憶した結果を返すようにする事で計算量を減らします。

それを一般に メモ化 と呼ぶようです。*4

実装:

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int N;
vector<int> P;
vector<vector<int>> visit( 2, vector<int>( 10001, -1 ) );//<---初期化!!!
void prime( int N )
{
    for( int i = 2; i <= N; i++ )
    {
        bool flag = true;
        for( int j = 2; j * j <= i; j++ )
        {
            if( i % j == 0 )
            {
                flag = false;
                break;
            }
        }
        if( flag )
        {
            P.emplace_back( i );
        }
    }
    reverse( P.begin(), P.end() );
}
bool dfs( const int T, const int N )
{
    if( N == 0 || N == 1 )
    {
        return T == 0 ? 1 : 0;
    }
    if( visit[ T ][ N ] >= 0 )
    {
        return visit[ T ][ N ];
    }
    if ( T == 0 )
    {
        for( const auto &x : P )
        {
            if( N - x >= 0 )
            {
                if( dfs( 1, N - x ) )
                {
                    visit[ T ][ N ] = 1;
                    return 1;
                }
            }
        }
        visit[ T ][ N ] = 0;
        return 0;
    }
    else
    {
        for( const auto &x : P )
        {
            if( N - x >= 0 )
            {
                if( !dfs( 0, N - x ) )
                {
                    visit[ T ][ N ] = 0;
                    return 0;
                }
            }
        }
        visit[ T ][ N ] = 1;
        return 1;
    }
}
int main()
{
    cin >> N;
    
    prime( N );
    
    cout <<  ( dfs( 0, N ) ? "Win" : "Lose" ) << endl;
    
    return 0;
}

まとめ:

考察 4 : 実装 6 くらいの割合で 1か月半 を消費した気がします。

考察では、グラフの基礎ゲーム木AND/OR木の概念を学習、ゲームの状態を考察するのにグラフも沢山描きました。

実装では、素数列挙のアルゴリズムエラトステネスの篩(ふるい)を学習したり、計算量を落とすメモ化も初めて書きました。
他にも実装面ではかなり細かい部分で消費しました。
(二次元配列の正しい要素数確保(今更)、メモリの概念(今更) とか...)

色んな学習要素が含まれている問題で、予想外に時間が掛かりましたが、
年内に AC 出来て良かったです(年内怪しいかな...って思ってた)。

※この記事を書いたのは昨年末です(公開するの忘れていた)

*1:ゲーム木 - Wikipedia

*2:http://ix9.jp/softcomputing/ai-4.shtml

*3:さらっと書いていますが、ここまでで半月以上を消費

*4:ACしてから知りました...。

No.476 正しくない平均|yukicoder

yukicoder 競プロ 競プロメモ

No.476 正しくない平均 - yukicoder を解きました。
std::accumulateの戻り値の型 にはまったのでメモ。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    long long A;
    cin >> N >> A;
    vector<long long> vc( N );
    for( auto &x : vc )
    {
        cin >> x;
    }
    cout << ( (double)accumulate( vc.begin(), vc.end(), 0LL ) / N == A ? "YES" : "NO" ) << endl;
    return 0;
}

accumulate *1で総和を正しく得られなかったのですが、
問題の制約を見ると、最大で 10^9 を 10回 加算する事を想定しなくてはいけませんでした。
int型の数値表現可能な範囲は、 -2,147,483,648 ~ 2,147,483,647 *2 なので、加算途中で桁あふれしてしまう事が判ります。

accumulate の計算途中および結果の型は、第3引数で指定します。
型を明示する為、サフィックス *3を初期値に付加します。
今回は long long にする為、第3引数0LLとしました。
(初期値の0とlong longのサフィックスであるLLを付加)
これでオーバーフローせず正しい戻り値を受け取れました!

std::accumulate の型
前項でも微妙に触れていますが、std::accumulate の戻り値の型は第三引数によって決まります。入力の範囲が long long 型だったとしても、初期値が int 型のリテラルである 0 であれば int 型として足し込んでいくのでオーバーフローしてしまいます。こういった場合は 0LL とサフィックスを付けて long long 型のリテラルにしてあげるとうまくいきます。

今すぐ使える C++ コーディングテクニック集 - torus711 のアレ
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    long long A;
    cin >> N >> A;
    vector<long long> vc( N );
    for( auto &x : vc )
    {
        cin >> x;
    }
    cout << ( accumulate( vc.begin(), vc.end(), 0.0 ) / N == A ? "YES" : "NO" ) << endl;
    return 0;
}

最初のコードでは第3引数を0LLとしてlong long型を明示しましたが、
accumulateの戻り値の型は、初期値として渡した値の型になる事を踏まえると、
第3引数に最初から double0.0 を渡すと、オーバーフローもせず、更に総和をキャストする事が不要となる様でした(学び)。

double型の仮数部は2^53個の数( = 9,007,199,254,740,991 )を表現出来る為、制約にも収まります。*4

ですが、浮動小数点数の演算に固有の誤差(丸め誤差、桁落ち、情報落ち)が常に生じる可能性がある *5 事を考慮すると、可能な限り整数での計算が好ましい様です。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    long long A;
    cin >> N >> A;
    vector<long long> vc( N );
    for( auto &x : vc )
    {
        cin >> x;
    }
    cout << ( accumulate( vc.begin(), vc.end(), 0LL ) == N * A ? "YES" : "NO" ) << endl;
    return 0;
}

なので結論としては、↑このコードが最適そう...(おわり)

ABC045 - B 3人でカードゲームイージー|AtCoder

AtCoder 競プロ

B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder を解きました。

題意:
・Aさん、Bさん、Cさんの3人でするカードゲーム。
・Aさんのターンからゲームは始まり、各自持っているカードに書かれている
 a, b, c それぞれの人のターンになる。
・カードの順序は入れ替え不可。
・ターンが来たら先頭から1枚カードを捨てれる。
・自分のターンでカードを 1 枚も持っていなければ、その人が勝ち(ゲーム終了)。
 ( 細かい制約は問題文へ )

解法:
問題文通りに実装したら解けました。
Aさん、Bさん、Cさんの持つカード数にバラ付きがあるので、それぞれ別のカウンタを用意したぐらいです。
(もっと簡潔な解き方があるかも知れません...)
計算量 O( |Sa| + |Sb| + |Sc| )

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    string A, B, C;
    cin >> A >> B >> C;
    
    string next;
    next.push_back( A[ 0 ] );
    
    int a{}, b{}, c{};
    while( true )
    {
        if( next == "a" )
        {
            if( A.empty() )
            {
                cout << "A" << endl;
                break;
            }
            next = *A.begin();
            A.erase( A.begin() );
            a++;
        }
        if( next == "b" )
        {
            if( B.empty() )
            {
                cout << "B" << endl;
                break;
            }
            next = *B.begin();
            B.erase( B.begin() );
            b++;
        }
        if( next == "c" )
        {
            if( C.empty() )
            {
                cout << "C" << endl;
                break;
            }
            next = *C.begin();
            C.erase( C.begin() );
            c++;
        }
    }
    return 0;
}

//自分用メモ
競技プログラミングを知ろう! [第1回]|Tech Book Zone Manatee

KUPC2013 A - 旧総合研究7号館|AtCoder

AtCoder 競プロ

A: 旧総合研究7号館 - 京都大学プログラミングコンテスト2013 | AtCoderを解きました。

題意:
・N個の改名後の校舎名と改名年度と、資料が作成された年度Qが与えられるので、
 Q年度の校舎の名前を出力する。
・平成元年度の校舎名は "kogakubu10gokan"
・1 ≤ N < 50
・1 ≤ Q ≤ 50
・2 ≤ year 1 < year 2 < … < year n ≤ 50
 ( その他細かい制約は問題文参照で )

解法:
年度は高々50年までしかないので、50 + 1 の配列を 平成元年度の校舎名 "kogakubu10gokan" で埋めて、その後改名された年度の校舎名で配列を上書きしてQ年度を出力する。
計算量はO( N )

#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++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
	int N, Q;
	cin >> N >> Q;
	vector<int> year( 50 + 1 );
	vector<string> name( N );
	REP( i, N )
	{
		cin >> year[ i ] >> name[ i ];
	}
	vector<string> res( 50 + 1 );
	string tmp = "kogakubu10gokan";
	REP( i, 50 + 1 )
	{
		REP( j, N )
		{
			if( i == year[ j ] )
			{
				tmp = name[ j ];
			}
			res[ i ] = tmp;
		}
	}
	cout << res[ Q ] << endl;
	return 0;
}


応用・発展:
例えば、Q の制約が 1 ≤ Q ≤ 10^9 だったらどう解く?と云う発展課題!
上記コードでは別配列を用意して 50 + 1 年分をわざわざ全て埋めたけれど、実はその必要は無く、指定されたQ年度の校舎名をそのまま返してあげれば良いだけ、という解法に至りました。
(なので上記コードは無駄な事をしている事が判った...)

#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++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
	int N, Q;
	cin >> N >> Q;
	vector<int> year( N );
	vector<string> name( N );
	REP( i, N )
	{
		cin >> year[ i ] >> name[ i ];
	}
	year.emplace_back( 51 );
	string res = "kogakubu10gokan";
	REP( i, N + 1 )
	{
		if( year[ i ] <= Q && year[ i + 1 ] > Q )
		{
			res = name[ i ];
		}
		if( Q > year[ N - 1 ] )
		{
			res = name[ N - 1 ];
		}
	}
	cout << res << endl;
	return 0;
}

loop 1個減ったのですが、こちらも計算量はO( N )。
2つのコードを比較する為に書き示すとしたらO( year* N )。

計算量(ステップ数)とO記法は別の概念というのをなんとなく覚えました。

※記事中の計算量にご指摘がある場合はご連絡ください...