C++で多倍長整数！

C++で多倍長整数が使える事をコンテスト中に知ったのでメモ。
でも標準ライブラリではなく、boost (オープンソースライブラリ) を使う様です。

参考）Chapter 1. Boost.Multiprecision - 1.53.0
参考）多倍長整数 - boostjp

cpp_int はメモリが許す限り無限の桁数を扱える型。

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp> // <-- add!!!
using namespace std;
using namespace boost::multiprecision; // <-- add!!!
cpp_int sum( cpp_int N )
{
	if( N == 0 ) return 1;
	else return N * sum( N - 1 );
}
int main()
{
    int N;
    cin >> N;
    
    cout << sum( N ) << endl;
}

実行コード：[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

↑1000! もちゃんと全桁出力できる(感動)

( AtCoderでは boost バージョン: 1.60.0 が使える！ *1 )

*1:http://abc051.contest.atcoder.jp/rules

WUPC2012 A - 招待状｜AtCoder

A: 招待状 - WUPC 2012 | AtCoderを解きました。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    vector<int> M{ 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    int MM1, DD1, MM2, DD2;
    cin >> MM1 >> DD1 >> MM2 >> DD2;
    //受け取った日と開催月が同じ場合は開催日-受け取った日
    if( MM1 == MM2 )
    {
        cout << DD2 - DD1 << endl;
        return 0;
    }
    //メールを受け取った日の月の｢日数｣を算出(受け取った日を含むので +1 する)
    int res = ( M[ MM1 ] - DD1 ) + 1;
    //メールを受け取った日の月と開催日"以外"の月の｢日数｣を足す
    for( int i = MM1 + 1; i <= MM2 - 1; i++ )
    {
        res += M[ i ];
    }
    //開催月の開催日までの｢日数｣を足す(開催日は含まないので -1 する)
    cout << res + ( DD2 - 1 ) << endl;
    return 0;
}

2016年 進捗大反省会

今年の振り返りをカテゴリ別に書き残そうと思います。

C++ について：

C++ を勉強し始めて、１年が経ちました。
春頃に range-based for *1 を覚えてから何故か劇的に C++力 が伸びました。
一気に vector, map, set などのコンテナを使える様になって出来る事の幅も広がりました。
STL や algorithm header にある関数も実際使う機会があると楽しくて、色々と覚えました。

それから、ラムダ式も覚え、苦手だった処理の関数化も出来る様になりました。

1年前と比較してコードもだいぶ綺麗になりました。(可読性的に)
C言語から勉強を始めた為、変数宣言をまとめて文頭でする癖があったのですが、きちんとスコープを考慮して書ける様にもなってきました。(実はこれが結構大変でした)

全体的には1年で基礎的な事を学習出来た気がします。
(C++というよりプログラミングの基礎？かも)

競プロについて：

競プロについては、進捗は少ししか出せなかったです。
現状はABCのC が全然埋められていないです。*2
3月末に ARC-A 埋めが終了して、ABC-C 埋めに移行しましたが、16問しか埋められていません。
原因としては、基本的なアルゴリズムの知識が無い事だったので、今年の後半は主にアルゴリズムの勉強をTLE本を使ってしていました。
とは云え、日々問題を解かないとC++力も低下しそうだし、適度な問題を解く事( C++を書く事 )と、アルゴリズムの勉強との両立が出来ず悩んだ時期もありました(本当に時間が足りない)。
最近は、自分に合ったアルゴリズムの勉強の仕方(？)も徐々に判って来て、DFSならDFSのタグが付いた問題を探して、勉強しつつ問題を解く、みたいな勉強方法に帰着できました。

それから、問題をしっかり｢考察｣する事を覚え始めました。
考察をするにあたって｢計算量｣を見積もるという事も必要になってきたので、最近の勉強内容は専ら｢考察｣と｢計算量｣を考えるのが中心です。

コード面での大きな変化と言えば、REPマクロを含む、競プロ テンプレートを使う様になった事です。*3
自分が使う様になって、それまで全然読めなかったプロのコードが読める様になったのは凄く良かったですね。

AC埋め的には、前半はARC-A埋め, 後半はAOJ, codeforces, yukicoder を良く解いていました。

AOJでは、文字列の問題を解いていました。(苦手だったので強化していた)

codeforcesは、解いた人が多い順にsortして解きました。
簡単な問題が多かったですが、コードは簡潔か、もっと便利なSTLで解けないか、プロのコードと比較してどうか、など C++ の勉強も含め1問1問丁寧に復習(解き直し)をしました。
結果、STLを多少使える様になったと思います。(そしてSTL大好きになった)
それから競プロの小技コード？みたいなのもこの頃覚え始めました。*4
全く同じコードでAC出来る問題も発見しました。(驚いた)
Problem - 379A - Codeforces ／ Problem - 460A - Codeforces

yukicoderは｢★1 全然解ける問題ない...｣って良く呟いていたのですけど、
ある時「あれ、解けるな(？)」みたいな時期が到来して一気に★1を解きました。
この頃、map と set を無駄に使いまくっていて禁止されました(懐かしい)
(配列外参照が起きない為凄く都合が良かった)
それからは vectorファースト な日々を送っています(多分)。
★2も色々な人を巻き込みながら数問解きました。(市バス *5 は楽しかった)

AC数まとめ 2016

• AtCoder ABC & ARC
• 115
• AOJ
• 17 *
• codeforces
• 52
• yukicoder
• 80
• codechef
• 2
• Topcoder
• 3

※AOJはカウントされないvolumeがあった(悲)

AC数を書き出したら凄く少なかった(もっと解いている感あった)
codeforces, yukicoder あたりは解き直しをしていたので結果的に1問に凄く時間をかけていて、AC数には結び付かなかったかも知れません。

技術書：

2016年は C++ の本に加え、競プロの本(アルゴリズム系)も増えました。
本屋の技術書コーナーにも良く足を運びました。

・リーダブルコード
・C++ランゲージ クイックリファレンス
・STL標準講座
・TLE本(アルゴリズムとデータ構造)
・チーター本
・すごいHaskellたのしく学ぼう！

本は昨年結構揃えたので今年はそんなに激増はしませんでしたね。*6

エディタ：

MacなのでずっとXcodeを使っていたのですけど、bits/stdc++.h が使えない為、いつの間にか使わなくなりました。
Visual Studio Code も少し使ってみましたが、結局、Vim を使っています。

結果的にはWandBox + Vim で落ち着きました。

2017年 タスク：

意識低いので目標は決めず、タスクとして列挙します。

・アルゴリズムの基礎学習
・DPを覚えて｢カップ麺生活｣をACする
・TopCoderのSRM Div2-Easy 埋め
・ABC-C 埋め
・プロのコードを沢山読んで学ぶ
・きちんと考察をする
・計算量を見積もれる様になる
・日本語力向上
・会話のキャッチボール
・論理的文章が書けるようになる
★本を読んで体系的に学ぶ
★専門用語は都度クリアにする

来年末、これを元にまた進捗反省会します！

御礼：

今年も様々な方に大変大変お世話になりました。
競プロのプロの方々、強いC++erの方々にはいつもご助言を賜り、感謝しかありません。
来年も引き続き勉強していく所存ですので、叱咤(激励)宜しくお願いいたします！

*1:本の虫: n2930: Range-based for loopについて

*2:http://kenkoooo.com/atcoder/?kind=user&name=chiwawa_star

*3:cpp macro template - C++競プロ学習日記(仮)

*4:今すぐ使える C++ コーディングテクニック集 - torus711 のアレ

*5:No.154 市バス - yukicoder

*6:今年読んだ技術書 Advent Calendar 2015 - C++競プロ学習日記(仮)

SRM 602 Div2 Level-1 250：TypoCoderDiv2

SRM 602 div2 250：TypoCoderDiv2 を解きました。

題意：
TypoCoderには2種類の Rating がある。
Brown ➡︎ 1200以上
Ciel ➡︎ 1200以下
ただし新しい参加者は Rating 500 スタート。
N回分のコンテスト参加後の Rating が与えられるので何回色が変わったかを出力する。

解法：
初期値 500 からの変動もカウントに入る為、初期値 500 を 配列の先頭( rating[ 0 ] ) に加えてから1200以上と以下の変動で場合分けをする。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

struct TypoCoderDiv2
{
    vector<int> rating;
    int count( vector<int> rating )
    {
        int cnt{};
        rating.insert( begin( rating ), 500 );
        REP( i, (int)rating.size() - 1 )
        {
            if( rating[ i ] >= 1200 && rating[ i + 1 ] < 1200 ) cnt++;
            if( rating[ i ] < 1200 && rating[ i + 1 ] >= 1200 ) cnt++;
        }
        return cnt;
    }
};

C++で素数列挙！エラトステネスの篩 編

C++で素数列挙！O( N√N )編 を書きましたが、
今度はもっと高速な エラトステネスの篩(ふるい)編 *1 を書いたのでコードを残します。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#include <vector>
std::vector<int> Eratosthenes( const int N )
{
    std::vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}
int main()
{
    int N;
    cin >> N;
    for( const auto &x: Eratosthenes( N ) )
    {
        cout << x << " ";
    }
    return 0;
}

ベースは 蟻本 P112 の「素数の個数」を求めるというコードです。
上記コードは、素数を pick upして vector に格納すると云うものです。
計算量はO( N log log N )だそうです。(蟻本 P112より)

実行確認：[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

*1:エラトステネスの篩 - Wikipedia