なおさん のコメント

強連結成分分解で書いてみた http://ideone.com/TacSya
No.1
64ヶ月前
このコメントは以下の記事についています
Naomiは、とあるアクションゲームをしている。 そのゲームでは、N個(1から番号がふられている)のステージがありそれぞれ難易度が設定されている。 さらに、それぞれのステージは、先に指定されたステージをクリアしていると難易度が半分になるという仕組みになっている。 選んだステージは必ずクリアできるとし、すべてのステージをクリアすると考える。 この時、任意の順番でステージを選べるとして、各ステージの難易度の合計が最小になるように、ステージを選ぶとしたとき、その難易度の合計を求めてください。 答えは小数になることもあるが、小数第一位まで求めるとして、丸め誤差などの誤差はないように求めてください。 (Special Thanks アルゴリズムアドバイス nmさん) 【入力】 N L1 S1 L2 S2 ・・・ Li Si ・・・ LN SN 一行目には、そのゲームのステージ数を表す整数値N(1<=N<=100)が与えられます。 2行目以降の、各i(1<=i<=N)行目はi番目のステージの特徴を表している。難易度を表す整数値Li(1<=Li<=100)とすでにクリアしていると難易度が半分になるステージの番号Si(1<=Si<=N)が半角スペース区切りで与えられる。 【出力】 答えの数値を文字列として出力してください。 答えは小数になることもあるが、小数第一位まで求めるとして、丸め誤差などの誤差はないように求めてください。 【sample1】 3 5 2 8 3 3 1 【ans1】 9.5 3つステージがある。 ステージ1は 難易度5ですでにステージ2をクリアしていると難易度が2.5になる。 ステージ2は 難易度8ですでにステージ3をクリアしていると難易度が4になる。 ステージ3は 難易度3ですでにステージ1をクリアしていると難易度が1.5になる。 この時、初めにステージ3からはじめ、2,1とクリアしていくと難易度の合計が最小の9.5となる。 【sample2】 5 5 1 8 3 3 2 6 5 9 4 【ans2】 22.5 ステージ1は、自身をクリアしていると難易度が下がるが、1度クリアすればいいのでこの場合特に意味はない。 クリアの順は左から[1,3,2,4,5]や[4,5,3,2,1]とクリアしていくと最小の22.5となる。 【sample3】 15 1 2 2 1 3 3 4 6 5 4 6 5 7 5 8 7 9 7 10 7 11 15 12 14 13 15 14 11 15 15 【ans3】 71.5 キーワード:union-find/幅優先探索/閉路検出/強連結成分分解 【problem】 https://gist.githubusercontent.com/yuki2006/5b84d7babd848dcd7ee6/raw/e6599e891ec8a3b0a457d116729d4910e20dc674/yukicoder19.txt 1st. chokudaiさん C# http://ideone.com/vRJqfe http://ideone.com/oYIE70 (閉路検出しない方法) 2nd. なおさんC++ http://ideone.com/4y6FO7 http://ideone.com/TacSya (強連結成分分解)