Educational Codeforces Round 69 (Rated for Div. 2)
神のいたずらか、悪魔の罠か。
出たから振り返るお
A - DIY Wooden Ladder
問題：長さaiの木の棒がN本与えられる。長さk+1以上の棒2本を縦に置いたとき、長さ1以上の棒がk本置ける。kを最大化せよ。
感想：
・これ、縦棒何組作ってもいいと思わん？そう呼んで1:32+3でした。ウケる。
考察：
・大きい方から2本取ったときの小さい方をkとする
答えはmin(k-1,n-2)。
横で置ける数がn-2本なことに注意する。
B - Pillars
問題：柱がn本ある。大きさaiの円盤が柱iに置いてある。以下のルールに従って動かすとき、1つにまとめられるか。
１：移動させるときは隣にしか移動できない
２：pillar i contains exactly one disk
３：移動先は空か、移動させる円盤より大きいものがないといけない
ただし円盤の大きさは1からnで重複がないとする
感想：
ルール2、移動前の柱には1つしか円盤がない状態が求められてるんですね…。普通にハノイの塔かと思ってめっちゃ考えちゃいました。
考察：
・はじめの状態で大きさnの円盤は動かせないし、他の円盤を動かすと二度と動かせないことがわかる。
・なので、大きさn-1の円盤は、大きさnの円盤と隣り合っていないといけない
・また大きさk+1までの円盤をnの上に重ねたとして、大きさkの円盤を動かすことを考える。このときkの円盤とk+1まで重ねた円盤の間に、大きさk未満の円盤が残っていたらダメ。
・したがって、大きさnの円盤がある柱から見て、外側が小さいような、山型の推移になっていればよい。
C - Array Splitting
問題：ソートされたn要素の整数列Aが与えられる。この列Aを、k個の連続する部分列に分割する。各部分列についてmax-minを計算し、k個足し合わせる。この和を最小化せよ。
考察：
・式のシグマを分けてみる。
a[x1]-a[0]+a[x2]-a[x1+1]+...+a[xk]-a[xk-1+1]みたくなる
i個目の部分列の範囲が[xi-1+1,xi]で、xk=n-1とする
・変形して
a[n-1]-a[x0]-Σ(i=1~k-1)(a[xi+1]-a[xi])
となる。隣り合う要素の差がn-1通りあり、そこからk-1個選んでa[n-1]-a[0]から引いたものが求める和。
この和を最小化するには、k-1個選ぶところを最大化する。
・隣り合う要素n-1個を全列挙して、大きい順にk-1個取る。
・a[n-1]-a[0]から引いたら答えになる
D - Yet Another Subarray Problem
問題：n要素の整数列Aが与えられる。正の整数m、kが与えられたとき、連続する部分列[l,r]のコストは以下の式で与えられる。
Σ(i=l~r)(ai-k**1
コストを最大化せよ
これコスト最大化にすごい違和感感じませんか？
価値最大化とか、利得最大化が普通じゃないかなって思っちゃいましたね。英語に弱いだけでcostの別のとらえ方があるかもしれません。知らんけど
考察：
・開始のindexによってどこでマイナスの項の値が変化するかが決まる
・より具体的に言うと
m=2で
長さが0は0、長さが1，2はk、3，4は2*k…
0からスタートすれば、0で-k、2で-kみたいな感じで順次更新できる。
・このルールに従えば累積和を使って開始indexについてO(N)で求まる。
いまの累積和 - 今まで出てきた累積和の最小値
これが、いまのindexを終点とするときの最大値を表す
・したがって最小値を記録しながら累積和を取る
・開始indexがm以上のときは1のときと同じ結果になるのでO(NM)で求まる。m<=10より十分高速
E - Culture Code
問題：
マトリョーシカには、内側の大きさと、外側の大きさがある。iをjにかぶせられるとは、jの外側の大きさ＜=iの内側の大きさのときである。（1つ上の内側の大きさー外側の大きさ） は隙間になっている。
マトリョーシカがN個与えられて、かぶせたときに全ての隙間を足したものを最小化したい。
ただし一番外側のマトリョーシカに、別のマトリョーシカを重ねられるときは、重ねなければならない。
最小化した隙間が、何通りのマトリョーシカの組で構成可能か求めよ。
考察：
・なんもわからん。
解説：
直訳
初めに、マトリョーシカを内側の大きさ昇順でソートする
DPを使う。d[i]=(x,y)：隙間の和の最小値ｘとそうなるときのsubsequences y。すべての組の間で
d[i]は隙間の和を暫定的に最小にするｘと、それを実現するｙ。
2つのメインケースがある。
もしout[i]<=in[j]なるjがないとする。そのときマトリョーシカiの中には何かある。d[i]=(in[i],1)
つまり一番外側のときの暫定隙間はin[i]である
マトリョーシカiをマトリョーシカjの中に入れるとする。そのときの暫定隙間はd[j].F-(out[i]-in[i])となる。
遷移は
d[i].F=min(out[i]<=in[j]) { d[j].F } - (out[i] - in[i])
・セグ木で高速化してO(NlogN)でいける
ここからは解説の考察(←？？？)
・外側から決めていく感じ？
・d[i]を決めるときに、必要な要素は、out[i]よりin[j]が大きいjのDPの値
・なのでinが大きい順に決めていけば良さそう
・sort by increasingって昇順じゃなくて降順なのかな。うーん
・out[i]<=in[j]である必要があるけど
in[i]<out[i]<=in[j]だから、inが大きい方から調べれば大丈夫そう。
・セグ木は長さNで持って、d[i]のxをいれて最小値を求める
・out[i]<=in[j]の範囲でのd[j]の最小値をセグ木で求める
・jのindexは、inだけのリスト持っておいて二分探索でわかる。
・mapかなんかで、d[i]のyごとに足しておく
・最小値d[j]が何通りあるかをmapから持ってきてd[i]のyとしてmapを更新する。
・d[i]のxはd[j].F-(out[i]-in[i])なので、セグ木をupdateしておく
※通したので追記
かなり遠回りな実装をしていると思います。ご了承ください。
まずin降順に調べていきます。
マトリョシカiを一番内側にしたときの、隙間最小値、それを実現する組み合わせをDPで持ちます。
遷移は、out[i]<=in[j]となるjの範囲で、
dp[i]=min(dp[j]) - (out[i]-in[i])
dp[i]=sum(dp[k]) ( k : dp[k]=min(dp[j])
最小値からマトリョシカiの厚さを引いたもの、それを実現する組み合わせの合計となります。
まずどのようなデータ構造を持つかですが、
1．i番目のマトリョシカが一番内側のとき、隙間合計の最小値がいくつか
2．i番目のマトリョシカが一番内側のとき、隙間を最小にする組み合わせの総数
3．ｘ以上の内側で(外側ｘのマトリョシカが入る中で）、上の１の最小値
4．内側ｘ以上で、3で求めた最小値を実現する組み合わせの総数
この4つになります
まず１ですが、普通の配列で良いと思います。なんなら３と一緒に記録できるので要らないです。そこまで手間でもないし見やすさ上がるので自分はvectorで作りました。
DP[i]とします。
2はこの問題のキモとなる部分です。これが答えに繋がります。４を考慮したいので４で詳しく書きます
３はおなじみのセグ木を使いました。
４が問題です。ある範囲かつ、ある値を持つ第二要素の合計って感じです。
はじめDP[i]の値ごとに累積和を考えました。しかし、累積和更新前の値が求められることがあります。
例えば、1 8、 7 9、8 11、10 13みたいなマトリョシカがあるとします
(1，8)を調べるとき、隙間最小になっているのは、(8,11)、(7,9)(10,13)の2通りです。
しかし、実現できるのは前者のみです。
したがって累積和ではうまくいかないことがわかります。
indexごとに累積和を記憶しておくことを考えました。
DP[i]：番号iのマトリョシカが最内側のときの最小隙間
Sum[i]：番号iまでで値がDP[i]になる組み合わせの累積和
Sum[i]は最内側がiでなくてもよいです
map<int,vector<int>> idx_save：DP[i]＝xとなるときのiのリスト
この最小値ｘで番号ｊ以上の累積和が欲しいときは、idx_save[x]をｊで二分探索して、idx_save[x]の中でj以上の最小値idx_xを求めます。Sum[idx_x]が欲しい値となります
Sum[i]=(Sum[直前にDP[i]となったところ] + Sum[idx_x])%mod;
となります。直前にDP[i]となったところはidx_save[dp[i]]の最後の値を見ます
out[i]<=in[j]となるjを求める(二分探索)、その範囲でDP[j]の最小値を求める(セグ木)、idx_xを求める(二分探索)、などの操作はO(logN)なので、全体でO(NlogN)で解くことができました。
全体の感想：
誤読辛すぎる。。。
ICPCルールっていうんでしたっけ。
完数で順位を付けて同じなら、それぞれの提出時間の合計＋ペナルティ*10分の小さい順とするってやつ
これ、前半詰まったら完全に取り返しつかないですよね。しんどい。
まあ最後の最後で4完して、3完内1位の1つ上になれたので良かったです
レートは1661→1704の+43でした。まずは水落ちしなくてよかった…
1900はまだまだだと感じますね。たぶんAB成功してもそんなに伸びなかったんじゃないかな。
気長に頑張っていこうと思います。
ていうか青の下、濃緑で、水色ではなくないか？コドフォの色分けが日本人にわかりづらすぎる。
*1:r-l+1)/mの切り上げ
