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: スキルの数

きままにものづくり

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

問題

解法

計算量

コード