問題一覧 > 教育的問題

No.3011 品物の並び替え (Extra)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 18
作問者 : cielciel
1 ProblemId : 230 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:20

問題文

ここに0番〜(N-1)番の品物がある。
また、
item1 item2 score
という形式で書かれた得点表がある。
品物を並べた時、item1がitem2よりも前であればscore点を獲得できるという意味である。

得点表が与えられるので、品物を適切に並び替えた時、獲得できる得点を最大化したい。そのときの得点および並び替えた状態を出力せよ。

※ http://yukicoder.me/problems/209
の制約強化版です。

入力

N M
item1[1] item2[1] score[1]
…
item1[M] item2[M] score[M]

$N$:品物の数
$M$:得点表の行数
$item1_i\ item2_i\ score_i (1 \le i \le M)$: 品物1、品物2、得点

制約
$30<=N<=50$
$1<=M<=N*(N-1)$
$0<=item1,item2 < N$
$item1!=item2$
$1<=score<=10000$
得点表の相異なる行において、item1とitem2がどちらも等しくなることはない。

出力

Total_Score
ordered_item[1] ... ordered_item[N]

$Total\_Score$:合計得点
$ordered\_item_i\ (1 \le i \le N)$: i番目に並べるべき品物 品物iを並べる場所ではありませんので注意して下さい。

出力について

以下の条件をすべて満たす時、ACとなります。

  • 出力要素がN+1個(以上)
  • 想定解のプログラムを100回動かして得られた得点の最大値をXとして、Total_ScoreがX*4/5 9/10以上 (※0:00変更)
  • ordered_itemに重複がない
  • ordered_itemにしたがって計算した結果がTotal_Scoreと等しい

サンプル

サンプル1
入力
4 9
0 1 1
0 2 2
0 3 3
1 2 4
1 3 5
2 3 6
3 2 100
2 1 100
1 0 100
出力
300
3 2 1 0
(this_is_garbage)

1番目に品物3、2番目に品物2、3番目に品物1、4番目に品物0を並べた時が最善です。
なお、このサンプルでは2行目にオーダーを出力しているが、各数のセパレータは空白、改行のいずれでも良い。
なお、N+2番目以降の要素は何を出力しても不正解にはならない。

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