2017-03-19

ARC070 D - No Need

競プロ AtCoder

arc070.contest.atcoder.jp

解法（証明？）

a[i] を降順にソートする．
今，a[i] が不必要かどうかを判定したいとする．この時，Si := a[1] + a[2] + ... + a_[i] とおく．
また，a[n] から a[i + 1] までの和で表現できる K 未満の数がわかっているとする．（dpで保存）
その中の任意の数 t について，t + Si < K であるならば，それは不必要な数である．
必要条件は明らか．なぜなら，t + Si < K が成り立つならば，a[i] を用いた和で K 以上となるものは，存在しないか，あるいはもともと K 以上であるかのどちらかだからである．
十分条件について示す．これは対偶を取れば良い．つまり，「必要な数ならば t + Si >= K が成り立つ」を示せば良い．
t + a[i] >= K ならば，a[i] を取り除けば K 未満となる和の作り方が存在することになるので，t + a[i] < K であると考えて良い．
ここで，数列 a が降順にソートされていることに注目すると，ある j があって t + (a[j] + ... + a[i]) >= K かつ t + (a[j + 1] + ... + a[i]) < K がなりたつ．この時，a[i] > a[j] だから， t + (a[j] + ... + a[i - 1]) < K が成り立つ．これは a[i] が必要な数であることに他ならない．
以上より，示された．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
 
int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for(int i=0; i<N; ++i) {
        cin >> a[i];
    }
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    sort(a.rbegin(), a.rend());
    int res = 0;
    vector<bool> dp(K);
    dp[0] = true;
    for(int i=0; i<N; ++i) {
        bool f = false;
        for(int j=0; j<K; ++j) {
            f |= dp[j] && j+sum >= K;
        }
        if(!f) {
            res++;
        }
        sum -= a[i];
        for(int j=K-1-a[i]; j>=0; --j) {
            dp[j+a[i]] = dp[j+a[i]] | dp[j];
        }
    }
    cout << res << endl;
}

2016-12-28

2016年を振り返る

年末

Twitterのハッシュタグで，「#一年の思い出を月別で振り返る」ってのがあったんですが，なんとなく自分でもやってみようと思ったのでブログに書くことにした．

1月

浪人していたので，センター試験の勉強をしていた気がします．してたかな？してなかったかも……．予備校の自習室の近くにネコのたまり場があったので，そこへ行くついでに自習室で勉強してました．

1月下旬は，センター試験で見事にボコボコにされてつらい気持ちになってたような気がします．

2月

さすがに遊べるような身分でもなく，普通に2次試験の勉強をしてました．時々，友人と予備校近くのフードコートで傷を舐め合ったり，傷口に塩を塗り合ったりしてました．

あれ？他の記憶が無い．なんでや．

3月

前期試験の発表前に中期日程の試験を受けたり，なんやかんやで受かってたり（親が喜んでくれてたので良かった）して一息つけた時期．受かってからはほどほどに遊んでました．

入学の手続きがややこしくて結構手こずってたな～．

4月

入学式も終え，これからの生活に（まだ）期待と不安を抱えていたころ．なんとか友人も作れた（そして偶然全員オタクだった．類は友を呼ぶんですねぇ……）し，授業も（微分積分学以外は）なんとかなりそうだったので，すこし安心してました．

入ろうと思っていたサークルの雰囲気もよくて，シュッと参加しました．良かったよかった．

余談ですが，この時期の学食混みすぎ．飯食うってレベルじゃねえぞ．

5月

大学生活に慣れてきてしまった緩みからか，不幸にも講義をぶっちしてしまう学生が目立ち始める．それにつられないように必死で講義に出ていた記憶があります．べつに講義に出ること自体は重要じゃないんですが，なんだかんだいって単位は無いよりあったほうが後々楽なので，頑張ろうと意気込んでました．

サークルでは競プロをやっていて，自分は殆ど初心者だったのでついていくのが大変でしたね．あとはC++の勉強をする読書会があったのでそれにも参加してました．

6月

気が緩み始める．いやね？一限にね？語学入れられたって出られないと思いますよ？僕は頑張ったほうだよ．うん．一限語学は人権侵害．

このころは友人宅で麻雀をうちまくっていた．うちの学科の人間，麻雀打てる人がめちゃんこいてびっくらこいた．しかも上手いし．なにもんだよ．

7月

テスト前で今までサボっていたつけが回ってくる．ちゃんと勉強しておけばよかった．お前は浪人時代に何を学んだんだという感じ．

でもなんとか乗り切る．やればなんとかなるもんですね．

8月

夏休み．何してたか記憶にない．空白の一ヶ月である．

あ，大洗に友人と旅行に行ってたか．楽しかったです（小並感）

9月

大半が免許合宿で埋まる．福井にいったんだけど，いいところだった．福井駅前とか，人は少ないし，でも店はそれなりにあるし，交通アクセスもまぁ良かったしで満足だった．免許も無事取れたしめでたしめでたし．

10月

夏休み気分を捨ててなんとか講義には出る．相変わらず微積がつらい．

この月の記憶も全然ないなぁ．競プロに本格的に取り組み始めたのがこの時期だったかもしれない．

11月

10月と大差なし．単調な（かといってつまらなくはない）生活が続く．

CODE FESTIVAL 2016の本戦に行けることになる．同回生ではビリの成績だったけど，本戦はコンテンツが充実していてすごくいい経験になった．来年もまた行けたらいいなぁ．

サークルでプロにハラスメントを受ける．ハラスメントダメ，ゼッタイ．はやくプロになりたい．

12月

なんとなく勉強する気になって，地に足の着いた勉強をするようになる．サボれる講義は積極的にサボるようになった（出席をしないという意味）．

サークルでは相変わらずハラスメントの応酬が繰り広げられていたけど，さすがに4月よりは僕も含めてみんな強くなってるなぁという感じはする．

AOJ-ICPCの350までほとんど埋まる（やったー）

最後に

来年のことは来年の僕がそのときどきでうまいことやってくれるでしょうから，あまり考えないことにしました．

それではみなさん，よいお年を．

2016-10-08

int とlong long のビット演算でハマった話

C++

#include <iostream>
#include <bitset>
using namespace std;
using ll = long long;

int main() {
    ll a = 0, b = 0, c = 0;
    for(int i=0; i<32; ++i) {
        a |= (1 << i);
    }
    for(int i=0; i<32; ++i) {
        b |= (1ll << i);
    }
    c |= (1 << 31);
    cout << bitset<64>(a) << endl;
    cout << bitset<64>(b) << endl;
    cout << bitset<64>(c) << endl;
}

Output:

1111111111111111111111111111111111111111111111111111111111111111
0000000000000000000000000000000011111111111111111111111111111111
1111111111111111111111111111111110000000000000000000000000000000

つらい．ちゃんと確認しような．

2014-08-19

C++11で始めるマルチスレッドプログラミングその1 ～std::thread事始め～

C++

この記事は、C++11におけるマルチスレッドプログラミング入門記事という位置づけで書かれたものです。簡単のため、表現が曖昧になったりしている部分があると思いますが、もっと厳密に知りたいという方はC++の規格を参照してください。

C++11のマルチスレッドライブラリ

C++03までは、マルチスレッドプログラミングを行うための言語機能やライブラリが標準で用意されていませんでした。そのため、プログラマはしばしばプラットフォームに依存したコードを書く必要がありました。

しかしC++11から、thread-aware memory modelなどの定義や、マルチスレッドをサポートするための言語機能とライブラリが導入されました。これによって、プログラマは抽象度の高いコードを用いてマルチスレッドプログラミングを行うことが容易になりました。

本記事では、事始めとしてstd::threadを用いて簡単なプログラムを書いていきます。また、ソースコードの例ではインクルードファイルを省略しているので、手元の環境でテストしたい方は注意してください。

std::thread事始め

スレッドを新たに作成するためには、std::threadを使います。具体的には、std::threadのコンストラクタで、第一引数に、別スレッドで処理させたい関数や関数オブジェクトを渡し、第二引数以降には第一引数で与えられた関数に適用する引数を渡して新たなスレッドを作成することになります。つまり、std::thread(callable_object, args...)のように引数を与えると、別スレッドでcallable_object(args...)の処理が行われるということになります。
また、std::thread内部では、コンストラクタで作成されたスレッドを保持し、std::threadオブジェクトと関連づいています。
以下が、std::threadを用いたプログラムの例になります。joinとdetachについては後に解説します。

void process() {
    //...
}

int main() {
    int i = 0;
    std::thread t1(process); // 別スレッドでprocessの処理を行う
    std::thread t2([&i](int x) {
        int counter = 0;
        while(counter++ < x) {
            i += counter;
        }
    }, 10); // 関数オブジェクトの引数に10を渡す
    t1.detach(); //スレッドt1の管理を放棄
    t2.join(); //スレッドt2の処理が終了するまで待機
    std::cout << i << std::endl;
}

出力

joinとdetach

std::threadを一度作成すると、必ずjoin()またはdetach()を呼ばなければなりません。さもなくば、std::terminateでジ・エンドです。
また、一度join()またはdetach()が呼び出されて、空の状態になったstd::threadに対して、再度join()、detach()を呼び出してはなりません。

join

join()を呼び出すと、join()が呼び出されたスレッド(上の例ではt2)の処理が終了するまで、join()を呼び出したスレッドはブロックされます。上の例だと、t2の処理が終わるまで、iの出力が行われることはありません。
また、join()を呼び出して処理が終了したthreadオブジェクトは、どのスレッドもささない空のthreadオブジェクトになります。
threadオブジェクトがjoin()を呼び出せる状態かどうかは、joinable()メンバ関数で確認できます。

detach

detach()を呼び出すと、threadオブジェクトとスレッドの関連を切り離すことができます。切り離されたthreadオブジェクトは、join()の呼び出し後と同様に、何もささない空のthreadオブジェクトとなります。また、切り離されたスレッドは、そのまま処理が続行されますが、他のスレッドから一切干渉することができなくなります。
threadオブジェクトがdetach()を呼び出せる状態かどうかは、join()同様、joinable()メンバ関数で確認できます。

RAIIを用いてjoin()、detach()の呼び出し忘れを防ぐ

先に述べたとおり、threadは必ずjoin()またはdetach()が呼び出されなければなりません。しかし直にjoin()やdetach()を呼び出すコードは、例外機構との相性が悪いです。例えば、以下のコードではjoinが呼び出されない可能性があります。

std::thread t([] { /*...*/ });
some_process(); // 例外が投げられうる
t.join();       // some_processで例外が投げられると呼び出されない

これを防ぐために、RAIIを用いてjoin()やdetach()を呼び出す仕組みがあります。以下のthread_guardがその一例です*1が、他にもBoostのscoped_guardなどがあるので、調べてみてください。

class thread_guard {
    std::thread& t;
public:
    explicit thread_guard(std::thread& t_) : t(t_) {}
    ~thread_guard() {
        if(t.joinable()) {
            t.join();
        }
    }
    thread_guard(thread_guard const&) = delete;
    thread_guard& operator=(thread_guard const&) = delete;
};

int main() {
    std::thread t1([]{ /* ... */ });
    thread_guard tg(t1);
    some_process();
} // 例外が投げられてもjoinが呼ばれる

threadの委譲

std::threadは、noncopyableかつmovableなクラスです。ムーブすると、スレッドの管理を別のthreadオブジェクトに委譲することができます。

std::thread t1([]{ /* ... */ });
std::thread t2;
// t2 = t1;  Error
t2 = std::move(t1); // ok

ただしこの時、委譲される側のthreadは何もささない空のthreadオブジェクトである必要があります。そうでない場合、std::terminate()が呼ばれます。
委譲する側のthreadは、ムーブの後なにもささない空のthreadオブジェクトになります。

threadの識別

スレッドに関連付けられている各threadは、IDづけがされており、それによって識別することができます。自身のスレッドのIDは、std::this_thread::get_id()を呼び出すことで得られます。
得られるIDの型はstd::thread::idですが、これは自由にコピーしたり、比較したりすることができます。
デバッグに使ったり、mapのkeyに使ったり、いろいろな用途に使えます。
スレッドに関連づいていないthreadオブジェクトのget_id()を呼び出すと、デフォルトコンストラクトされたstd::thread::idが得られます。

std::thread t1([]{ /* ... */ });
assert(t1.get_id() != std::thread::id());
std::thread t2;
assert(t2.get_id() == std::thread::id());
// 出力もできる
std::cout << t1.get_id() << std::endl;

おまけ:スレッドの数はどれぐらいにすべき？

当たり前ですが、スレッドを増やせば処理がその分処理が早くなるわけではありません。ハードウェアのCPUのコア数や、コンテキストスイッチ、OSのリソース等、考えることはたくさんあります。
スレッドの数の指針としては、std::thread::hardware_concurrency()の値を参考にするといいと思います。もちろん、速度の向上以外にも、マルチスレッドにする理由はあるので(GUIとか)、ケースバイケースといってしまえばそうなってしまうのですが…。

追記

雑に続きを書きました．
C++11で始めるマルチスレッドプログラミングその2 std::mutex 編 - すいバカ日誌

*1:インターフェースとしては不十分なので、あくまで例と考えてください。

2014-06-06

例外安全について簡単にまとめた

https://github.com/Suikaba/publications/tree/master/exception-safety

例外安全について簡単にまとまっているものがあまり見受けられないので、作ってみた.
とはいったものの、僕はC++に疎いので、間違いがあるかもしれません.
その時は指摘をお願いします.

追記(2014/08/21).
heisseswasserさんのご指摘をうけ、資料の一部を修正しました.具体的には以下の部分を修正しました.

2.12.3 の stack unwinding についての補足の部分で、gotoの記述に誤りがあったのを修正. また、頂いた情報を元に、longjmpについても加筆.

2014-03-22

Boost.Serialization - BOOST_CLASS_VERSION

C++ Boost

以下のコードを書いたとする.

namespace foo {

class bar {
    // ...
private:
    // serialize の実装
};

BOOST_CLASS_VERSION(bar, 1);
}

すると、以下の様なエラーが大量に出てくる.

error: 'foo::boost::**' has not been declared

どうやらこれはBOOST_CLASS_VERSIONをグローバル名前空間に書かないと起こるようである.
実装を読んでいないのではっきりとは言えないが、BOOST_CLASS_VERSIONを用いる際は名前空間の外にだそう.

namespace foo {
// ...
}
BOOST_CLASS_VERSION(foo::bar, 1);

2013-12-17

using と using namespace

C++

Twitterでこういうコードを見かけた。

#include <utility>
 
namespace N {
	using namespace std;
	class C {};
	void swap(C&, C&) {}
	void f() {
		int n1 = 1;
		int n2 = 2;
		swap(n1, n2); // compile Error
	}
}
 
int main() {
	N::f();
	return 0;
}

これはコンパイルエラーになる。だが、using namespace std;を using std::swapにすると正しく動く。それはなぜか。
using declaration(using std::swap)は現在のコンテキスト内にswapを提供する（この場合N内）が、using directive(using namespace std)はグローバルnamespace、すなわちglobal namespace(::)にstd名前空間内の変数やら関数が提供される。
コードに戻ろう。もし仮にusing namespace std;としていた場合を考える。swap(n1, n2)が呼ばれたタイミングでは、まずnamespace N内のswapを照会する。そして、今回それが見つかる。こうなるとここでLookupはおしまい、つまりglobal namespaceまでswapを見に行かないので、std::swapがそもそも候補に入ってない。結果、swap -> C& -> C& -> void が呼ばれてCompile Errorになる。
using std::swapとすれば、std::swapがN名前空間内に提供されるので、std::swapが正しく呼び出される。なのでコンパイルが通る。

確かこんな挙動だったと思いますが、間違ってたら誰か教えてください。