AGC065

Bのみ1完。AGCのわりに疲れていない。最初なかなか集中できないと思っていたけど、後半になってもそこまで難しいことはしていなかった(そこまで頭は使わないBの実装、何もわからないので頭が空回りするA)。疲れよりも無力感がある。ABに大体90分ずつ使ったが、もしAが60分で解けていればCを30分考えることができていたわけで、自分はそういった機会も得られないんだという無力感。終了後に考えても集中力がダンチで、同じくらい考えるのに10倍くらい時間がかかって効率悪い。

A - Shuffle and mod K

0の扱いから、最小化する問題とは違うものになる。自分の右に自分より小さい数が来ると1つ上の世界に行ける。この回数をまず最大化する。とりあえずmapで度数分布を求める。これを横に切って使いたかったが、できないのでmapをなめて減少列を貪欲に作っていく(eraseの戻り値が削除したやつの次の(大きい)要素なので実装上は増加列を作った)(計算量は、0個になったら消せばO(N*log(N)))。0,3の間に1を入れて0,1,3にしても、2,1の間に5を入れて2,5,1にしても意味はない。減少列を並べればよさそう。ここで、全体の先頭はできるだけ小さく、末尾は大きくしたい。列が1個しかないときは場合分けしておく(0個のことはない)。先頭候補の最小値とその位置を除いた末尾の最大値、みたいにその反対もやって大きいほう(どっちも非正だけど)を採用。サンプルが弱すぎるので自分でテストケースを作ってバグ(1個除いた最大値とか苦手すぎる)を見つけて直して提出、WA。5分くらい考えてBへ。

Bも難しかったので、そこから15分くらい、AB交互にやっていた。4,3,6,4,3,2を4,3,2,6,4,3にすれば改善すると気づいた(撃墜ケースを見つけた)が、こんなんできるわけないと思い一旦Aを捨てた。

Bを通して戻ってきた。かなり通されてはいるが、全然わからない。最も短い減少列の区間が常に作れるのではと思い提出してみると、WA。これの撃墜ケースを考えていると、貪欲に作った最後の2つの減少列を組み合わせればそれが常に実現できるように思った。撃墜できるわけないという思いの中でコンテスト終了。終了後、writerのツイートを見て、9,0より0,9のスコアが高いことを知る。あまり疲れてないと言いつつ、修正を考える気力はない。

Aは難しすぎる。自分には難しすぎる。一番重要なコンテストだと思って毎回臨んでいるのに、あなたはべつに対象じゃないですよと言われ続けて精神崩壊。

(追記)自分で考えてもわからず、解説を見てもやり方しか書いてないように見えるので困った。たまたま見つけたブログにより、Aの全ての要素を1大きくしても答えが変わらないと初めて知る。確かにそうだ。問題を自分の中でエンコーディングしてずっとそれをやっていたが、あまりにも難しいので元の問題文に立ち返る余裕がなかった(普段はなかなか解けなかったらやっている)。ずらしていいとなると、上の世界に行く回数は最大に固定していい(最適解の先頭をK-1とかにすれば最大になる)。最頻値の「幅」を最小にしたいので、最頻値が現れない幅の最大を求める(これは次の要素との差をN回調べればいい)。

B - Erase and Insert

初手がN通り。そこからだんだん選択肢が減っていく。減り方が色々なので困るが、そこをまとめてDPできる可能性を見る。操作を素直に前からやるか、後ろから戻すかで迷う。後ろからは正当性に自信がないが、前からはさすがに煩雑になりすぎて無理に思えるので、後ろから。N=6で順列がPの状態から6を動かした直後を考える。次に5を動かすが、5がどこにあったかは関係ない。6より左へ動かす必要がある。6より左に次の4があった場合、4のすぐ左に置くかすぐ右に置くかの2通りはどちらも同じことになる。こんなんまとまるのかと思っていたが、DPの持ち方を日本語で書いていくと整理されて希望が見えてきた。このへんはAGCなだけあって見慣れないDPなのでかなり時間がかかる。このDPを構築するのに一番頭を使った。

(0-indexedで)iをどこかから動かすとき、dp[j]を、i+1の左にi未満がj個あるときの(iをどこに動かすかも含めた、最終的にQになる)通り数とする。i+1がNのときは、i+1が右端のさらに右にあるとする。i-1がそのj個に含まれるかはPを毎回愚直に調べればわかる。i-1の場所から右は、iが1小さい前回のDPの結果の参照先が1ずれる。左端に動かしたときは1通り(そこから先のムーブが左端への移動に固定される)で、それ以外は累積和で更新できる。最後、盤外にあるNの左にN-1未満がN-1個あるので、dp[N-1]が答え。実装することでしか考えを整理できなかった。

サンプルが合わず、サンプル1を使って計算過程を調べると、どうも値が小さい。累積和に左端の1通りを入れる必要があるのにうっかりした。このデバッグも大変だった。結局、Bを通したときには30分しか残っていなかった(3時間あったのに!)。