コンテストページ
Dashboard - Educational Codeforces Round 80 (Rated for Div. 2) - Codeforces
解法
✔A - Deadline
条件は、d <= (x - n) * (1 - x) と書けて、右辺を x に関する二次関数と思うと、最小値がわかります。
✔B - Yet Another Meme Problem
条件は、B が 99999... の形であることと同値です。
✔C - Two Arrays
cat(A, reverse(B)) が弱単調増加であることと同値なので、隣接差を考えると二項係数になります。
✔D - Minimax Problem
数列 b は、数列 a[i] と a[j] の項ごとの max であるとありますが、こちらは最大化する問題ですから、好きに選んで良いとしてよいです。 そこで、a[i] の方で使う添字の集合を全探索です。
✔E - Messenger Simulator
時刻をキーとして、その時刻に受け取ったメッセージがその送信者にとって最新であるときに bit が立っている状態のものを考えましょう。すると、新しくメッセージを受信するたびに、その人が履歴のどれだけ深いところにいるのかが、前回受け取ってから今までの時刻でいくつ bit が立っているかでわかります。これは、セグメント木で処理可能なクエリです。また、各人最後のメッセージがいつであったかは配列で管理しておきましょう。
すると答えになりうるのは、初め、受信直前、受信直後、最後ですから、これらのタイミングで答えを更新していきましょう。
✖F - Red-Blue Graph
考えたこと
次のようにフローに対応させると、湧き出し・吸い込みの条件付きの最小費用循環流問題になります。
赤
- 上側の赤い頂点は 1 以上の湧き出しです。
- 下側の赤い頂点は 1 以上の吸い込みです。
- 辺を赤く塗るのは、下向きに 1 のフローを流すことです。
- 下向きの辺は容量が 1、コストが r です。
青
- 上側の青い頂点は 1 以上の吸い込みです。
- 下側の青い頂点は 1 以上の湧き出しです。
- 辺を青く塗るのは、上向きに 1 のフローを流すことです。
- 上向きの辺は容量が 1、コストが b です。
白い辺
- 白い頂点は太っ腹なので、いくら湧き出しても吸い込んでも起こりません。
さらに、ソース s とシンク t を用意して、次のように変換すると、湧き出しと吸い込みのない、最小流量付き最小費用流になります。
- s から湧き出し頂点に、最小流量 1 の無料辺を張ります。
- 吸い込み頂点から t に、最小流量 1 の無料辺を張ります
- 白い頂点に関しては、s からと t へと、両方とも容量無限の無料辺を張ります。
さらに、最小流量付きの辺は、頂点を倍加することで制約なしの問題に帰着できます。
- 湧き出し頂点 x について、それを倍加して x' を爆誕させて、容量無限の無料辺 s -> x -> x' を張りさらに x->x', x->t に容量 1 の無料辺を張ります。
- 吸い込み頂点 y について、それを倍加して y' を爆誕させて、容量無限の無料辺 y' -> y -> t を張りさらに y'->y, s->y に容量 1 の無料辺を張ります。
最小費用流は、増分路のうちコストが最小なものを Bellman -- Ford のアルゴリズムで探して、そこにできるだけ流すを繰り返すとよいです。
ダメだったこと
これは、どうなのでしょうという気持ちはありつつ、よくわからないので見てみぬふりをしていたのですが、そうです。フローを流す順番は操作できます。こちらのブログが参考になります。これをすると通るはずですから、後日実装をしてみましょう。
結果
77 位です。良い方なのではないでしょうか。
