AT_future_contest_2022_qual_a Project Leader

[problemUrl]: https://atcoder.jp/contests/future-contest-2022-qual/tasks/future_contest_2022_qual_a $ N $ 個のタスクを $ M $ 人のチームメンバーに割り振りたい。 各タスクは高々1人に割り振り、タスクが割り振られたチームメンバーにはそのタスクが完了するまで他のタスクを割り振ることは出来ない。 全部で $ K $ 種類の技能があり、各チームメンバー $ j $ には技能レベルを表す非負整数ベクトル $ \bm{s_j}\ =\ (s_{j,1},\cdots,s_{j,K}) $ が、各タスク $ i $ には要求技能レベルを表す非負整数ベクトル $ \bm{d_i}\ =\ (d_{i,1},\cdots,d_{i,K}) $ がそれぞれ定まっている。 このうち、各チームメンバーの技能レベル $ \bm{s_1},\cdots,\bm{s_M} $ は入力として与えられない。 $ w_{i,j}:=\sum_{k=1}^K\ \max(0,d_{i,k}-s_{j,k}) $ と定める。 チームメンバー $ j $ にタスク $ i $ を割り振った時、タスクの完了までには以下のように定める $ t_{i,j} $ 日かかる。 1. $ w_{i,j}=0 $ の場合、$ t_{i,j}=1 $。 2. $ w_{i,j}\ >\ 0 $ の場合、$ -3 $ 以上 $ 3 $ 以下の整数値をとる一様乱数を $ r_i $ として、$ t_{i,j}=\max(1,w_{i,j}+r_i) $。 $ t $ 日かかるタスクを $ d $ 日目に開始した場合、$ d+t-1 $ 日目の終わりにそのタスクは完了する。 タスク間には依存関係があり、あるタスクを開始するためには、依存する全てのタスクが前日の終わりまでに完了していなければならない。 出来るだけ短い日数で全てのタスクを完了してほしい。 ### Input & Output Format 各入力値の範囲については入力生成の項を参照せよ。 まずはじめに、タスク数 $ N $、チームメンバー数 $ M $、技能数 $ K $、依存関係数 $ R $、各タスクの要求技能レベル $ \bm{d_1},\cdots,\bm{d_N} $、依存するタスクの組のリスト $ (u_1,v_1),\cdots,(u_R,v_R) $ が以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ R $ $ d_{1,1} $ $ \cdots $ $ d_{1,K} $ $ \vdots $ $ d_{N,1} $ $ \cdots $ $ d_{N,K} $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_R $ $ v_R $ $ (u_i,v_i) $ は、タスク $ v_i $ ($ 1\leq\ v_i\leq\ N $) がタスク $ u_i $ ($ 1\leq\ u_i\leq\ N $) に依存しており、$ v_i $ を開始する前に $ u_i $ を完了しなければならないことを示している。 $ u_i\ $ m $ $ a_1 $ $ b_1 $ $ \cdots $ $ a_m $ $ b_m $ **出力のあとは標準出力を flush しなければならない。**そうしない場合、TLEとなる可能性がある。 次に、その日の終わりにタスクを完了したチームメンバーのリスト $ f_1,\cdots,f_n $ ($ 1\leq\ f_1\

N/A

N/A

### ストーリー F社のプロジェクトリーダーに就任したあなたの仕事は、チームメンバーに適切にタスクを割り振ることである。 現在取り組んでいるプロジェクトはいくつかのタスクからなり、 各チームメンバーの持つ技能レベルと各タスクごとの要求技能レベルに応じて、タスクの完了までにかかる日数の期待値が変化する。 経験豊富なあなたは、各タスクの要求技能レベルを正確に把握することが出来るが、就任したばかりのため、各チームメンバーの技能レベルはまだ全く分かっていない。 チームメンバーの技能レベルを徐々に見極めながら、適切にタスクを割り振ってほしい。 ### 例 日数 Output Input 事前情報 ``` 3 2 2 1 0 1 2 0 1 1 2 3 ``` 1日目 ``` 2 1 1 2 2 ``` ``` 1 1 ``` 2日目 ``` 0 ``` ``` 1 2 ``` 3日目 ``` 1 1 3 ``` ``` 0 ``` 4日目 ``` 0 ``` ``` 0 ``` 5日目 ``` 0 ``` ``` -1 ``` ### 得点 $ D $ ($ 1\leq\ D\leq\ 2000 $)日目の終わりに全てのタスクを完了した場合、$ N+2000-D $ の得点が得られる。 $ 2000 $ 日以内にタスクを全て完了出来なかった場合は、完了したタスクの総数を $ T(\ $ N $ $ M $ $ K $ $ R $ $ d_{1,1} $ $ \cdots $ $ d_{1,K} $ $ \vdots $ $ d_{N,1} $ $ \cdots $ $ d_{N,K} $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_R $ $ v_R $ $ s_{1,1} $ $ \cdots $ $ s_{1,K} $ $ \vdots $ $ s_{M,1} $ $ \cdots $ $ s_{M,K} $ $ t_{1,1} $ $ \cdots $ $ t_{1,M} $ $ \vdots $ $ t_{N,1} $ $ \cdots $ $ t_{N,M} $ これらの情報があれば、提供されたテスターを用いる代わりに同等のテスターを各自実装することも可能です。 また、プログラムの出力において `#` から始まる行はコメントとして無視されます。 特に、`#s` から始まる行は、以下の形式で記述された技能レベルの予測値であると解釈され、ビジュアライズ時に使用されます。 > #s $ i $ $ s_{i,1} $ $ \cdots $ $ s_{i,K} $ 予測値は何度でも出力でき、同じ $ i $ に対する予測値は上書き更新されます。 Web版のビジュアライザでは予測値の変化をアニメーションで確認できます。 例えば例で示した出力にコメント行を以下のように挿入することで、1日目に $ s_1 $ の予測値を $ (0,\ 1) $ に、2日目に $ s_2 $ の予測値を $ (1,\ 0) $ に更新することが出来ます。 ``` 2 1 1 2 2 #s 1 0 1 0 #s 2 1 0 1 1 3 0 0 ``` コメント行は実際の提出でも無視されるため、そのままのプログラムを提出可能です。 ### サンプルプログラム(Python) ``` # assign random tasks to team member 1. import sys import random # Prior information n, m, d, r = list(map(int, input().split())) task_difficulty = [] for i in range(n): task_difficulty.append(list(map(int, input().split()))) task_dependency = [[] for _ in range(n)] for i in range(r): temp = list(map(int, input().split())) task_dependency[temp[1] - 1].append(temp[0] - 1) # -1: not started # 0: started # 1: completed task_status = [-1] * n # -1: not assigned # k: assigned task k (1