実質 ARC の企業コンテストです。結果はD完でしたが、いつも以上にグダグダであやふやな考察をしていました。
M-SOLUTIONS プロコンオープン
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Sum of Interior Angles
問題概要: 正 N 角形の内角の和は何度か。
考察
- 内角 = 180 - 外角
- Σ外角 = 360
なので、
- Σ内角 = 180N - Σ外角 = 180N - 360 = 180(N-2)
となります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/m-solutions2019/submissions/5725135
「外角の和が 360」の (中学数学レベルでの) 証明が気になって検索してみたら「内角の和が 180(N-2)」を使っている記事が多そうでした。
外角の和を使わない証明としては、(三角形の内角の和が180度であることを対頂角と平行線の同位角が等しいことを利用して示し、) 多角形の頂点から隣接しない N-3 頂点へ線を引いて N-2 個の三角形を作るという手法があるようです。
B - Sumo
問題概要: 15試合のうち、8試合以上勝てば次の大会に進出できる。いま k 試合終了して、i 番目の試合の勝敗が S(i) で与えられる。次の大会に進出する可能性があるか判定せよ。
考察
言い換えれば、7回まで負けていいということです。したがって、試合結果 S(i) のうち敗北の個数が7以下 (8未満) なら YES、そうでなければ NO です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/m-solutions2019/submissions/5724626
イテレータを使うとシンプルに書けます。
println!("{}", if S.chars().filter(|&c| c == 'x').count() < 8 { "YES" } else { "NO" })
C - Best-of-(2n-1)
問題概要: 2人のプレイヤー (高橋、青木) が以下のルールで繰り返しゲームを行うとき、片方が N 勝するまでのゲーム回数の期待値を求めよ。
ゲーム: 確率 A で高橋の勝ち、B で青木の勝ち、C で引き分け
出力形式:
求める期待値は互いに素な整数 P, Q を用いて P/Q と表せます。 R×Q≡P(mod109+7) となる 0 以上 109+6 以下の整数 R を出力してください。 (この問題の制約下で、このような R は必ず一意に存在します。)
考察
出力形式は要するに有限体の上で計算しなさいということです。
教訓《極端なケースを考える》を発動し、まず C=0 のケースを考えます。
期待値の定義から、ゲーム回数が x (≥N) で終わるケースの確率を計算することを考えます。例えば N=3 のときゲーム回数が x=5 のケースでは、ゲームの勝敗の列として以下のようなものがあります。
- AAABB
- AABAB
- AABBA
- ..
高校数学フェイズを省略すると、C=0 のケースでの期待値は以下です。
$\sum_{x=1}^{N} \binom{x-1}{N-1} (A^N (1-A)^{x-N} + B^N (1-B)^{x-N})$
次に C≠0 のケースを考えます。ゲームを以下のように言い換えると、
- ゲームの開始時に、「確率 1-C で表が出るコイン」を表が出るまで投げる
- その後、確率 A/(1-C) で高橋が勝ち、そうでなければ青木が勝つ
ゲームの回数の代わりにコインを投げた回数の期待値を計算してよいです。
1回のゲームでコインを投げる回数の期待値は 1/(1-C) です。(期待値の漸化式 E = 1 + C E からいえる。)
2 については、C=0 のケースと同様です。ただし引き分けが占める確率 C がないので、A, B が 1-C に占める割合を考えて、２人の勝率が A/(1-C), B/(1-C) になる点に注意します。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/m-solutions2019/submissions/5736724
D - Maximum Sum of Minimum
問題概要: N 頂点の木と N 個の正の整数 c(i) が与えられる。c(i) を各頂点に 1:1 で対応させるとき、木のスコアの最大値を求め、その最大値を達成する対応の一例を示せ。
- 頂点 i, j の間の辺のスコアは、両頂点に対応する c の値の小さい方
- 木のスコアは、辺のスコアの総和
考察
グラフの構築問題はパスグラフとスターグラフを考えるとよいらしいですが、入力例に載っています。
パスグラフの例では、左の頂点から順番に c(i) の小さい数を割り当てていくとスコアが最大になります:
1 - 2 - 3 - 4
スターグラフの例では、中心の点に最大値を割り当てるとスコアが最大になります:
1
|
2 - 6 - 5
/ \
3 4
辺のコストは min(c(i), c(j)) なので、max c(i) は採用されないことが分かります (正確には、max c(i) が n 個あるとき max c(i) のスコアを持つ辺は最大 n-1 個)。
正当性がないので詳しくは書きませんが、おそらく
- 大きい値は近くに集めた方がいい
- うまく根を決めて BFS
- 最大値の隣になるべく大きい値を置くと良い => 次数が高い点を根にすると良い
と予想して、「次数が最大の頂点を根として BFS で c(i) を降順に割り当てる」というアルゴリズムを試したところ AC でした。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/m-solutions2019/submissions/5732267
実は、次数は何も関係ない。それはそう。
振り返って考えると、「最大スコアが sum c(i) - max c(i)」であることが分かれば任意の点からの DFS (BFS) で良いことが以下のように正当化できるので:
「max c(i) は採用できませんが、逆に max ではない c(i) は採用できるかというと、常に採用できます。再帰的に、c(i) より大きい c(j) はすべて頂点に割り当てたと仮定します。割り当て済みの頂点の隣に c(i) を割り当てれば、c(i) が間の辺のスコアとして採用されるからです。」
スコアの上限が sum - max であることに気づけなかった (& 証明できなかった) のが敗因 (?) かなと思いました。