3完+１ペナ 65:39で1906パフォでした。青落ち...
立ち回りの方針は基本的に前から＆丁寧に
A Larger Score
スコアを改善するので、前からK項にあるものの最小値＜持ってくる値にならないといけません。しっかりと証明はしてないんですが、2つ以上の値を持ってくるのは無駄になると思った(+順位表で割と通されている)ので、それを信じます。
i番目の値(K ≦ i, 0-indexed)を持ってくるとすると、
K+1項目に移動するまでで i-K回
そこからAiより小さい値のうち最も右にあるものを追い出せばよいので、その位置をXとしてK-X回
が最小手数になるので、 i-Xになります。
あとはこのminをとればよいです、Aiのうち小さい順にみていくとXの更新が楽になります。 (AC 12:34)
B 01 Generation
とりあえず初手で実験してみますが、いまいちいい性質がありません。
操作をもう少し言い換えられないかと考えてみます。
数列Aをflip回数を数えたものだと考えます。(その偶奇が一致すればよいです)
すると、操作Aは数列Aのすべての項に+1して、そのあとに0を先頭に加える
操作Bは末尾に0を加える
と言い換えることができます。
この数列Aについて、0112のように同じ数が連続した後にそのあとの数を増やすことはできません。
これを簡単に示していきます。
同じ数が連続している場合は操作Bが行われている必要があります。
そうでなければ、隣り合う数列の値は必ず1異なることになります(flipして0を加えるので)
11の部分で操作Bが行われているとわかると、2に該当する部分は11より後に追加されたことになります。そのため、そのflip回数が1を超えることはありません。
よって示されました。
以上より、ランレングス圧縮などで数列を圧縮し、今とれる最大値を更新していくことを考えます。連続した部分がでてきていないなら+1、そうでないなら-1をすることが最善となります。これが負にならなければ条件を満たす構築方法が存在します。(AC 29:04)
C Rotate and Play Game
ゲーム系は苦手なのでちょっと不安になりますが、それなりに通されているので頑張らないといけなそうです。
まず、「こういうことを最適化/カウントする」→「全パターンについて求めて」というタイプの問題なので、そもそもの問題(今回でいうとcyclic-shiftがないもの)ができないとどうしようもないことが多いので、そこを考えます。
とりあえず貪欲にとりたいのですが、それができない場合もあります。できない場合を考えると4321のように、大きい値が前半に連続している場合が挙げられます。
どういう時にとれないのか？と考えると、2*i項までに取りたいものがi+1以上あるとだめだとわかります。
なんとなくできるとき・できないときがわかってきたので、問題に戻ってみます。直感的に取りたいのが前に連続しちゃった...となるならば、うまいことshiftすれば最大値が達成できるのでは？と思います。(maroonさんによくある自明な上界/下界)
そこで、sample3で最大値を計算すると一致します。
また、この仮説が正しいとすると「わざわざkを聞く理由」もでてきます。
このあたりからおそらく最大値は達成できるのだろうと見切りをつけます。
ここまでわかるとかなり扱いやすくなります。
まず取るべき値/そうでない値の2値に分類できます。
ここで、さっき考察しておいた「どういう時にとれないのか？」を考えてみると、2*iまでの和がi+1になるとダメだという結論があったので、これを適用していきます。
(どちらでもいいですが)取るべき値=-1, そうでない値=1と変換し直すと、偶数項目の累積和が負にならなければよいということになります。
あとは、これを累積和やSegment Treeを使って適切に区間minをとってあげて、条件を満たすか判定するとよいです。
ぼくの実装では、項を2つずつにまとめたので、1回だけshiftして奇数回shiftするバージョンも計算しました。(1WA + AC 1:00:39)
D Differ by K bits
Aを解き始めたときに中国人が3人爆速で通していたので怪しいと思ったんだよな...
中国のコンテストで既出らしいです。
まずAGC031 Differ by 1 bitが近そうなので見に行きます。1bitのときはうまいこと構築できそうな気がするんですが、それ以降はわかりません。
立っているbitの偶奇に着目すると、K=偶数のとき、立っているbitの偶奇が変化せず、どう考えても半分つくれないのでNoとなります。
また、K=Nのときも数字が2パターンしかつくれないのでN=1のときを除きNoとなります。
ここからもう少しいい条件がないかと思って、assertで提出を繰り返してみたんですがいい条件がありませんでした。というかこれ以外は全部構築できるらしいです。
粘った結果何も思いつかず終了してしまいました。解説読みましたがかなり難しいですね...。
総評
ABCはそんなに悪くないペースで解いたかなと思っていたんですが、Dがめちゃくちゃ通されていてパフォーマンスが渋かったです。
構築問題にかなり苦手意識があるので、練習していきたいです。
黄色戻るぞ～～～
