ABC282-D : Make Bipartite 2 解説

ABCのD問題が久しぶりに解けなかったので解説しながら理解を深めます．

atcoder.jp

問題概要

  • 単純無向グラフG(V, E)が与えられます．u < vを満たす頂点(u, v)の組で次の2つを満たす組の総数を出力してください．

    • 頂点uと頂点vを結ぶ辺は存在しない．
    • Gに辺(u, v)を追加したとき，Gは二部グラフである．

  • 制約 : 1 ≦ |V| ≦ 2 × 105, 0 ≦ |E| ≦ min(2 × 105, |V| × (|V| - 1)/2)

考察ステップ

  • 制約からO(|V|^2)が通らないので全探索は当然×
  • そもそも入力グラフが二部グラフでなければ辺追加しても二部グラフではないため，0になりそう
  • 解の候補全体から辺を追加した時に制約を満たさない組を引いた方が良さそう

コード

Submission #37363361 - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

こうなりました

やること

  1. グラフを連結成分ごとに分割する
  2. それぞれの分割したグラフについて，二部グラフとなるように2彩色する
  3. 解候補全体からそれぞれの分割したグラフの同じ色の頂点からなる組合せの数を引いたものが答え

1. グラフを連結成分ごとに分割する

  • UnionFindを使うと便利です．
    • 特にAtCoder Libraryを用いるとgroupsという関数が用意されていて，各連結成分に含まれる頂点まで教えてくれるので良いです．
  • 提出コードでは，得られた連結成分の情報から実際にグラフを分割しています．サイズが連結成分の数の連結グラフの配列にしてます．

2. 2採色する

  • 幅優先探索を用いて1つの頂点の色を決め打って色を塗ります．
    • この時，同じ色の頂点同士は辺を持ってはならないです．
    • どうしてもそのような頂点が生まれる場合，そのグラフは二部グラフではありませんので，0を出力して終了します．
    • 詳しくは二部グラフの判定について学ぶと良いと思います．
  • 同じ色の頂点を1つのグループとすると，二部グラフになります．

3. 答えを求める

  • ある二部グラフにおいて，1つの辺を追加して二部グラフとなる条件は，違う色の2つの頂点を結んだ場合です．
  • 上の例では，辺(1, 4)や辺(1,5) は追加できますが，辺(1, 2)は追加できません．
  • そのような数を考えると，1つの二部グラフが与えられた時のこの問題は，頂点数をN，辺の数をM，それぞれの色で塗られた頂点の数をS, Tとすると，次のようになります．

  • それでは2つ以上の二部グラフからなって，双方から1つの頂点を選び辺を作る場合はどのようになるでしょうか．
  • 実はどのような選び方でも問題なく二部グラフとなります．

  • このことから，答えは頂点数をN，辺の数をM，連結成分の数をW, Gの連結な部分グラフG_iにおいてそれぞれの色で塗られた頂点の数をS_i, T_iとすると，次のようになります．

たのしく木グラフ : 競プロ典型 90 問 003 - Longest Circular Road（★4）

問題

atcoder.jp

読み替え

グラフを扱う問題です．

N個の頂点とN-1本の辺が与えられます．これで作られるグラフは連結*1です．

ある頂点uと頂点vの間に辺を1本張ることを考える時，サイクル*2ができる場合があります．このとき．サイクルの長さの最大値を求めてください．

解説

頂点がN個で辺がN-1本の連結グラフを考えると，そのグラフにサイクルが含まれることはありません．これは数学的帰納法で示すことができます．このグラフは木というグラフクラスに含まれます．木の特徴は次のとおりです．

  • ある頂点uからある頂点vまでの経路を考える時，それを満たす経路は1つしか存在しない．
  • ある頂点uとある頂点vの間に辺を張ることを考えると，サイクルができる．そのサイクルの長さはuからvへの経路の長さ+1である．

これを利用して問題を解きます．

ある頂点から最も経路の長さが長い頂点とその長さを求めるのはBFSを利用することでO(N)できます．BFSは幅優先探索で与えられた頂点と隣接する(辺を持つ))頂点を連続的に見ることで条件を満たす頂点*3を探す手法です．

図を用いて説明します．

f:id:dokaraya:20220208151150p:plain

上の図では始点として赤の頂点を考えます．それを距離0の頂点とし，隣接する頂点を見ていきます．今回の場合だと左上の頂点と真ん中の頂点が対象です．これらについて距離1の頂点とします．同様に距離1の頂点と隣接する頂点それぞれについて距離2の頂点とします．ただし，既に始点からの距離がわかっている頂点については更新しないこととします．これを全ての頂点について始点からの距離がわかる状態になるまで繰り返します．

最後に最も始点からの距離が長い頂点の1つを選び，返します．

BFSを全ての始点について行うことで解を得ることを考えたいのですが，O(N2)となり，制約としてN<100000であるため，N=100000の場合などには2秒以内に計算を終えることができません．

しかし次のようにBFSを2回だけ行うことで解を得ることができます．

  • ある頂点vを選びBFSを用いてvを始点とする最も距離の長い頂点sを得る．
  • BFSを用いて頂点sを始点とする最も距離の長い頂点tを得て，その距離+1を出力する

これは木の直径を求めるアルゴリズムで，木の最も距離の長い頂点の組と距離を得ることができるアルゴリズムとして知られています．これはN=100000の場合でも問題なく2秒以内に動作させることができます．最も距離が得られたため，サイクルの長さはその距離+1となります．

BFSの実装については先駆者が多くいますのでそちらを参考にしてください．

ソースコード例(C++)

*1:任意の2点間に必ず経路が存在する

*2:同じ頂点・同じ辺を通らないような経路を考える時に始点と終点が同じもの．JR山手線みたいな感じです．

*3:今回だと与えられた頂点から最も遠い頂点

たのしく累積和 : 競プロ典型 90 問 010 - Score Sum Queries（★2）

問題

atcoder.jp

学生がN人います．各学生の所属するクラス(1 or 2)と試験の成績が与えられます．

校長先生からQ回，次の質問がくるのでうまく答えたいです．

校長先生「L番目からR番目の学生の期末試験の点数の合計をクラス別で教えてくれ」

解説

制約を見ると質問は最大で100000回来るようです．そこで想定される最悪ケースの質問「全員の学生の期末試験の点数の合計をクラス別で教えてくれ」の計算量を考えます．

愚直に実装すると，1度の質問でO(N)かかります．学生は最大100000人いるみたいなので，100000 × 100000 > 1012 となり，コンピュータでは太刀打ちできません．高速化が必要です．

期末試験の点数の合計を高速に求められるととても嬉しいです．そこで，次の2つの配列を質問に答える前にあらかじめ用意しておきます．．

  • cl[1][i] : 学籍番号i番目までの1クラスに所属する成績の総和
  • cl[2][i] : 学籍番号i番目までの2クラスに所属する成績の総和

これを用いることで，高速にLからRまでの成績の総和を求めることができます．具体的には1クラスの場合，cl[1][R] - cl[1][L-1]で求めることができます(当然配列外参照などは気にする必要があります)．

これは累積和というテクニックです．これを用いることで1度の質問をO(1)で答えることができます．

累積和は色々なところで使うので，慣れる必要があります．

ソースコード例(C++)

たのしく前処理 : 競プロ典型 90 問 004 - Cross Sum（★2）

問題

atcoder.jp

解説

H × Wの数字がはいったマスが与えられるので，それぞれのマスについてマスと列が等しいか行が等しい全てのマスの数字の総和を出力する問題です．

f:id:dokaraya:20211031123700p:plain (実際には数字が各マスに入っています)

例えば赤のマスについて調べたいとき，赤のマスに書かれている数字と青のマスに書かれている数字の総和を出力します．

単純に計算すると，1度の計算でH+W回の操作が必要になり，全体でHW(H+W)回になります．

今回の入力では列の数と行の数の最大値が2000なため，単純な実装では現代のコンピュータでは2秒以内に計算できません．

そのため何らかの工夫が必要になります．

ここで次の場合を考えてみます．

f:id:dokaraya:20211031124814p:plain

左を計算すると，2 + 5 + 6 + 7 + 8 + 10 + 14です．

右を計算すると，3 + 5 + 6 + 7 + 8 + 11 + 15です．

両方に5 + 6 + 7 + 8 が入っていることがわかります．これは行が同じため，計算する必要のある場所がかぶっているためです．

また，これは列が同じときにも使うことができます．

この性質を利用して，予め各列についての総和，各行についての総和を求めることで計算を効率的に行えます．

i行j列のマスについて操作を行うとすると，i行目の総和 + j列目の総和 - i行j列の値 とすることで計算できます．

このように先に入力に対し何らかの処理を行うことを前処理といいます．

簡単な動作例

f:id:dokaraya:20211031125359p:plain

それぞれの行と列について総和を求めます．

f:id:dokaraya:20211031125810p:plain

答えは次のようになります．

f:id:dokaraya:20211031130332p:plain

ソースコード例(C++)

たのしくbit全探索: 競プロ典型 90 問 002 - Encyclopedia of Parentheses（★3）

問題

atcoder.jp

解説

正整数Nが与えられるので，長さがNの正しく整合している括弧列をすべて出力する問題です．

ここでの整合とは左括弧と右括弧が正しく対応していることです．

OK ( ( ) ( ) ) , ( ( ) ( ( ) ( ) ) ) ( ),
NG ( ( ), ( ) ), ) ( ( ) ),

最も高速なアルゴリズムを設計するのはなかなか難しそうですが，今回の問題はNの最大値が20であるため，全探索ができそうです*1．

今回は左括弧と右括弧の2通りと見ることができるため，bit全探索が使えます．

bit全探索は0と1からなる要素数がNの配列を全列挙することで組合せをすべて作る手法です．入力の要素数が少ないときに有効です．

要素3の例 [ 000 ⇒ 001 ⇒ 010 ⇒ 011 ⇒ 100 ⇒ 101 ⇒ 110 ⇒ 111 ]

今回長さNの文字列を作るため，全探索の数としては2Nになります．0から2N - 1までの全通りを2進数表記にすることでN文字のそれぞれの括弧を左括弧にするか右括弧にするか決定します．

0なら左括弧，1なら右括弧と見立てて，生成された組合せが正しく整合しているか確認します．

確かめるために用いる変数vを0で初期化します．bit列を前から見ていき，0なら+1，1なら-1します．

次のいずれかに当てはまる場合，そのbit列は正しく整合していないです．

  1. ループの途中で変数vが負になる．
  2. ループが終了したときに，v = 0ではない．

これに当てはまらなかったbit列を括弧に直して出力します．

簡単な動作例

N = 4

組合せの数は24 = 16

  • [0 ⇒ 0000] ⇒ 2.に当てはまるため正しくないです．
  • [1 ⇒ 0001] ⇒ 2.に当てはまるため正しくないです．
  • [2 ⇒ 0010] ⇒ 2.に当てはまるため正しくないです．
  • [3 ⇒ 0011] ⇒ 正しいです．　　　　　　　　　　　 ⇒ ( ( ) )
  • [4 ⇒ 0100] ⇒ 2.に当てはまるため正しくないです．
  • [5 ⇒ 0101] ⇒ 正しいです．　　　　　　　　　　　 ⇒ ( ) ( )
  • [6 ⇒ 0110] ⇒ 1.に当てはまるため正しくないです．
  • [7 ⇒ 0111] ⇒ 1.に当てはまるため正しくないです．
  • [8 ⇒ 1000] ⇒ 1.に当てはまるため正しくないです．
  • [9 ⇒ 1001] ⇒ 1.に当てはまるため正しくないです．
  • [10 ⇒ 1010] ⇒ 1.に当てはまるため正しくないです．
  • [11 ⇒ 1011] ⇒ 1.に当てはまるため正しくないです．
  • [12 ⇒ 1100] ⇒ 1.に当てはまるため正しくないです．
  • [13 ⇒ 1101] ⇒ 1.に当てはまるため正しくないです．
  • [14 ⇒ 1110] ⇒ 1.に当てはまるため正しくないです．
  • [15 ⇒ 1111] ⇒ 1.に当てはまるため正しくないです．

ソースコード例(C++)

*1:220 = 1048576で，判定がO(N)であれば十分現代のコンピュータで2秒以内に計算できそうと予想できます．現代のコンピュータは1秒でおおよそ1億ステップ計算できると考えて良いです

たのしく二分探索: 競プロ典型 90 問 001 - Yokan Party（★4）

問題

atcoder.jp

解説

L cmのようかんをK+1個に分割するとき，分割したようかんの大きさの最小値をできるだけ大きくする問題です．

f:id:dokaraya:20211024011145p:plain
図1. ようかんの例(ようかんには見えませんが)

最小値の最大値が求められるような場合，二分探索が有効です．

二分探索を簡単にイメージするためには，次の例を考えることが効果的です(ご存じの場合読み飛ばすことを推奨します)．

  • 人の年齢をの最小回数の質問で正確に当てたい．
    • 簡単にするために質問者Aは対象者Bの年齢が20歳以上68歳未満であるとわかっていることにします．
    • 今回の例では対象者Bの年齢を34歳とします．
    • 次のように当てます．
      • A「Bさんの年齢は44歳以上ですか？」( (20 + 68)/ 2)
      • B「いいえ」(ここでBさんの年齢は20歳以上44歳未満であることが確定します)
      • A「Bさんの年齢は32歳以上ですか？」( (20 + 44)/ 2)
      • B「はい」(ここでBさんの年齢は32歳以上44歳未満であることが確定します)
      • A「Bさんの年齢は38歳以上ですか？」( (32+ 44)/ 2)
      • B「いいえ」(ここでBさんの年齢は32歳以上38歳未満であることが確定します)
      • A「Bさんの年齢は35歳以上ですか？」( (32+ 38)/ 2)
      • B「いいえ」(ここでBさんの年齢は32歳以上35歳未満であることが確定します)
      • A「Bさんの年齢は33歳以上ですか？」( (32+ 35)/ 2 (小数点切り捨て))
      • B「はい」(ここでBさんの年齢は33歳以上35歳未満であることが確定します)
      • A「Bさんの年齢は34歳以上ですか？」( (33+ 35)/ 2)
      • B「はい」(ここでBさんの年齢は34歳以上35歳未満であることが確定して，それは一意に定まるため，34歳であることが確定します)

この例では20歳以上68歳未満の48通りを半分ずつ削ることで，効率的に探索します．これが二分探索です．

半分ずつ削るため，探索空間をNとすると O(logN)です．

ようかんの問題では，スコアの最小値を0，スコアの最大値をL*1と考えて，次の判定問題を考えます．

  • ようかんが目標スコアより小さくならないように切っていき，K+1個に分割可能か？

分割可能かは貪欲法を用いることで判定可能です．片端から目標スコア以上になるように切れる部分を狙って切ることを繰り返すことで十分です．

二分探索の実装では，スコアの最小値を表す変数leftと，スコアの最大値+1を表す変数rightを用いるのが便利です．

目標スコア(範囲の中間点)は(left + right) / 2で求めることができ，それが達成できればright = (left + right) / 2に，達成できなければleft = (left + right) / 2とします．範囲が一意に定まるまでループさせます．

right - left = 1のとき，範囲が一意に定まったとして，leftが求める値になります．そのため，while(right - left > 1) を用いましょう．

計算量は二分探索でlog(L)，各ステップの判定でN*2となるため，全体としてO(N log(L) )です．十分高速です．

簡単な動作例

図1の例を用います．K = 2とします．そのため，3分割することが目標です．

f:id:dokaraya:20211024011145p:plain
図1. ようかんの例(ようかんには見えませんが)

  1. [left = 0, right = 24] ⇒ mid = 12で，3分割できないため，right = midとする．
  2. [left = 0, right = 12] ⇒ mid = 6で，3分割できるため，left = midとする(11の切れ目と18の切れ目で達成できます)．
  3. [left = 6, right = 12] ⇒ mid = 9で，3分割できないため，right = midとする．
  4. [left = 6, right = 9] ⇒ mid = 7で，3分割できないため，right = midとする．
  5. [left = 6, right = 7] ⇒ right - left = 1であるため，答えとしてleft = 6を出力する．

    ソースコード例(C++)

知的文章を書く能力が欲しいです

*1:入力のようかんの長さ，当然切ってようかんの長さが伸びることはない

*2:切れ目の個数，貪欲法による判定で切れ目すべてを1度ずつ見る必要があります．

競プロ典型90問の解説を書きたいと思います．

学習モチベを保つために競プロ典型90問の解説を書きます．

解いたら順次書く感じでやりたいとおもいます． atcoder.jp

リスト