Atcoder: Nikkei Programming Contest 2019
A. Subscribers
難しい. 解答例
の最大値および最小値を求める問題.最大値がなのは分かる.最小値には「どちらも購読していない人たちが人以上でなければならない」という条件が入る:より,先の人数は,移項してが必要.加えてであるから,連立させてとなる.
B. Touitsu
最初なんとなくどれかに揃えれば良さそうな気がしたがそんなことは無かった.の文字目について多数決を採ればよい.どれも異なればコストは+2, 1ペアだけあれば+1, すべて揃っていれば+0. 解答例
C. Diffrent Strokes
高橋くんが目標を実現するための手段としては「自分のスコアを大きくする」以外に「青木さんのスコアを小さくする」もある.ここから考えると,高橋くんが番目を取ると青木さんはを取れないから高橋くんはだけ得すると考えられる.よってをソートし,これが大きい順にを取ればよい.青木さん視点でも同様に考えればの大きい順に取りたいこととなる.したがって先のソート結果から二人して大きい順に取って行き,高橋くんの手番ではスコアに+を,青木さんの手番では-していけばよい.
editorial
解説では片方の得点だけを考えてよいようにゲームを変形している.青木さんがすべて食べた状態,すなわち高橋くんのスコアがの状態から高橋くんがを選んで自分のスコアに加算する(青木さんがを選んでもスコアが変動しない)ゲームを考えても同じこと.すると両者が注目すべきは高橋くんのスコアだけになる:高橋くんは自分のスコアを増大させることだけに専念すればよいのでの大きいほうから取って行けばよい.青木さんが出来ることは高橋くんが高いスコアを取れないように妨害する,すなわちの大きいほうから取っていくことだけである.
D. Restore the Tree
トポロジカルソートはこの前やったこともあり使いそうだとは思ったもののどう使えばいいかわからず撤退.閉路ができるのではと疑ってしまったのだが全くそんなことは無かった(木構造に対して親から子孫に矢印を引くので子孫から親方向の辺が作られることはない).
解説(editorial?)
根からトポロジカルソートすると(根は入力辺が無い点を調べればすぐに求まる),その結果はすべての辺のin/out順に並んでいる.いま要素に入る辺が(出現順序もこの通りとする)から出ているとき,元々の木に存在した辺は.
証明(editorialが分からなかったので独自解釈,したがって誤りがありそう):が元々の辺だったとすると,操作によってを引く条件から元々の木にもからに至る経路[1]が存在することとなる. まず元々は木構造であるから合流地点は存在しない:いまに入る辺はとがあり,これらが同一でなければならないからである.ここでからへの経路はとなるが,これに含まれる各頂点はこの順序でトポロジカルソートに現れるはずである.これはの順序に矛盾.
一方でが元々の辺であるとすればとなり,問題なく操作によってを引くことが可能.辺の出自がと3頂点以上の場合も各とに対して同様の議論を適用すれば以外あり得ないことが分かりそう.
最初トポロジカルソートにおいて右側の要素の深さは左の要素と同等またはそれ以上だと勝手に思っていたのだがそんなことはない(wikipediaの図からも分かる).木構造でも片方の子を深く掘れば反例が作れる.
追記:editorial式
上を踏まえてeditorialを読むとそれなりに分かった気になれた:点に入る辺を(はトポロジカルソートに従って整列されているとする)とすると,合流地点が存在しないことから元の木でのからへの経路はすべてただひとつの辺に合流する(元の木でのの親).よってはの祖先(またはそれ自身)であるから,はトポロジカルソートにおいてこの順に現れることが分かる(重複部については順不同とする).いまの中にが存在するが,それはしかあり得ない.
こうして見ると合流地点の非存在性を意識できなかったことが敗因な気がする.
別解
本番で思いついたものの詰めきれずに捨てた解法だったがこれでも正解できるようだ.各頂点について根からの距離が最長となるような経路が元の木の経路となる.理由としては操作によって追加される辺は先祖から子孫を繋ぐ,すなわち根からの距離を減少させるようにしか張れないことが挙げられそう.これにより距離最大以外の経路を採用すると最大長の経路が作れなくなって矛盾する(と思う).
今回のようなDAGの最長経路の求め方を検索すると,トポロジカルソートを利用したものが出てくる.GeeksforGeeksによると,トポロジカルソート順に頂点を調べ,そこを始点とする辺の終点について距離を更新していけばよいとのこと.理由が書かれていないので推測:通り過ぎた頂点に対して新たに最長経路が見つかるとそこから到達する頂点すべてに対して再計算が必要になるが,トポロジカルソート順だと一度通り過ぎた点はもう使われないために再計算が起こらないから? 解答例
ところで提出を眺めていると上位陣にこれをBFSで求めている解答が複数存在した[2]. BFSのアルゴリズムを思い出すと,BFS順で最後に点に到達するときが根からまでの最長経路となる(最短経路から順に見つかっていくので).したがってBFS順で最後になるまでは無視し,最後になったらようやく遷移をすればよい.最後かどうかはに到達する辺の個数を数えておけば判断可能で,このときに親ノードを記録し,遷移をしていく.重みが一定の場合にしか使えなそうだが考え方として面白かった. 解答例
最初は「根からDFSをして各頂点に対して根からの最長距離を記録しておけば,もう一度DFSをすることでその情報から経路を復元できる」という方針を立てていたのだがこの方針だと例の再計算を何回も行うことになりTLE.
後にも述べるが木は合流地点を持たないためとが同時に辺であることはない.従っては必ず存在する. ↩︎
https://atcoder.jp/contests/nikkei2019-qual/submissions/4100659 など. ↩︎