AtCoder ABC 147 - こんちゅう

解けなかった問題の簡単な説明を覚書程度に記す。

ABC147E

atcoder.jp

DP。まず $|A_{ij}-B_{ij}|$ を計算する。

dp[i][j][k]:i,jマスまで行ったとき偏りkを実現できるかどうか

とすると， $|A_{ij}-B_{ij}|$ の最大値をMとして $O(HWM(H+W))$ くらいで解ける。

kは別に80までで十分なんじゃないか？と思ったこともあるけれど反例がある。例えば今の偏りが60で，マスが40,50,50と続いたとき，60+40-50-50をしないと0にはならない。

ABC147F

atcoder.jp

難しくない？解説見ても数日実装できなかった。

$D=0$ は別処理。 $D>0$ として一般性を失わない。 $S+T$ の値は固定なので結局 $S$ の値としてどれだけあるかを数えればいい。
高橋君がK個取るとする。するとSとして取りうる値はKX+(0+1+...+K-1)D～KX+(N-k+N-k+1,...,N-1)Dとなる。

じゃあこれでKを固定した時の値が $O(K)$ で出せたからあとはKを0~Nまで動かせば完成だ！...と思ったら，これだと $O(N^2)$ かかってしまう。しかしKを変えたときの値が重複する可能性もあるのでKに対する単純な直和ではない。
制約からどうやら $O(NlogN)$ くらいで解かないといけないらしい。こっからが辛かった。

KX mod Dで場合分けをすると, KX mod Dが異なる列は絶対にカブらない。例えばD=2,X=1,N=5として,
K=3のとき 3+(0+1+2)*2~3+(2+3+4)*2
K=4のとき 4+(0+1+2+3)*2~4+(1+2+3+4)*2
について，K=3と4で被っている値はない。(3 mod 2 != 4 mod 2より)

KX mod Dで場合分けを実行する。例えばKX mod D = aとなったKたちに対して，それらの数列の和集合が答えになる。
例えば上の例でK=2のとき2+(0+1)*2~2+(3+4)*2なので，K=4のときの数列と重複が存在する。これはイベントソートにより効率的に計算できる。たとえば交差が1の数列たちを考えて，それらの初項と末項が $a_1,a_n,b_1,b_n$ とすると,

vector<pair<ll,ll>> timetable;
timetable.push_back(make_pair(a_1,1));
timetable.push_back(make_pair(a_n,-1));
timetable.push_back(make_pair(b_1,1));
timetable.push_back(make_pair(b_n,-1));

として,timetableを1項目でソートした上で一つずつ取り出し，

for(auto& t : timetable) {
     if(res > 0) ans += t.first - before;
     before = t.first;
     res += t.second;
}

とでもすればいい。一つ一つにばらすと典型テクニックらしいんだよなあ。