Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

a,b,a^bの順になります

やるだけ

問題：整数列Aから連続する部分列を削除して、残ったものがdistinctになるようにせよ

削除する部分列の長さを最小にせよ

考察：

左からと右からを考えます。

左からL個残したとき、右側をどこまで残せるかはO(N)でわかります。

したがってO(N^2)で解けます

完全な典型なので、素早く解きたいところでした。12分なのでちょっと遅め

問題：0~n*n-1をn*nのグリッドに置く。各行各列のXORが等しくなるようにせよ。ただしnは4の倍数である

考察：

4の倍数なので4*4ずつ配置するとよさそうです。

順番においてうまくいきます。

全てに16足したとき16以上のｂｉｔは等しく、4個並ぶと0になるので必ずＸＯＲが等しくなります。

2*2セットでできるらしいです。

苦手なタイプの問題ですが、14分で解けたのは割とよかったと思います。

問題：ｎ個の順列がある。左側にあって、aiより小さい値の和siが与えられる。復元せよ。

考察：

まず一番後ろが簡単に求まります

x(x-1)/2=s[n-1]を解けばよいです。

次にa[n-2]をｍと仮定したとき、整合性があるかはO(1)で求まります。

mより小さい値を足したとき、m(m-1)/2になればよいです。

もしmに関する項をまとめるとm(m-1)/2+xi+xi+1...となります。

これはmを大きくすると単調に非減少です。

したがって二分探索によってmが定まります。mより小さく既に出た値の和はSegmentTreeで求まります。

以上でO(Nlog^2N)で解くことができました。

問題：ｗ列あり、各列ｎ行の和を取る。ある行は長さｌのベクトルでできており、端がはみ出さなければずらしてよい。値がない部分は0とする。各列で、和の最大値を求めよ

考察：

ｗ＝ｌならそのまま足す。

もしｌが十分小さければ、真ん中には行の最大値を足せばよいので、簡単に求まりそうです。

そうでないときは、尺取りや、SegmentTreeを使いO(WlogL)でそれぞれの列の最大値が求まります。

2番目の真ん中の部分を考えましょう。これはimos法で解くことができます。

[l,w-l)に最大値を足すので、1次元上をimos法で進めればO(W)で求まります。

以上からO(LlogL)で解くことができました。

反省：

基本的な考え方は80分くらいにはできていました。ちょっと遅いけど、Dで詰まった分を考えれば許容範囲かなと思います。

ただ1次元上のimos法が定着しておらず、イベント処理みたいな形式にしてバグっていました。

イベント処理形式って使うんですかね。座圧＋imosで十分そうに見えました。次からは抜けないように通したいです。