![問題概要
? “(“と”)”だけからなる対応の取れた括弧列 S 中の
文字を赤と青に塗り分ける
? i 文字目と j 文字目の括弧が対応しているとき、
S[i, j] に含まれる赤色の文字の数 R と青色の文字の
数 B について、|R – B| ≦ K を満たす
? 上記の制約を満たす色の塗り分け方は何通りあるか？](https://image.slidesharecdn.com/ddpc2016final-160325065612/85/Disco-Presents-2016-10-320.jpg)
![満点 (150点)
? 木の形が回転操作により変わりうる
– オイラーツアーではそのような状況に対応できない
? 与えられる木が二分探索木であることに着目する
– 各ノードに部分木の値の最小値 min と最大値 maxを持たせると
[min, max]が部分木を表す区間になる
– この区間が分かれば、先ほどと同様RMQを用いて解くことが可能](https://image.slidesharecdn.com/ddpc2016final-160325065612/85/Disco-Presents-2016-28-320.jpg)
![ノードの挿入操作
? 担当する区間は親が担当する区間より一意に定まる
? 挿入されたノードが担当する区間に 1 を加算
– (存在しないノードも親と同じ高さになるが関係ない)
v
[min, max]
l
[min, v - 1]
?
[v + 1, max]
v
[min, max]
l
[min, v - 1]
r
[v + 1, max]
+1](https://image.slidesharecdn.com/ddpc2016final-160325065612/85/Disco-Presents-2016-29-320.jpg)
![ノードの回転操作
? 担当する区間の変更として表せる
? 2 つの区間に+ 1と-1を加算
v
[min, max]
l
[min, v - 1]
r
[v + 1, max]
v
[l + 1, max]
l
[min, max]
r
[v + 1, max]
+1-1](https://image.slidesharecdn.com/ddpc2016final-160325065612/85/Disco-Presents-2016-30-320.jpg)
Disco Presents ディスカバリーチャンネルプログラミングコンテスト2016 本選 解説
- 1. ?AtCoder Inc. All rights reserved. 1 DISCO presents ディスカバリーチャンネル プログラ ミングコンテスト2016 本選 解説 AtCoder株式会社
- 3. 問題概要と解法 ? N 人が参加したコンテストの順位表をもとに それぞれの参加者が獲得した賞金を求めよ ? 順位表の情報に従って賞金を決定すればよい – 実際には賞金が存在するのは 5 位までなので、そこまで 見ればよい
- 5. 問題概要 ? 時間の経過とともに料理がなくなるビュッフェがある – 料理にはそれぞれ美味しさと取ることができる締切がある ? 単位時間あたり 1 つ料理を取ることができる ? 取った料理の美味しさの総和が X 以上となる 最小の時刻 t を求めよ
- 6. 考察 ? 美味しい料理から貪欲に取るのがよさそう – 締切を考慮しなくてはならないので難しい ? 時刻に関して逆に考える – 時刻の経過とともに料理が追加されるビュッフェになる – そのとき食べられる最も美味しい料理から取ればよい ? ある時刻 t から料理を取り始めるとき，取った料理の 美味しさの総和が X 以上となる最大の時刻 t を求めよ という問題になった
- 7. 想定解法 ? 時刻 t に関して二分探索+貪欲 – 優先度付きキューを用いることで料理の追加と削除、 最も美味しい料理の取得が効率よく可能 ? 計算量は O(N log2N)
- 8. 別解 ? 賢い貪欲法を行うことでより効率的に解ける ? 最も美味しい料理から貪欲に取っていく – その際できる限り締切に近い時刻に取ることにしておく – 時刻 0 でもその料理を取ることができない場合は諦める ? 今取っている他の料理と交換しても，得することは存在しない – 取った料理の美味しさの総和が X 以上になったとき， 取った料理の個数が答えとなる ? 締切に近い時刻に取ったことにしたのを前倒しにする ? 計算量は O(N logN) – 他にも様々な解法が存在します
- 10. 問題概要 ? “(“と”)”だけからなる対応の取れた括弧列 S 中の 文字を赤と青に塗り分ける ? i 文字目と j 文字目の括弧が対応しているとき、 S[i, j] に含まれる赤色の文字の数 R と青色の文字の 数 B について、|R – B| ≦ K を満たす ? 上記の制約を満たす色の塗り分け方は何通りあるか？
- 11. 考察 ? 対応の取れた括弧列は順序木と対応している – 正確にはこの問題においては順序木の集合になる ? 「(()(()))」は以下のような順序木に対応 2 3 1 4
- 12. 考察 ? 塗り分けるという操作は 1 つの頂点に赤い石か 青い石を合計 2 個になるように置くことに対応 2 3 1 4
- 13. 考察 ? 塗り分けるという操作は 1 つの頂点に赤い石か 青い石を合計 2 個になるように置くことに対応 ? 塗り分けに関する制約は各頂点を根とする部分木に 存在する赤い石の個数を R、青い石の個数を B として |R – B| ≦ K を満たすという制約になる 2 3 1 4
- 14. 問題 ? 根付き木の集合が与えられる ? 各木のそれぞれの頂点に赤い石と青い石を合計 2 個に なるように置く ? 各頂点を根とする部分木それぞれについて、部分木に 含まれる赤い石の個数を R、青い石の個数を B として |R – B| ≦ K を満たす石の置き方は何通りあるか？
- 15. 解法 ? 根付き木どうしの間に石の置き方の制約はない – 各根付き木についての答えを最後に掛けあわせればよい ? 各根付き木内で dp(i, r) = 頂点 i を根とする部分木に含まれる赤い石の個数が r であるような制約を満たす石の置き方の総数 としてDPを行う ? 各頂点において、r を部分木に含まれる頂点の 2 倍 まで見るように遷移を行うと頂点数を N として 計算量は O(N2)となる
- 16. D: ディスコ社内ツアーⅡ
- 17. 問題概要 ? N 頂点 M 本の有向辺からなる単純有向グラフが 与えられる ? 各辺にはOかEのラベルがついている ? ある頂点 s から出発して，以下の条件を満たすように 頂点 t に移動したい – Oのラベルがついた辺をそれぞれ奇数回通った – Eのラベルがついた辺をそれぞれ偶数回通った ? 始点 s と終点 t の組み合わせはいくつあるか？
- 18. 考察: 有向オイラー路 ? 具体的な辺を通る回数が与えられたときを考える ? これは有向オイラー路の判定問題に近い – 有向オイラー路とはグラフの辺をちょうど 1 度ずつ通る ような路(トレイル)のこと – k 回辺を通るのは，k 本辺があるとすればよい ? 有向オイラー路が存在する条件は – 無向基礎グラフが連結 – 各頂点の相対出次数が 0 、あるいは相対出次数が 1、– 1 の 頂点が 1 つずつ存在し、他の頂点の相対出次数が 0 ? 前者は有向オイラー閉路，後者は有向オイラー路
- 19. 考察: ? ラベルがOの辺が存在しないならば答えは N – 以後はラベルがOの辺が少なくとも 1 つあることを仮定 ? ラベルがOの辺はそれぞれ一度通ったことにする – 通る回数を 2 ずつ増加させることで，有向オイラー路が 存在するようにすることが可能か？という問題になる ? それぞれの頂点の相対出次数の偶奇が定まる – 全ての頂点の相対出次数が偶数 – 相対出次数が奇数であるような頂点が 2 つのみ存在 の 2 つの場合を以後は考える
- 20. 解法: 全ての頂点の相対出次数が偶数 ? 有向オイラー閉路が存在するように辺の通る回数を割当てが可能な条件は – ラベルがOの辺全てがある強連結成分内に含まれる であり、このときの答えはそのような強連結成分に含まれる頂点の数 – ある強連結成分に含まれる頂点 u, v を選び、「u の相対出次数に 2 加算し、 v の相対出次数に -2 加算する」という操作が可能である ? u から v への辺があるならばそのような操作が可能なことは自明 ? u から v へのパスを適当に選んで通る回数を 2 ずつ増加させることで上記の操作が 可能であることが示せる – この操作を適切に行うことで、全ての頂点の相対出次数を 0 にすることが可能 – 上記より、ラベルがOの辺全てがある強連結成分内に含まれているときは そのような閉路が存在することが示せた – ラベルがOの辺全てがある強連結成分内に含まれていないときは、 ラベルがOの辺全てを通って、元の出発点に戻ることができない
- 21. 解法: 相対出次数が奇数の頂点が 2 つ存在 ? 有向オイラー路が存在するように辺の通る回数を割当てが可能な条件は – 強連結成分分解により縮約されたグラフにおいて、以下のようなパスが存在 ? 縮約された頂点内部にラベルがOの辺が含まれるような頂点たち全てがパスに含まれる ? パスにおいて使用した辺のラベルは全てO ? 縮約されたグラフにおいて、このパスに使用されないラベルがOの辺は存在しない であり、パスに含まれる頂点の数が 1 ならば答えは 2 、それ以外のときの 答えは 1 – 縮約された頂点内において、全ての頂点の相対出次数を(始点と終点を除いて) 0 にすることが、先程と同様に示される – パスにおいて使用した辺のラベルがEのとき、 2 回以上通らなくてはならない ため条件を満たさない – 縮約されたグラフにおいて、このパスに使用されないラベルがOの辺が 存在するとき、明らかに条件を満たさない
- 23. 問題概要 ? はじめ，頂点が存在しないような二分探索木 T がある ? 以下の Q 個のクエリを順番に処理せよ 1. 値が v であるようなノードを T に挿入せよ 2. 値が v であるようなノードの左部分木の高さ h(l) と 右部分木の高さ h(r) の差を求めよ 3. 値が v であるようなノードを右回転せよ 左の子が存在しない場合は – 1 を出力せよ 4. 値が v であるようなノードを左回転せよ 右の子が存在しない場合は – 1 を出力せよ
- 24. 部分点1(20点) ? この問題は平衡しているとは限らない二分探索木の 構築とそのバランスを調べる問題 ? 部分点 1 においてはクエリの数が少ないので、 各操作を愚直にシミュレーションすればよい – 回転操作により根が切り替わる場合があることに注意
- 25. 部分点2 (30点) ? クエリの種類は 1 と 2 のみ ? 挿入操作、バランスを調べる操作を高速に行いたい ? 挿入操作は、以下のようにして O(logN) で実現可能 – T に含まれるノードの値はそれぞれ異なる – 値 v のノードの親となるノードは以下のどちらかであり、挿入が 可能なノードは以下のどちらかのうち必ず片方のみである (ただし、値が v となるノードが根となる場合のみ例外) ? T に含まれるノードのうち、値がv 未満で最大のノード ? T に含まれるノードのうち、値がv より大きく最小のノード – 上記の親となるノードを調べる操作はsetを使って実現可能
- 26. 部分点2 (30点) ? バランスを調べる操作を高速に行いたい – ここで、最終的な木の形は定まっており、回転操作により 途中で木の形が変形することがないことに着目する – クエリを先読みし、最終的な木を構築する 4 2 6 71 3 5 8
- 27. 部分点2 (30点) ? 最終的な木を構築し、オイラーツアーを行う ? バランスを調べるクエリはオイラーツアーで割り振った インデックスを利用してRMQで取得 ? 挿入操作により頂点が追加されるたびに、親の情報を もとにRMQを更新してやればよい – 更新も取得もセグメント木ならば O(logN) で処理可能 – 更新回数も取得回数もO(QlogQ)で抑えられる
- 28. 満点 (150点) ? 木の形が回転操作により変わりうる – オイラーツアーではそのような状況に対応できない ? 与えられる木が二分探索木であることに着目する – 各ノードに部分木の値の最小値 min と最大値 maxを持たせると [min, max]が部分木を表す区間になる – この区間が分かれば、先ほどと同様RMQを用いて解くことが可能
- 29. ノードの挿入操作 ? 担当する区間は親が担当する区間より一意に定まる ? 挿入されたノードが担当する区間に 1 を加算 – (存在しないノードも親と同じ高さになるが関係ない) v [min, max] l [min, v - 1] ? [v + 1, max] v [min, max] l [min, v - 1] r [v + 1, max] +1
- 30. ノードの回転操作 ? 担当する区間の変更として表せる ? 2 つの区間に+ 1と-1を加算 v [min, max] l [min, v - 1] r [v + 1, max] v [l + 1, max] l [min, max] r [v + 1, max] +1-1
- 31. 解法まとめ ? T に含まれている値をsetにより管理する ? 各ノードには、親、左の子、右の子、担当する区間 を持たせる ? 深さは区間加算、区間の最大値の取得が可能な データ構造(セグメント木など)により管理 ? 各クエリを適切に処理する ? これはO(QlogQ)で実現可能