parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 数列を辞書順最小にしたいということから、貪欲。ちゃんと説明する。 最初に取り除く石について考える。取り除く候補の石の山が２種類あるとし、それぞれp,qとする。pを取った場合に次のxは3、qを取った場合に次のxは7とする。このとき解は前者では 3,?,?,... 後者では 7,?,?,... のようになり、未確定の部分がどのような値になっても辞書順最小は前者であることがわかる。 与えられた石の山aについてa[i]のとりうる値をA,B,C,D(A>=B>=C>=D)とする。下に図があり、それを見たほうがよくわかる。解の求め方は、まず石がA個ある石の山がk個あるとし、このうち一番左の山が次に追加する… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F02%2F20%2F005958" title="AtCoder ARC069 E: Frequency - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/parukii/20170220/20170220005933.jpg Hatena Blog https://hatena.blog 2017-02-20 00:59:58 rich https://par.hateblo.jp/entry/2017/02/20/005958 1.0 100%