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

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

ABC062 A - Grouping|AtCoder

A: Grouping - AtCoder Beginner Contest 062 | AtCoder を解きました。
A 問題ですが、学びがあったのでメモ。

題意

・1 から 12 までの整数が下記のようにグループ分けされています。

  • 1, 3, 5, 7, 8, 10, 12
  • 4, 6, 9, 11
  • 2

・整数  x, y \, ( 1 ≤ x < y ≤ 12 ) が与えられるので、 \it x, \it y が同一のグループに属している場合 Yes を、そうでない場合は No を出力する。

コード:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, y;
    cin >> x >> y;
 
    int cnt1{}, cnt2{};
    for( auto &i : vector<int>{ 1, 3, 5, 7, 8, 10, 12 } )
    {
        if( i == x || i == y ) cnt1++;        
    }
    for( auto &i : vector<int>{ 4, 6, 9, 11 } )
    {
        if( i == x || i == y ) cnt2++;        
    }
    cout << ( cnt1 == 2 || cnt2 == 2 ? "Yes" : "No" ) << endl;
}

実装を少し考えてみたけれど、自分ではこれ以上簡潔に書けなくて、
AC した後、他の方の提出を見たらグループ番号を持たせるという工夫があり、学びでした。

  • 1, 3, 5, 7, 8, 10, 12 ➡︎ グループ 0
  • 4, 6, 9, 11 ➡︎ グループ 1
  • 2 ➡︎ グループ 2

↑上記のようにグループ番号( 0, 1, 2 )を付加します。(番号は何でも良い)
↓そして、 1 から 12 までの整数を昇順に並び替えグループ番号で配列に持ちます

vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 }

この時、制約より x0 が与えられる事はないので、適当に -1 とかで vc[ 0 ] を埋めておく。
これにより、vc[ x ] vc[ y ] がどのグループか  O( 1 ) で知る事ができ、一致判定が可能となる訳です。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
    
    int x, y;
    cin >> x >> y;
    
    cout << ( vc[ x ] == vc[ y ] ? "Yes" : "No" ) << endl;
}

↑コードが凄く簡潔になりました!

std::equal_to|C++|STL

std::equal_to の覚書

C++日本語リファレンスによると下記の通り↓
メンバ変数を持たず、状態を保持しないとのこと。

equal_toクラスは、等値比較を行う関数オブジェクトである。*1

equal_to< 型 >()( left, right ); で、指定した型による left == right の比較が行われ、
bool 値( 0 / 1 )が返ってくる様です。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //int
    for( int i = 0; i < 3; i++ )
    {
        cout << i << ":" << equal_to<int>()( i, 2 ) << endl;
    }
    cout << endl;
    //string
    vector<string> vc{ "NO","YES","NO" };
    for( int i = 0; i < 3; i++ )
    {
        cout << i << ":" << equal_to<string>()( vc[ i ], "YES" ) << endl;
    }
    return 0;
}

実行結果はこちら

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //int
    auto f = [ = ]( int x ){ return x == 2; };
    for( int i = 0; i < 5; i++ )
    {
        cout << i << ":" << f( i ) << endl;
    }
    cout << endl;
    //string
    vector<string> vc{ "NO","YES","NO" };
    auto f2 = [ = ]( string x ){ return x == "YES"; };
    for( int i = 0; i < 3; i++ )
    {
        cout << i << ":" << f2( vc[ i ] ) << endl;
    }
    return 0;
}

実行結果はこちら

ラムダでも同じ感じで書けました◎
(単にラムダを書く練習です...)

std::equal_to の使い所はまだ思い浮かばないのですけど、
使うとしたら、std::all_of *2 との合わせ技で使う例を見たので、
vector 等に入った要素の比較判定とかで使えそうではあります。

std::function|C++|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|メモ化再帰

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

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;
}

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