日経主催の競プロコンテストに参加しました。着手した問題の考察、というか自分が取った解法を書いていきます。

## 全国統一プログラミング王決定戦予選

問題一覧: https://atcoder.jp/contests/nikkei2019-qual/tasks

## A - Subscribers

問題概要: N 人のうち、新聞Xを購読しているのはA人、新聞Yを購読しているのはB人いる。新聞 X, Y の両方を購読しているのは最大何人で、最小何人か。

考察: 最大人数のほうを考えます。仮に A < B とすると新聞 X を購読している A 人がみんな新聞 Y も購読しているというケースで最大になり、B 人です。A > B のケースと合わせると min(A, B) 人となります。

次に最小人数を考えます。みんなが片方だけの新聞を購読しているケースが最小になる……でしょうか？ もしそうだとすると、新聞の購読者が全体で A+B 人いることになります。A+B ≤ N ならそれでいいでしょう。しかし A+B > N なら前提と矛盾します。

A+B > N のとき、何人かは両新聞を購読していると仮定している必要があります。K 人が両新聞を購読していると、全体としては A+B-K (≤N) 人です。K の最小値は A+B-K が最大値 N に等しいとき、つまり K = A + B - N です。

筆者の回答 [AC]: https://atcoder.jp/contests/nikkei2019-qual/submissions/4102236

## B - Touitsu

問題概要: 長さが N の3つの文字列 A, B, C が与えられる。いくつかの文字を書き換えたところ、A = B = C になった。書き換えられた文字数の最小値を求めよ。

考察: 文字列が等しいかどうかは、同じ位置にある文字が等しいかどうかで決まります。そのため、ある文字を書き換える必要があるかどうかは、他の位置にある文字とは無関係に決まります。つまり、それと同じ位置にある他の2文字だけによって決まります。

A, B, C の i 番目の文字がそれぞれ a, b, c であるとき、明らかに a = b = c なら書き換える必要はありません。2つが同じ文字で残り1つが異なる文字なら、異なる1文字を書き換えるのが最良です。3つの文字がすべて異なるなら、2つ書き換える必要があります。どれを書き換えるかは答えに影響しないので、気にしなくてかまいません。

これをすべての i (0 ≤ i < N) について行い、結果の総和を取れば答えが出せます。

筆者の回答 [AC]: https://atcoder.jp/contests/nikkei2019-qual/submissions/4101367

## C - Different Strokes

問題概要: N 個の料理がある。i 番目の料理は、高橋くんが食べると A_i の幸福度を得て、青木くんなら B_i の幸福度を得る。高橋くんから始めて、交互にいずれかの料理を食べる。高橋くんの幸福度を X、青木くんの幸福度を Y とするとき、高橋くんは X - Y が最大になるように料理を選び、青木くんは Y - X が最大になるように料理を選ぶ。最終的な X - Y の値を求めよ。

考察: 高橋くんが料理 i, j のどちらを選ぶかという状況を考えます。

A_i + B_i > A_j + B_j のとき A_i - B_j > A_j - B_i なので、高橋くんは料理 j より料理 i を選んだほうがよいです。

したがって、 (A + B) の値でソートすると、料理は上から順番に選んでいくだけになります。

筆者の回答 [AC]: https://atcoder.jp/contests/nikkei2019-qual/submissions/4106588

ちなみに私は A_i + B_i = A_j + B_j のケースで A_i > A_j の料理を取らなければいけない、と思いこんでいましたが、これは計算ミスによる勘違いでした。

## D - Restore the Tree

問題概要: N 頂点の根つき木に M 本の有向辺の書き加えて得られるグラフが与えられる。追加された辺は、もとの根つき木において親から子孫へ向けて張られている。もとの根つき木を求めよ。

考察: 頂点 v に向かって伸びている辺の個数を v の入次数と呼ぶことにします。

根つき木の根の入次数は 0 であり、他の頂点の入次数は 1 以上です。そのため、根がどれかは入次数を計算するだけで分かります。

根から深さ優先探索をしてみれば、何らかのツリーは構成できますが、このツリーがもとの根つき木であるとはかぎりません。というのも、ツリーを構成する際に削除した辺 (書き加えられた辺) が「親から子孫に向かって伸びている」という条件と矛盾する可能性があるからです。

もとの根つき木におけるノードの世代という概念を考えます。根を第0世代、根の直接の子を第1世代、第1世代の直接の子を第2世代、……とします。

書き加えられた辺はもとの根つき木において世代を2つ以上飛び越える辺です。というのも、世代を遡るような辺や同じ世代への辺は条件に反します。1世代先への辺は、親から子への辺がすでにあるので、書き加えられません。

根が分かっているということは、第0世代の頂点はすべて分かったといえます。根から幅優先探索して、頂点の世代を1世代ずつ順番に確定させていけば復元できそうです。

探索中に頂点 u から頂点 v に伸びている辺を辿るとき、この辺がもとの根つき木の辺であるか考えます。

頂点 v の入次数が 1 ならYESです。というのも、もとの根つき木が連結であるために、この辺が必要だからです。

頂点 v の入次数が 2 以上ならNOなので、この辺は削除し、v の入次数を減らします。NOであるというのは以下のように分かります。

入次数が 2 以上であるということは、u とは別の頂点 w から頂点 v への辺が存在します。

探索中に辺を削除しているので、u より前の世代から v への書き加えられた辺は削除済みです。だから w→u はそういう辺ではありません。

u より前の世代から v へのもとの根つき木の辺があるとしたら、それはすでに探索済みで、しかも v の入次数が 1 のはずですから、これもありえません。そのため w は u と同じかそれ以降の世代の頂点です。

w が u と同じ世代であるケースを考えます。u→v が書き加えられた辺ならOKですが、仮にそうでないとすると v は u の次の世代であり、w→v と u→v はどちらも親子間の辺なので w = u だったということになります。矛盾したので、u → v は書き加えられた辺です。

w が u より先の世代の頂点なら、辺 u→v は世代を飛び越えているため、書き加えられた辺だといえます。

この手続きによって書き加えられた辺をすべて削除すれば、もとの根つき木を復元できます。

筆者の回答 [AC]: https://atcoder.jp/contests/nikkei2019-qual/submissions/4105392

公式の解説PDFによれば、トポロジカルソートをしたらもっと楽に解けるそうです。

## おわりに

D 完でした。