AtCoder ARC069 E: Frequency

数列を辞書順最小にしたいということから、貪欲。ちゃんと説明する。

最初に取り除く石について考える。取り除く候補の石の山が２種類あるとし、それぞれp,qとする。pを取った場合に次のxは3、qを取った場合に次のxは7とする。このとき解は前者では

3,?,?,...

後者では

7,?,?,...

のようになり、未確定の部分がどのような値になっても辞書順最小は前者であることがわかる。

与えられた石の山aについてa[i]のとりうる値をA,B,C,D(A>=B>=C>=D)とする。下に図があり、それを見たほうがよくわかる。解の求め方は、まず石がA個ある石の山がk個あるとし、このうち一番左の山が次に追加する要素xになる。とりあえず最左でないk-1個の山からそれぞれA-B個ずつ取り除く。このときxは変わらない。次にただ1つになった最左のAの山からA-B+1個の石を取り除く。まだxは変わらない。最後にこの山から石を1個取り除く。このとき、最大の石の山の大きさはBであり、最左のBがもともとのAよりも左にあればxはその位置へ移動し、そうでない場合はxはもとの位置のままである。こうしてもとの問題よりもa[i]の値が小さくなった。あとは同じ手順をすべての石の山が空になるまで繰り返せばいい。

実装

最初のaの値について、各値が出現する最左のインデックスをmapで持っておく。また、各大きさの石の山がいくつあるかもmapで表し、最も大きい石の山を先の手順で削っていき、より小さい石の山のカウントを増やしていく。このとき、出力すべき解の変数に加算していく。

思いつき方

図を描く。手を動かす。