2019-09-02

AtCoder Beginner Contest 139 E: League 解説の解説

方針は2つあり，貪欲法とトポロジカルソートを利用するものがある．

貪欲法

問題より，各人には次に対戦すべき相手リストLが与えられる． Aさんの次に対戦すべき人がBさんだったとする．Bさんの次に対戦すべき人がAさんだった場合，試合を行う(この状態を相思相愛と呼ぶ)．二人の対戦リストLの先頭を削除する．

このような組み合わせの2人が存在しなかった場合，条件を満たす試合の組み合わせは存在しない．このことは以下のようにして示せる．

例えばAさんの次に対戦すべき人がBさんであるが，Bさんが次に対戦すべき人はCさんだったとする． AさんとBさんが試合を行う前に，BさんはCさんと試合を行う必要があるが，そのCさんも別のDさんと先に試合を行う必要があるという風に，どんどん依存関係が続いてしまい，最終的に矛盾が生じる．

このような考え方をした場合，以下のような素朴な解き方ができる．

int day = 0;
while(全ての人のLが空でない){
    相思相愛な人同士の組み合わせを，可能な限り見つけ，試合を行う // (1)
    Lを更新する
    day++;
}

whileループは高々N*(N-1)/2しか回らないが，(1)を素直にやろうとすると0(N)かかってしまい，全体の計算量がO(N³)になってしまうが，これは以下のようにして高速化出来る

list ←試合を行えるリスト
listに，はじめから試合を出来る組み合わせを入れる

int day = 0;
while(listが空でない){
    listの中にある組み合わせの試合を全て行う // (2)
    Lを更新する
    (2)で試合を行った人で，次に試合が出来る組み合わせをlistに追加
    day++;
}

実装はsnukeさんの解説放送のコードが非常にわかりやすい

https://atcoder.jp/contests/abc139/submissions/7296454

トポロジカルソート

全ての試合は，N人のうちの2人の組み合わせでユニークに番号をつけることができる．ある人Aの対戦リストLについて，試合(A,L[j])は試合(A,L[i])より後に行わなければならないという依存関係がある(i < j)．

すべての試合をノードとし，依存関係を有向辺で示したグラフGを構築する．グラフGがDAGでない場合，依存関係を解消できないので条件を満たす試合の組み合わせは存在しない．同じ人が出る試合の集合は依存関係が有るため，依存関係にない試合は同日に行える．よって答えはGの最長経路である．

2019-07-21

ダイクストラ法の計算量

蟻本とかにあるpriority_queueを使ったダイクストラ法の計算量の見積もりがよくわかってなかったので，メモ．詳しい実装は蟻本を見てもらうとして，問題となるコードは大体以下の通り．

while(!que.empty()){
    P p = que.top(); que.pop(); // (1)
    int v = p.second;
    if(d[v] < p.first) cotinue; // (2)

    for(auto e : G[v]){ // (3)
        if(d[e.to] > d[v] + e.cost){
            d[e.to] = d[v] + e.cost; 
            que.push(P(d[e.to], e.to)); // (4)
        }
    }
}

まず，優先度付きキューには暫定コストと次の行き先のペアが格納されるが，これはアルゴリズム全体を考えると，このキューには高々E個の要素しか入らない．これはあるエッジは高々1回しか見ないことから言える．よってwhileループはE回しか回らない．

(1)の処理にかかる計算量は，優先度付きキューの要素がEのオーダーなので，logE．外側のwhileと合わせてO(ElogE)

(2)の処理を考えると，これは次の最短経路木に入れるノードを確定させる処理である．すなわち，これより下を通る処理はVしかない．

(3)の処理にかかる計算量は，全てのノードについて，そのノードから出る辺を足し合わせたものに等しい．エッジには端点が2個しかないことから，これも結局はO(E)で抑えられる

(4)の処理にかかる計算量は，ElogE

以上より，優先度付きキューを用いたダイクストラ法の計算量はO(ElogE) = O(ElogV)である．(E <= 2V(V-1))

2019-04-27

emplace_back

vectorのemplace_backが良さそうということに案外気付いたのでメモ

vector<pair<int,int>> a;

a.push_back(make_pair(1,2)); //これはok
a.push_back(1,2); //これは駄目

a.emplace_back(make_pair(1,2)); //これはok
a.emplace_back(1,2); //これもok!!

なんでこれが許されるかというと，emplace_backでは要素型のクラスが取りうるコンストラクタ引数の値を元に、要素をコンテナ内で直接構築して追加するという操作が行われているため

2019-03-02

STLの勉強　コンテナ

Effective STLのお勉強
第1章コンテナから

コンテナの選択について

コンテナライブラリは、キュー、リスト、スタックのような一般的なデータ構造をプログラマが簡単に実装することを可能とする汎用のクラステンプレートとアルゴリズムのコレクションです。(cppreference.comより)

シーケンスコンテナ(vector, string, deque, list)
シーケンシャルアクセスが可能なデータ構造
連想コンテナ(set, multiset, map, multimap)
高速に検索可能(O(logn))なソート済みのデータ構造
非順序連想コンテナ
ハッシュコンテナ

使い分けケース・バイ・ケース

コンテナの任意の位置に新しい要素を挿入する必要がある
→シーケンスコンテナが必要．連想コンテナは使用不可
どのカテゴリのイテレータが必要か
→ ランダムアクセスイテレータが必要ならvector, deque, string
挿入または消去が行われるとき，既存のコンテナ要素の移動を避ける必要がある → 連続メモリコンテナはやめとけ
Cと互換性を保ちたい → vectorを使っておけ

コンテナのオブジェクトのコピーについて

コンテナはオブジェクトを格納しているが，そのコンテナが格納しているのは指定したオブジェクトの「コピー」である．すなわち，コピーの負荷が大きいオブジェクトを追加する動作は，パフォーマンスに悪影響を及ぼす．また，オブジェクトの継承がある場合，基本クラスオブジェクトのコンテナに派生クラスオブジェクトを挿入すると，派生部分がなくなってしまう問題がある．

これらを解決する手段は，オブジェクトのコンテナの代わりに「ポインタ」のコンテナを生成することである．

単一要素メンバ関数より，範囲メンバ関数を使え

v1, v2という2つのベクトルがある．v1をv2の後ろ半分と同じ内容にする簡単な方法を考えよ

以下のような選択肢がある．

assign関数を使う

v1.assign(v2.begin() + v2.size() / 2, v2.end());

copy関数を使う

v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));

for文と代入で頑張る

v1.clear();
for(auto ci = v2.begin() + v2.size() / 2; ci != v2.end(); ci++)
    v1.push_back(*ci);

結論はassign関数使ったほうがいいよねっていう話．copyの内部もループがある． insert, erase, assignは覚えておこうね

進捗置き場

競プロの問題の解説など．大雑把な方針と自分のコードだけ載せてます