なかなかトケナイなぁ。
ARC079D Decrease(Contestant ver.) (600) トケタ
さすがに簡単だった。たぶん次の前振りなだけだと思う。構成ゲーはあっさり解ける場合もあるので、着実に拾いたい。
ARC079E Decrease (Judge ver.) (600) トケナイ
こっちは解けなかった。悲しい。
mod N+1不変は気付いてたけどそこから進まなかった。操作終了後の余りの様が分かればいいのになと思っていたが分からず、「操作の場所を考慮しなくていい」というところに行きつかなかったのは反省。愚直なシミュレーションは考えていたので、気付いていたら解けていたかもしれない。
競プロでは、「こういうことが分かればいいな」というのが分からない場合に、考察力が足りないのではなく、そもそもわかんない(から全探索せよ)、という時も往々にしてあるので、注意が必要。
codeFlyer （bitFlyer Programming Contest D 数列XOR (600) トケタがカケナイ
F2上の行列で扱えばいいのは気付いたけど、今のところ書けません。悲しいね。
そろそろ行列ライブラリを自分で作る段階に入ったのかもしれない。ランクとか累乗とかたまに出るけど、書けないと悲しいので、何とかしないと。
Mujin Programming Challenge 2018 F チーム分け (600) トケナイ
数え上げDPっぽい。最後の人の組を決めるのは指数時間かかりそうなので没。最後の人を除いて組んで、そこに最後の人を差し込む、という方針でうまく行きそうだったけど、何人目までかの他に管理するものが分からずタイムアップ。人数制限がなければそれで解けるんだけどなー。サイズを昇順・降順にするとうまくいくかもと思ったがそれもダメ。
解説を読む。c[k]=iとなるkの個数カウントは典型やんけ...文字列ならできるのに、数列だとなぜかできなくて悲しい。順番に関係なく対等なときはこうしてカウントして扱うべきでしたね...
DPの管理は「i人以上の組まで作る」「j人残っている」というもの。結構考えづらいなぁ。しかし、人数制約をうまくクリアするならそうするしかないのかもしれない。こういうの解けるようになりたいなぁ...
ARC071E TrBBnsformBBtion(600) トケタ
mod3という不変量がすぐに見つかって、累積和で簡単にトケタ！こういう数オリのCっぽいのはできる。競プロでも不変量チックな議論は結構やるので、見落とさないようにしたい。
CODEFESTIVAL2018FinalE Tough Journey(600) トケタ
キュー使って更新していけばよくねと思ったがそれではO(NK). しかし普通にK個戻って最小を見るだけだなとなり、Segment Treeで解決。たぶん初めてSegmentTreeを使って通せた気がする。やったね。でも添字がアホほどズレたので、気を付けないと。
さて想定解法的には問題なかった(重量システム=賞味期限システム、は分かりやすいな)が、スライド最小値でO(N)でできるのは知らんかった。普通に蟻本に載ってたね...(上級だけど) 後で確認。
全国統一プログラミング王決定戦予選2019 E Weights on Vertices and Edges (800) 昔見た
ちょっとネタバレ食らってたけど、もう一度考えた。まず連結成分を見るので、Union-Findを使いたいのと、操作を逆順で見ればよさそう、ということが分かる。そこで辺を削除するのではなく追加していって辺の数を最大にしたい、となるけど、ここで典型「ソートせよ」を用いる。重さの小さい順に入れていけば、もし追加できるときに過去の辺についても追加できる。
そこで、次のアルゴリズムをする。
1. n頂点のみのグラフを用意し、重さの小さい順に辺を追加する。
2. もし重さ条件を満たさなかったら、とりあえず辺は追加し(=unionし)、「後で追加するかも」としてプールしておく。
3. 重さ条件を満たせば、辺を追加し、その連結成分にプールしておいた辺も同時に追加する。
これでなんかいけそう。正当性はちゃんと示してないけど、Union-Findのライブラリをいじって実装したら通った。やったね。
真面目に正当性を考えてみる。まず条件を満たしかつ極大であること(=この状態から辺を追加できないこと)はアルゴリズムの定義からよい(入れなかった辺について、それを今のグラフに追加して連結成分での辺の最大ならそもそも判定してるし、最大でないなら他のやつからプールから入ってる)。また2つの条件を満たすグラフについて、その辺集合を合併しても条件を満たす(連結成分がでかくなるとより頂点の重さの和が増えるだけ)、よって極大が最大となる。これでいいかな。
解説もほぼ同方針で、プールして足すのではなく、後から足しているみたい。ただ降順でみていくときの操作がかったるそうなので、今回の方法みたいにいちいちプールしておく方が書きやすいかも？(正当性が怪しく見えるけど)
これ自分で解けたら気持ちいいんだろうなぁ...やってみたいね。
アイデア
・個数カウント
文字列で文字ごとに出現回数をカウントするのをよくやるが、数列で忘れがちなので注意。
・スライド最小値
数列a_0, ... , a_{N-1}について、k個前までの最小値を求めたい。セグ木だとO(NlogN)だが、dequeを使うとO(N)でできる。
作戦としては、dequeに最小値となりうる添え字を保持するというもの。順番に添え字を追加していくが、追加するときに自分以上のものは捨てておく。最小値は先頭の添え字の時で、範囲外まで来たら捨てておく、これで出来ます。
