コンテストページ：https://yukicoder.me/contests/253

成績

f:id:ngtkana:20200229003902p:plain

75 位です。あの！？

感想

かなり冷えてしまいました。

D を長時間考えた上でわからなくてとばして E に行ったのですが、これはそこまで悪かったとは思っていません。たしかに済んでみると、実は D に粘着していたらなんて思ってしまいますが、それは当時にはわからないことです。

条件

Vim に移行したく、今回は Vim から参加をしました。それに伴い、VS Code に入っているスニペットにアクセス出来ませんから、ライブラリの仕様はすべて縛ることにしました。（頑張れば見に行けないこともないのですが、せっかくですから、縛ることにしました。）

✔A - Four Integers

ソートをして、差をチェックです。

✔B - てん vs. ほむ

左から取るものと右から取るものの境界を全探索です。まずはすべて右から取るものとして計算です。そして境界を少しずつ右にずらしていくと良いです。

ところで私は差ではなくほむさんの得点を最大化してしまいましたから、慌てて二倍をして、すべての成分をそこから引きました。神リカバリーです。（はい！？）

✔C - Point Add and Array Add

a[i] を b[i] に何回足したいのかを管理です。これを c[i] としましょう。 a[i] が更新されるまではこのように遅延して良いです。しかし、更新されてしまいそうになったら、慌てて反映をして、c[i] を戻しましょう。

具体的には、次のような操作です。

A i x（ただし、i は 1 減らしてあります。）

まずは、c[i] を取得して、b[i] に反映です。次に、c[i] を 0 に戻します。そして、a[i] に x を追加です。

B l r（ただし、l は 1 減らしてあります。）

c の l から r の範囲に 1 を足します。

ということは、c が普通の配列では対応できません。c に要求される操作は、

c[i] を取得
c[i] を 0 に変更
c[l], ..., c[r-1] に 1 ずつ加算

です。

隣接差に変換です。すると、一点取得は範囲総和、一点変更は二点変更、範囲変更も二点変更に変わります。これが出来るものといえば、セグメントツリーです。

✖D - 注文の多い順列

わかりませんでした。

許容範囲でソートをすると良さそうなのですが、どうなのでしょう。条件が片方だけならば厳しい順に決めていけばよいのですが、反対側もあるのが難しいです。挿入 DP では状態がたりなさそうです。難しいです。

✖E - Twotone

わかったつもりだったのですが、通りません。

色の変わり目を全探索です。↲ 各頂点から、各色のパスがいくつあるのかを計算です。↲ すると、相異なるものの積の和ですから、和の二乗から二乗の和を引いて 2 で割ればよいです。↲ ↲ パスの数は、その頂点の属するその色のグラフの連結成分の大きさ - 1 です。↲ 色ごとに別々のグラフを作り、座標圧縮です。↲