WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Statement訳シャイニーは会社を経営していた。そこにはN人の社員がいる。社員は入社した順に0~N-1と番号が付けられている。社員0は上司を持たないただ1人の社員である。他の社員は直属の上司を1人持っている。superiorが与えられる。0番目の要素は-1であり、これは0番目の社員が上司を持たないことを表している。iが1~N-1でのsuperior[i]は、i番目の社員の上司の番号を表している。現在、社員達はこれといって仕事ができない。シャイニーはこの状況を変えたいと思っている。彼女は社員達に仕事を行うためのトレーニング受けてもらい、かかった費用を支払うことに決めた。具体的には、それぞれの社員には、2種類のトレーニングを受けてもらうことにした。K種類の仕事があり、それを行えるようになるためのトレーニングもK種類ある。training[i]はi番目のトレーニング受けるときにかかる費用を表している。複数の社員が同じトレーニングを受けた場合、それぞれの社員に費用を支払わなければならない。それぞれの社員は部署に所属している。社員xの部署は社員xとその直属の部下によって構成される。xとなるようなyがxの部署に所属している。xとなっていても、zはxの部署に所属しないことに注意して欲しい。シャイニーはオールラウンダーな部署が好きである。オールラウンダーな部署とは・部署内の社員は何か仕事を行っており、かつ・同じ仕事をしている社員がいないことである。シャイニーはそれぞれの部署をチェックするため、部署にいる社員達は部署がオールラウンドであるように、仕事を選ぶ。それが出来たならば、シャイニーはこの部署はgoodと評価する。シャイニーはN個の部署全てがgoodであれば、会社もgoodであると評価する。(全ての部署が、同じタイミングでgoodである必要はないことに注意して欲しい。各部署は、あるタイミングでオールラウンドにすることができるのであれば、会社としてgoodとなる)シャイニーはそれぞれの社員に、どのトレーニングを受けてもらうかを決めなくてはならない。彼女は会社をgoodとしたかったが、それによる費用は最小限に抑えたかった。シャイニーの会社をgoodとすることができるのであれば、それにかかる必要最小限の費用を返せ。100Petrさんのソースコードを見てまず、自分は貪欲でいけると勘違いしました。trainingを昇順でソートしておく。4を振ってけばいいんじゃないの~と考えたけど、落とし穴がある。下段右の社員は2をやらせなくてもよい。その上司は既に2の仕事を覚えているからというわけで、貪欲はちょっと厳しいので、DPをする。社員それぞれに2つトレーニングさせて、シャイニーがチェックしに来たときにどちらか仕事を選ばせることができるが、実は仕事を1つに固定しちゃっていいような気がする・・・。3)の仕事が出来る社員に、1回3の仕事をやらせましたって時に、次回0の仕事をやらせる意味はない気がする。更新の仕方が問題で、愚直にやると(部下の数!)の計算量になってしまうため、下記の様に最小費用流でもとめる。BOSSのやりたい仕事はBOSSだけに任せ、残りの仕事を部下にどう割り振ればよいか決めさせれば良い。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。