NSTomoS’s blog

NSTomoSの情報系の記録用ブログです.

c++で競プロ入門(3)

今回はABC040のD問題を解いていきます.

D問題 道路の老朽化対策について

abc040.contest.atcoder.jp

部分点とは

難しい問題には部分点が与えられる場合があります.
問題の制約条件よりもゆるい制約条件が与えられ,その条件下で成果した場合点数の一部が得られます.
部分点の解法は元の問題の解法(満点解法)よりも簡単なので,満点解法が思いつかない場合はあきらめて部分点解法を取りに行くのも戦略です.
(実際に,満点解法を思いつけると思って挑んだものの解けず,「最初から部分点解法を解いておけば順位が上がったのに…」なんてことも多々あります.)

今回のD問題の場合,問題の制約は1≦N≦100,000 0≦M≦200,000 1≦Q≦100,000,ですが,1≦N≦1,000 0≦M≦2,000 1≦Q≦1,000,の制約のテストケースを全てACできれば部分点が与えられます.
今回はまず部分点解法で解いていきます.

キュー

後述する幅優先探索ではキューというデータ構造が必要になります.
キューは待ち行列のことで,データを行列の最後に追加(push)して先頭から取り出すこと(front,pop)がそれぞれ{O(1)}でできるデータ構造です.

c++ではqueueというコンテナで実装されており,push()で最後にデータを追加,front()で先頭のデータを参照,pop()で先頭のデータを削除できます.

幅優先探索

今回の問題は都市とその間の道路についての問題です.
このような問題は都市を頂点,道路を辺としたグラフの問題として解くことができます.

今回の問題ではグラフを探索する必要がありますが,その手法の一つに幅優先探索探索があります.
これはグラフを出発地点から均等に掘り下げていく手法です.

アルゴリズムは前述のキューを用います.

  1. 空のキューと頂点の探索済みか否かのチェックリストを用意する.
  2. スタート地点の頂点をキューに追加する.
  3. キューが空でない間以下の操作を行う
  4. キューから頂点を取り出す
  5. 取り出した頂点に接続している頂点が探索済みでないならば,探索済みにしてキューに追加する.

幅優先探索の時間計算量は,最悪の場合全ての頂点と全ての辺を参照するので{O(|V|+|E|)}となります.
({|V|}はグラフの頂点数,{|E|}はグラフの辺数)

ちなみに,これを最後に追加したものを最初に取り出すデータ構造のスタックを用いると深さ優先探索となります.
これはどんどん探索を掘り下げていって探索できなかったら最後に見た枝分かれまで戻ることを繰り返す探索手法です.

ペアpair

今回の実装で使うpairを解説しておきます.
これは二要素の構造体のようなもので,競技プログラミングではしばしば用います.
pairの生成にはmake_pairを使います.
一つ目の要素をfirst,二つ目の要素をsecondで参照できます.
要素としてpairを取って入れ子にすることも出来ます.
優先順位を宣言しなくても一つ目の要素の型の優先順位を用いてくれるため,非常に便利な場面が多いです.

部分点解法

部分点解法は愚直な解法を考えてみましょう.
各クエリで与えられる出発地点から出発して,各クエリで与えられる年よりも後に作られた道だけを使っていける都市の数を数えればいいことになります.

この都市の数え上げには幅優先探索を用います.
キューへの追加時に,クエリで与えられる年よりも後に作られている道のみをキューに追加します.
また,チェックリストで探索済みにした回数を数えることで,行くことが出来る都市の数を数えます.
(これは探索後にチェックリストを数えることでも可能です.)

ソースコードは以下のようになります

gist7e35a0648f1e6551578a1f84d64189fa

edgeは都市iから伸びるj番目の道路が都市edge[i][j].firstにつながっており,edge[i][j].second年に造られたことを示します.

これで部分点50点が得られました.

しかし,この実装は{O(Q\times (N+M))}なので,問題の制約条件下ではTLEとなります.

満点解法の方針

満点解法は方針を変えなければ解けません.

道路とクエリをそれぞれ造られた年({y_j})と使用する条件の年({w_j})の新しいものから考えると,道路によって最初はばらばらだった町を繋げていきながら,クエリを処理できそうだと気づきます.
(注:これは実際の道路の作成ではなく,使用可能な道が増えていくということです.)

従って,道路とクエリをそれぞれ年で管理して,年を最大値から減らしながら,その年に造られた道があったら都市を繋げて(同じ集合とみなし),その年が閾値のクエリがあったら出発地点が含まれる集合の要素数をクエリの番号で記録する作業を繰り返す方針で考えます.

ここでバラバラの都市を集合にまとめながらその集合内の個数を求めることが出来るデータ構造が(それもある程度の速度で)必要であることが分かります.

UnionFind

そこでUnionFind(素集合データ構造)を使います.
UnionFindは集合を管理するデータ構造で

  • 任意の二要素が属する集合を一つの集合に結合する
  • 任意の二要素が同一集合か否かを判定する.

の二つの操作を行うことが出来ます.

データ構造は木を用いて実現され,1つの木が一つの集合に対応し,木を連結させることで集合の結合を行い,二要素の根を探してそれが一致するかで判定を行います.

木を用いるために偏りが出て実行速度が落ちるのを防ぐために,

  • 経路圧縮:再帰的に根を調べるときに,要素を根につなぎ直す.
  • ランク:木の高さ(ランク)を管理し,ランクの低い木をランクの高い木に繋げる

の二手法が提案されていて,二つを組み合わせた実装も可能です.

今回は要素を配列で管理し,配列の値として親要素の番号を持つ方法で,経路圧縮のみを用いて実装します.
また,今回は集合の要素数が必要となるため,根要素の配列値として要素数を負にした値を持たせます.
実装すると以下のようになります.

gistfd9388e6ef2cee3ad7ca6a8ad1f6cdfa

unionc言語由来の予約語に存在するため,結合操作の関数名はuniteにしています.

操作の計算量は{O\log(N)}です.
(根を再帰的に参照するroot関数がならし計算のために{O\log(N)}かかるため)

クラス

UnionFindの実装でクラスを用いたので軽く解説します.
クラスとはc言語的に言うと「関数を持つ構造体」のようなものです.
構造体の変数と同様に.で繋げて構造体の関数を呼び出すことが出来ます.
クラス内の変数,関数をメンバ変数,メンバ関数と言います.
実はここまで用いてきたSTLのコンテナなども全てクラスです.

返り値を持たない,クラス名と同名のメンバ関数コンストラクターと呼びます.
これは,クラスを実体化する(オブジェクトを生成する)際に呼び出される初期化用の関数です.
コンストラクターは引数の後に:で区切ってメンバ関数を引数で初期化できます.

また,クラスで宣言される変数関数はそのままではクラス内では参照できません.
クラス外から参照する必要のあるものはpublic:より下に記述します.

クラスを用いたオブジェクト指向は他にもクラスの継承などの重要な概念があるのですが,競技プログラミングではあまり利用しません.

満点解法

以上のことをまとめて実装すると以下のようになります.

gist8c2873fe00e45b3224e1eb207b805d15

edgeは各道路の繋げる都市を造った年ごとに格納したもので,
queryは各クエリの出発都市とクエリ番号を閾値の年ごとに格納したもので, ansは要素番号に対応したクエリの答えを格納します.

ちなみに,この実装は年を最大値から1ずつ減らすようにしていますが,edgequeryを造った年と閾値の年でソートした配列にして,マージのような作業を行うことで答えを出す実装も可能です.
もしも{y_i,w_i}の最大値が非常に大きい場合などはこちらで実装すべきでしょう.

まとめ

これでABC040の4問全てで満点を取ることが出来ました.

様々なアルゴリズムに触れることが出来る競技プログラミングの世界にぜひお越しください.