[CSA] Round #1 Sorting Partition

Sorting Partition

https://csacademy.com/contest/archive/task/sorting_partition/

題意は分かったんですが、どのようにして解けば良いのか分からなかったので、取り上げたいと思います。解説を読んでもいまいちピンと来ませんでした。

考え方

配列 \( A \) の部分配列に分け、その部分配列をそれぞれソートして、全体がソートされれうようにします。このときの部分配列の個数の最大値を求めます。

間違った考え方

最初に考えた方法は、配列の最初から最大値を見つけていき、現状の最大値と同じ又はより大きい値が出てきたら、パーティションの個数を増やします。しかし、この考えでは不十分でした。

解説の方法

配列の後ろから最小値を調べていき、最小値の区間を持つ配列を作ります。

例えば、

\[ A = \{1, 5, 3, 4, 5, 7\}\]

とすると、対応する最小値の配列は、

\[ B = \{1, 3, 3, 4, 5, 7\}\]

となります。これを用いて、次は先頭から最大値を調べていき、最小値の配列と比較します。詳しくはソースコードを見てください。

ソースコード

感想

なぜこのようにして解けるのあまり理解していないので、問題とセットで覚えようと思います。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする