[AtCoder] 天下一プログラマーコンテスト2016予選A B – PackDrop

PackDrop

方針

ネットワークの信頼性の問題のようであり、問題文が少し長いです。

子機器を持たない末端のノード (葉ノード) が \( B_i \) です。機器 \( 0 \) (根ノード) から \( B_i \) への到達率を \( 0.99^{C_i} \) にするということは、\(B_i \) とその親機器 の間に PackDrop を \(C_i\) 個設置すれば可能です。つまり、必要数の最大値は \(C_i\) の合計となりますが、今回は最小値を求めるのでもう少し考える必要があります。

葉から根に向かって親のコストを更新する

まず初めに、ノード \(i \) におけるコストを \(A_i\) と定義します。このコストは PackDrop の必要数に対応します。

葉ノードのコストを \( A_i = C_i \) として初期化します。それ以外のノードは根ノードを除き \( ∞ \) とします。次に、葉から根に向かって、親ノードの値と子のノードの値を比べて、親ノードのコストを全ての子ノードのコストの中の最小値で置き換えます。これを全ての葉ノードから深さ優先探索で根ノードまで行います。このとき、根ノードの最小値は \( 0 \) とします。

根から葉に向かってコストを更新する

上記の更新によって根ノードの子ノードのコストは確定しています。

よって、根ノードの子ノードからから葉に向かってコストを更新していきます。更新方法は、子ノードのコストから親ノードから累積されたコストを引きます。累積されたコストとは、深さ優先探索を行ったときに訪れた親ノードのコストの和です。

深さ優先探索では、根→子→子→…→葉のように探索されるので、葉ノード以外では、ある子ノードは次の探索における親ノードと見ることができます。探索において、子ノードは親ノードの累積コストを引かれますが、マイナスになることはありません。これは、親ノードのコストが子ノードの探索によって伝搬された最小値で置き換えられているためです。

コード

参考サイト

https://www.hamayanhamayan.com/entry/2016/07/30/233610

感想

300 点にしては考察が難しい問題だと思いました。解説を読んでなんとなく理解することができました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする