きままにものづくり

日々の気付いたことなんかを書いてます。

SRM620Div1Medium

問題

N人のメイドいる。それぞれM個のスキルに対しての能力表scoreが与えられる。スキルに対して安定的なソードを何度か行うことでresultと同じ結果を得られるか調べよ。

解法

ソートの順番を遡ることで答えを導く。
resultの結果が昇順にならんでいた場合はそのまま答えになる。となりあう要素の関係が重要なのでresultの結果を以下の用に加工する。
 conds_i = (result_i, result_{i+1})
スキルiに対して以下の条件を満たす場合は、そのソートを行える。
 a = conds_i.left
 b = conds_i.right
 score[a][i] \leq score[b][i]
次に、以下の条件を満たす要素をcondsから取り除く。
 score[a][i] < score[b][i]
上の条件を満たす場合は、今回のソートで順番を補正してくれるので取り除くことができる。
この処理を繰り返し、空にすることができたら"Possible"を、ソートを選ぶことができなくなったら"Impossible"を返す。同じスキルに対して複数ソートする必要はないので、M回処理を行えば必ず停止する。

計算量

 O(M^2)
M: スキルの数

コード

広告を非表示にする