2014 Yandex.Algorithm Elimination Stage, Round 2 A - Cycles with Common Vertex

問題文

http://codeforces.com/gym/100453

問題概要

n 個の鎖が与えられ，それぞれのサイズは c_i である．
鎖とは，連結グラフであり，かつ両端点以外の頂点の次数が2であるものである．
これらの鎖を，鎖とは別に用意した1つの頂点 X に，その両端をつなげる．
こうしてできたグラフ（Xに輪っかがいっぱいついてるみたいなグラフ）の何箇所かを黒で塗る．
ただし，任意の黒で塗られた頂点間の最短距離が K 以上となるように塗らなければならない．
このとき，最大何箇所を黒で塗ることができるか？

・制約
1 <= N <= 10^5
1 <= K <= 10^5
K <= c_i <= 10^9

解法

各輪っかのサイズは c_i + 1 になり，K個置きに黒く塗る．
すると，各輪っかについて，黒く塗られていない最大の連続した部分があるはずである．
その部分の真中に，X が来るようにする．
すると，X から各鎖について，黒く塗られている場所までの距離は K/2 以上となる（ただし，K / 2 は整数での割り算であり，切り捨てである）．
したがって，このように配置すれば，異なる鎖に含まれる黒同士の距離は K / 2 * 2 以上となり，基本的に最大に色をぬることができる．

ただし，切り捨てであるから，実際は K / 2 == (K - 1) / 2 となる鎖がいくつか含まれる可能性がある．
そのような鎖の数を M とすると，それらのうちから M - 1 個選んで，黒く塗る箇所を1つ諦めるしかない．

以上で，O(N) で解けた．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> c(N), space(N);
    int cnt = 0;
    for(int i = 0; i < N; ++i) {
        cin >> c[i];
        space[i] = (K + ((c[i] + 1) % K)) / 2;
        cnt += space[i] * 2 < K;
    }

    ll ans = 0;
    for(int i = 0; i < N; ++i) {
        ans += (c[i] + 1) / K;
    }
    ans -= max(0, cnt - 1);

    cout << ans << endl;
}

感想

A問題にしては難しくない？若干迷走してしまった．

2014 Yandex.Algorithm Elimination Stage, Round1 F - Data Mining

問題文

http://codeforces.com/gym/100448

問題概要

n 個の要素からなる数列 a が与えられる．あなたは以下の操作を k 回行える．

• ある要素の値を隣接する（どちらかの1方の）要素に加える．

k 回の操作の後の，数列に含まれる値の最小値を最大化せよ．
また，出力はその値を 10^9+7 で割った余りで出力するものとする．

・制約
1 <= n <= 10^4
1 <= k <= 10^6
1 <= a_i <= 10^8

解法

K < N の時は，どう頑張っても a の K + 1 番目の値より大きく出来ず，また逆にこれを実現する分配方法が存在するので，ソートして K + 1 番目の値を出力する．

K >= N のときは，できるだけでかい隣接2項を互いに足し合わせまくって，最後の N - 1 回で残りに足していく感じ．
どの隣接2項が良いかを考えるのだが，互いに足し合わせる操作は N - K + 1 回行われることを考えれば，ある a[i] と a[i + 1] を選んだときの答えは
fib(N - K + 1) * min(a[i], a[i + 1]) + fib(N - K + 2) * max(a[i], a[i + 1])
である．
これが一番大きいものを選べばよいのだが，N - K + 1 が大きいとオーバーフローして計算できないので，long double でごまかす．
とはいっても十分小さい K に対してはフィボナッチ数の比が黄金比に十分近づいていないので，愚直にやらないといけない．
具体的には，N - K + 1 > 40 のとき（これはかなり雑で，オーバーフローギリギリを狙うのが良いと思う），黄金比を φ として
min(a[i], a[i + 1]) + ma(a[i], a[i + 1]) * φ
の大きさで一番大きい i を選択する．
あとは先の値を mod で計算すれば答えになる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

constexpr int mod = 1e9 + 7;

int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    if(k < n) {
        sort(begin(a), end(a));
        cout << a[k] << endl;
    } else {
        vector<ll> fib(k + 1);
        fib[1] = fib[2] = 1;
        for(int i = 3; i < k + 1; ++i) {
            fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
        }
        ll ans = 0;
        if(k - n + 2 <= 40) {
            for(int i = 0; i + 1 < n; ++i) {
                ans = max(ans, fib[k - n + 1] * min(a[i], a[i + 1]) + fib[k - n + 2] * max(a[i], a[i + 1]));
            }
            ans %= mod;
        } else {
            const ld phi = (1.0 + sqrt(5.0)) / 2.0;
            int pos = 0;
            ld val = 0;
            for(int i = 0; i + 1 < n; ++i) {
                if(val < min(a[i], a[i + 1]) + max(a[i], a[i + 1]) * phi) {
                    pos = i;
                    val = min(a[i], a[i + 1]) + max(a[i], a[i + 1]) * phi;
                }
            }

            const ll mi = min(a[pos], a[pos + 1]);
            const ll ma = max(a[pos], a[pos + 1]);
            ans = (((fib[k - n + 1] * mi) % mod) + ((fib[k - n + 2] * ma) % mod)) % mod;
        }

        cout << ans << endl;
    }
}

感想

誤差が不安だったけど，fib(41) / fib(40) の比率がもうほとんど正確な黄金比に近い値になっているので大丈夫なんでしょうきっと．

2014 Yandex.Algorithm Elimination Stage, Round1 E - Burger Bar

問題文

http://codeforces.com/gym/100448

問題概要

n 個の要素からなる数列 a が1つ与えられる．
以下を満たす集合 X のうち，最小の |X| をもとめよ．

• X = {b_1, ..., b_k} とすると，任意の a の要素は，Xの要素のうちからいくつか選んで足し合わせて作ることができる（ただし，おなじ i に対して b_i を2回使うことはできない）．

・制約
1 <= n <= 20
1 <= a_i <= 50

解法

a_i のサイズが高々50であるから，解の上界は6である．
50C5 = 2 * 10^6 ぐらいなので，5個までを適当に全探索しても間に合いそう．
多分条件を満たすXがたくさんあるので，条件を満たすかチェックする分のオーダーを入れてもそんなに遅くないと思う．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> used;
    function<bool(int)> can_make = [&](int limit) {
        if((int)used.size() == limit) {
            vector<bool> dp(51, false);
            dp[0] = true;
            for(int i = 0; i < limit; ++i) {
                for(int j = 50 - used[i]; j >= 0; --j) {
                    dp[j + used[i]] = dp[j + used[i]] | dp[j];
                }
            }
            bool ok = true;
            for(int i = 0; i < n; ++i) {
                ok &= dp[a[i]];
            }
            return ok;
        } else {
            for(int i = (used.size() == 0 ? 1 : used.back() + 1); i <= 50; ++i) {
                used.push_back(i);
                if(can_make(limit)) {
                    return true;
                }
                used.pop_back();
            }
            return false;
        }
    };

    int ans = 6;
    for(int i = 1; i <= 5; ++i) {
        if(can_make(i)) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}

感想

まさかEまできて全探索を書かされるとは思わなかった．

2014 Yandex.Algorithm Elimination Stage, Round1 D - Splitting Money

問題文

http://codeforces.com/gym/100448

問題概要

n 個の数列が与えられる．
各要素について，集合Aとして使うか，集合Bとして使うか，あるいは使わないかを選択できる．
最終的に，集合Aとして使った数字のXORと，集合Bとして使った数字のXORが等しくなるようにしたい．
そのような集合AとBは何通りあるか．ただし，同じ数字であっても，元の数列で違う位置にあるものであれば，それらは区別するものとする．

・制約
1 <= n <= 10^4
1 <= a_i <= 10^4

解法

まず，数字の値が小さいことに注目する．

また，集合AのXORと集合BのXORが等しいとは，そもそもどちらかの集合に含めるとしたすべての要素のXORが0であることと同値である．
そのように数字を選んだ場合，各要素をどちらに振り分けても，それぞれのXORの値は等しくなる．

以上の2つから，以下の dp で計算することができる．
dp[i][j] := i 番目の要素まで見て，どちらかの集合として使う要素の XOR の値が j となるような値の振り分け方

ある数字を集合として使う時，どちらの集合に入れるかで2通りあるので，遷移は
dp[i + 1][j ^ a[i]] += dp[i][j] * 2
となる．

計算量は O(n * a_i) ．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> dp(1 << 14);
    dp[0] = 1;
    for(int i = 0; i < n; ++i) {
        auto nxt = dp;
        for(int j = 0; j < (int)dp.size(); ++j) {
            const int x = j ^ a[i];
            if(x < (int)nxt.size()) {
                (nxt[x] += (2 * dp[j]) % mod) %= mod;
            }
        }
        dp = move(nxt);
    }
    cout << dp[0] << endl;
}

2014 Yandex.Algorithm Elimination Stage, Round1 C - Non-Convex Quadrilaterals

問題文

http://codeforces.com/gym/100448

問題概要

n 個の整数が与えられる．それらから4つ選んで，四角形の4辺の長さとする．
もちろん選び方によっては四角形が作れないが，そういう選び方は出来ないものとする．
こうしてできる四角形のうち，凹四角形であるもののなかで，周の長さが最も大きいものの値はなにか？

・制約
1 <= n <= 10^4
1 <= a_i <= 10^8

解法

実際に四角形を書けばすぐわかるが，ほとんどの四角形はいい感じに変形すると，
おなじ4辺をもつ凹四角形に変形できる．
したがって，基本的に四角形が作れるならそれは凹四角形にできるから，数字の大きい方から4つ選んでいって，実際に四角形を構築できるか考えれば十分である．
四角形が構築できる条件は，4つの辺のうちの最大の長さが他の3辺の長さの和未満であることである．

コーナーケースが1つあり，それは正方形である．これはどう変形しても凹四角形にできない．

計算量はソートの分で O(nlogn)．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(rbegin(a), rend(a));
    int ans = -1;
    for(int i = 0; i + 3 < n; ++i) {
        if(a[i] == a[i + 1] && a[i] == a[i + 2] && a[i] == a[i + 3]) continue; // square
        int sum = 0;
        for(int j = i + 1; j <= i + 3; ++j) {
            sum += a[j];
        }
        if(sum > a[i]) {
            ans = a[i] + sum;
            break;
        }
    }
    cout << ans << endl;
}

2014 Yandex.Algorithm Elimination Stage, Round1 B - Adjusting Ducks

問題文

http://codeforces.com/gym/100448

問題概要

n 要素からなる数列が与えられる．また，ある要素の値を任意の数に変えることができる．その時，もとの値と変えた後の値をそれぞれ a, b として |a - b| のコストがかかる．この操作は何回でも行える．
この操作によって，数列に含まれる値として，単独で存在するものがないようにしたい．最小のコストはいくらかかかるか？

・制約
1 <= n <= 10^5
1 <= a_i <= 10^8

解法

基本的には値の近い2つの数字をペアにしていけば良さそうである．
よって，最初にソートして以下の dp をした．

dp[i][j] := i 番目の要素まで見て，その要素が直前の要素に変えられたか，あるいは直前の値を今見ている値に変えたかとしたときの最小コスト．

今見ている要素に直前の値を合わせる時，そのさらに前の（つまり2個前）要素は，今見ている要素に合わせるのは明らかに不利である．なぜなら，その場合は直前の要素に今の値を合わせたほうがコストが小さく済むからである．
したがって，この場合は2つ前の要素は，今見ている要素とは無関係に考えてよい．

次に，今見ている要素を直前の値に合わせるときは，同じような理由で2つ前の値は直前の値に変えられていると考えて良い．
この遷移のやり方だと，今見ている値を直前の値に合わせて，かつ2つ前の値をその前の値に合わせるようなものを考えていないようだが，実は問題ない．なぜなら，これは直前の値を今見ている値に合わせたのと同じだからであり，これは先程の遷移に含まれているからである．

以上で O(N) でこの問題をとくことができる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <typename T> constexpr T inf;
template <> constexpr ll inf<ll> = 1e18;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(begin(a), end(a));
    vector<vector<ll>> dp(n + 1, vector<ll>(2, inf<ll>));
    dp[1][0] = dp[1][1] = abs(a[0] - a[1]);
    for(int i = 2; i < n; ++i) {
        dp[i][0] = dp[i - 1][1] + a[i] - a[i - 1];
        dp[i][1] = min(dp[i - 2][1], dp[i - 2][0]) + a[i] - a[i - 1];
    }
    cout << min(dp[n - 1][0], dp[n - 1][1]) << endl;
}

感想

変な dp をしてしまったが，もっとわかりやすいのがありそう．うーん．

C++11で始めるマルチスレッドプログラミング その2 std::mutex 編

はじめに

本記事は
C++11で始めるマルチスレッドプログラミングその1 ～std::thread事始め～ - すいバカ日誌
の続きとなる記事です（何年越しだよ）．
今回は std:;mutex による基本的な排他制御について書きます．
本記事を書いた時点では C++17 がもう策定されていますが，タイトルはC++11のまま行きます．

排他制御について

異なるスレッドが同じリソースを共有するような場面は当然発生します．
しかし，異なるスレッドが共有リソースに対して同時にアクセス（すくなくとも1つは変更操作）をした場合，データ競合 (data races) が発生し，未定義動作となってしまうことがあります．ちなみに，data races は C++ の規格としてその定義が書かれているので参照してください．*1

データ競合が問題になる例として，双方向 linked-list (以下単に list と書く) を考えてみましょう．
list に対して erase 操作を行った場合，3つの要素（それ自身，直前，直後）のポインタをすげ替える必要があり，これらは命令として一度に実行することは出来ません．
したがって，それぞれの処理の間には，他のスレッドが入り込む余地があり，ここで問題が発生します．例えば直前の要素の next ポインタのみを挿げ替え終わっている時点で，他スレッドが直後の prev ポインタを参照する，ようなことは容易に想像できます．

このように，処理の途中段階では，データ構造の不変条件 (invariants) が崩れていることが多く，そのような状態でのデータ構造への操作は危険な操作となります．

したがって，共有リソースはデータ競合を防ぐための何らかの保護機能を用いなければなりません．
それには Lock-free なデータ構造や transactional なデータ構造を用いるという方法もありますが，今回扱うのは std::mutex (mutual exclusive) による排他制御です．
排他制御は，共有リソースに対しての同時（書き込み）アクセスが，ただ1つのスレッドしか許さないようにすることを言います．

std::mutex による排他制御

まずはサンプルコードから．

#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <string>

std::mutex stdout_m; // std::cout の排他制御
template <typename T>
void threadsafe_print(T v) {
    std::lock_guard<std::mutex> lock(stdout_m);
    std::cout << v << std::endl;
}

class widget {
public:
    void heavy_process(int i) {
        std::lock_guard<std::mutex> lock(m);
        threadsafe_print("called heavy_process with: " + std::to_string(i));
        std::this_thread::sleep_for(std::chrono::seconds(1));
        v.push_back(i);
    }

    void print() {
        std::lock_guard<std::mutex> lock(m);
        threadsafe_print("called print");
        for(auto x : v) {
            threadsafe_print(x);
        }
    }

private:
    std::vector<int> v;
    std::mutex m;
};

int main() {
    widget w;
    std::thread t1([&] {
        for(int i = 1; i <= 10; ++i) {
            w.heavy_process(i);
        }
    });
    std::thread t2([&] {
        for(int i = 11; i <= 20; ++i) {
            w.heavy_process(i);
        }
    });

    t1.join();
    t2.join();

    w.print();
}

このコードをもとに説明していきます．

stdout_m, widget::m, std::lock_guard

これらが今回の主役の std::mutex です．mutex を用いた排他制御では，アクセスの試み -> mutex を lock -> データに対する処理 -> 終了 -> mutex の unlock という流れになります．
lock, unlock は mutex から直接呼ぶことも出来ますが，RAIIを利用して書くのが安全です．std::lock_guard がそれに該当します（コンストラクタで lock，デストラクタで unlockする）．
stdout_m で std::cout を排他制御しないと，出力が混ざって見にくいのでそうしています．
widget::m については，各 widget オブジェクトごとに別となります．
mutex が lock されている間は，他のスレッドはその mutex を lock できません．
この場合，unlock されるまで待つことになります．これによって排他制御が実現します．

heavy_process, print

heavy 内部で std::vector にデータを追加します．これは他スレッドが同時に行うと問題なので，排他制御が必要です．
print 内部で v を参照していますが，ループの途中で heavy_process が呼ばれると v の状態が変わってしまうので排他制御が必要になります(途中でイテレータが無効になるかもしれない）．

std::this_thread::sleep_for

指定した時間だけ今のスレッドを sleep します．テストに便利なので今後もよく使うと思います．

以上でサンプルコードの解説は終わります．
試しに lock_guard を消してみると，たまに異常終了するのが観察できるので，いろいろ試して遊んでください．

スレッドセーフ性*2とデータ構造のインターフェース

マルチスレッド下での共有されるデータ構造の設計をすることになったとしましょう．
このとき，そのデータ構造のインターフェースは，注意深く設計する必要があります．
その点について確認するため，簡単なスレッドセーフなキュー safe_queue を実装してみましょう．

std::queue

よくある queue のインターフェースの一部を抜粋・簡略化して示します．

template <typename T, typename Sequence = std::deque<T>>
class queue {
public:
    explicit queue();
    explicit queue(Sequence const& s);
    
    bool empty() const;
    size_t size() const;
    T& front();
    T const& front() const;
    void push(T const&);
    void push(T&&);
    void pop();
};

front と pop が完全に分割されています（pop で先頭要素を return しない）が，これは Exceptional C++ などでも触れられているとおり，例外安全性を保つために必要な分割です．

この設計を何も考えずそのまま safe_queue に流用して良いでしょうか？
答えは No となります．

なぜだめなのか？

例えば以下のプログラムを，スレッドAとBが safe_queue に対して処理を行うことを考えます．

safe_queue<int> que;
if(!que.empty()) {
    auto value = que.front();
    que.pop();
    // ...
}

このとき，たとえは以下のようなフローが考えられます(empty, front, pop はそれぞれ std::mutex により排他制御されていると仮定します）．

(thread A) que.empty() の評価
(thread B) que.empty() の評価
(thread A) auto value = que.front();
(thread B) auto value = que.front();
(thread A) que.pop();
(thread B) que.pop(); // ???

thread B からの que.pop() は，予期した動作ではなさそうです．
というのも，thread A, B ともに見ている値は同じ que の先頭要素なのに対し，B が pop する値はまだ見ていない2番めの要素だからです．

このように，それぞれの関数内で std::mutex を lock したからといって，スレッドセーフなデータ構造が作れるという単純な話ではないのです．

解決策

std::mutex での排他制御を目指す場合，front と pop が分離されていると先に述べた問題が発生してしまうので，分離しないという選択を取ります．
ただし，例外安全性は保証したいので，多少コストを書けてどちらも実現する方法を考えます．例えば以下のようなものがあります．

• 引数の参照に対して pop が先頭要素を返す．デメリットは，呼び出し側で格納用の変数を宣言する必要があること．格納用の変数が作れないこともある（初期化に何らかの有効かつ意味あるデータが必要・初期化コストが無視できない）．
• 戻り値に pop されたデータを指すポインタを返す．ポインタのコピーには例外が発生しないことを利用．デメリットは，内部で何らかの形でポインタの管理が挟まるので，ゼロコストとは言えないこと．

今回はこの案を採用し，また front() は提供しないことにします．

safe_queue の実装例

class empty_queue : std::exception {
public:
    const char* what() const throw() {
        return "Empty queue";
    }
};

template <typename T>
class safe_queue {
public:
    safe_queue() {}
    safe_queue(safe_queue const& other) {
        std::lock_guard<std::mutex> lock(other.m);
        que = other.que;
    }
    safe_queue& operator=(safe_queue const&) = delete;

    void push(T value) {
        std::lock_guard<std::mutex> lock(m);
        que.push(value);
    }

    void pop(T& res) {
        std::lock_guard<std::mutex> lock(m);
        if(que.empty()) throw empty_queue();
        res = que.front();
        que.pop();
    }
    std::shared_ptr<T> pop() {
        std::lock_guard<std::mutex> lock(m);
        if(que.empty()) throw empty_queue();
        auto const res = std::make_shared<T>(que.front());
        que.pop();
        return res;
    }

    bool empty() const {
        std::lock_guard<std::mutex> lock(m);
        return que.empty();
    }

    size_t size() const {
        std::lock_guard<std::mutex> lock(m);
        return que.size();
    }

private:
    std::queue<T> que;
    mutable std::mutex m;
};

int main() {
    safe_queue<int> sq;
    for(int i = 0; i < 1000; ++i) {
        sq.push(i);
    }

    std::thread t1([&] {
        while(!sq.empty()) {
            auto value = sq.pop();
            threadsafe_print("[thread A] poped: " + std::to_string(*value));
        }
    });
    std::thread t2([&] {
        while(!sq.empty()) {
            auto value = sq.pop();
            threadsafe_print("[thread B] poped: " + std::to_string(*value));
        }
    });

    t1.join();
    t2.join();
}

まとめ

今回は std::mutex による排他制御の基本だけを扱いました．
ミューテックス自体の実装の話は
C++ミューテックス・コレクション -みゅーこれ- 実装編 - yohhoyの日記（別館）
がわかりやすかったです．

もしかすると次回に続くかもしれません（本当か？）．

*1:N4727 §6.8.2.1 Data races

*2:C++とスレッドセーフ性については yohhoy さんの記事スレッドセーフという幻想と現実 - yohhoyの日記（別館）が参考になります