問題一覧 > 通常問題

No.468 役に立つ競技プログラミング実践編

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 : kuuso1 / テスター : tubo28
6 ProblemId : 1456 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-12-18 00:44:21

Note

この問題はAdvent Calendar Contest Advent Calendar 2016 の18日目の記事として作問されました．

予備知識

品質管理の手法として良く知られたものに「新ＱＣ７つ道具」と呼ばれるものがあります．
今回はその中の一つであるところの「アローダイアグラム法」にクローズアップしてみたいと思います．
「アローダイアグラム法」はプロジェクトを達成するために必要な作業の工数や順序関係を，
下図のように図形化することでボトルネックを調べたり効率よく進捗管理するために用いられる手法のことです．


プロジェクト全体のつながりを上図のように「結合点」と「作業」でつなぎ，各作業にはその作業に必要な時間を併記します．
結合点は，プロジェクト内における各取り組みや，マイルストーンとなる区切りなどを表します．
ある結合点から作業を開始するためには，その結合点に至るすべての作業が完了している必要があります．
例えば，ある取り組みと別の取り組みの完了時期を同期させたい場合などは，作業時間0の矢印を書きます．
（図中の結合点4から結合点5のように）
時刻0からこのプロジェクトが開始するとして，完了までに必要な時間は，例えば下図のように求めることができます．



各結合点ごとに最速でいつ着手できるか（最早結合点時刻）を求めることで，全体に必要な時間を計算でき，
また各結合点ごとに最悪でいつ着手しなければ全体に遅延を生じてしまうか（最遅結合点時刻）を求めることもできます．
最遅結合点時刻と最早結合点時刻が一致するということは，着手できるようになってすぐに着手しなければならないということなので，
その結合点が全体を律速していることを意味します．
そのような結合点を結ぶことで全体のボトルネックとなる工程（クリティカルパス）を明らかにすることができます．


問題文


さてあなたは今，のべN人のプロジェクトのリーダーです．
のべN人は0,1,…,(N−1)と名前がついており，0と(N−1)はあなたであり，プロジェクトの開始と終了を宣言します．
プロジェクトには合計でM個の作業があります．
i 番目の作業 (0≤i<M) は，Aiさんに割り当てられていて，所要時間Ciで完成し、次のBiさんに渡されます．
すべてのメンバー(0,1,…,(N−1))は，自分のところに集まる作業がすべて完了してからしか自分の作業に着手できませんが，
自分の抱える作業は，すべて完全に並行にすすめることができると考えていいです．
（時刻 t に着手したならば，そのメンバーが担当するk個の作業 （所要時間 {C0,C1,C2,…,Ck−1} ）は，
　それぞれ時刻 {t+C0,t+C1,t+C2,…,t+Ck−1}に完了する．）

もっとえらいひとがいかにも知りたいであろう以下の情報を，指定の要領で報告してください．
・プロジェクト全体の完了に必要な最短時間
・最短時間での完了を実現するうえで，余裕有りと見込めるのべ人員（クリティカルパス上に居ないのべ人員）の数の割合

入力

N M
A0 B0 C0
A1 B1 C1
⋮
AM−1 BM−1 CM−1


入力は全て整数であり，それぞれは以下の制約を満たす．
3≤N≤105
2≤M≤5×105
0≤Ai<N , 0≤i<(M−1)
0≤Bi<N , 0≤i<(M−1)
0≤Ci<160 , 0≤i<(M−1)
全体の連結性および，0がプロジェクト開始，N−1が完了であることは保証される．
また，作業のループは発生しない．

出力

T P/N

ここで，Tはプロジェクト全体の完了に必要な最短時間．
Pは最短時間での完了を実現するうえで，余裕有りと見込めるのべ人員（クリティカルパス上に居ないのべ人員）の数．
Nは与えられるNをそのまま出力．
最後に改行してください。

サンプル

サンプル1
入力
8 12
0 1 3
1 2 7
1 3 2
2 4 1
3 4 6
2 6 4
3 5 1
4 6 2
4 5 0
4 7 4
6 7 2
5 7 4
出力
16 3/8

上の図のケースです．3人はメンバー3,4,5の3人です．

サンプル2
入力
5 4
0 3 3
3 1 2
1 2 3
2 4 1
出力
9 0/5


こういうケースです．
開始と完了はそれぞれ0,N−1が保証されますが，各作業ではAi<Biが保証されないことに注意してください．

サンプル3
入力
8 12
0 1 3
0 2 3
1 3 3
1 4 3
2 3 3
2 4 3
3 5 3
3 6 3
4 5 3
4 6 3
5 7 3
6 7 3
出力
12 0/8


パラで進んでいるように見えて，全員がクリティカルパスに乗っていることももちろんあります．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。