Codeforces Round #553 (Div. 2)

バチャ

読解しづらくて9分でした。渋み

連続する4つなので全探索すればよいです

問題：行列の各行から1つ整数を選ぶ。XORを取って0にならないような選び方があるか調べよ

考察：

2種類の整数が含まれる行があるとき、必ず構築可能です。

なぜならその行以外から適当に選んだ時、どちらかは0より大きくなります

また、すべてで1種類しかないときは、適当に選んで0かどうか見ればよいです。

問題：偶数と奇数がいい感じに並んでいる。l番目からr番目の和を求めよ

考察：

まず１からｒ番目の和から、１からｌ－１番目の和を引くことを考えます

１からｘ番目の和がうまく求まれば解くことができます。

まえから2^(k-1)個ずつ並んでいて、kが奇数のときは奇数の列、偶数のときは偶数の列で構成されています。

完全に含まれる群数列がどこまでか、偶数奇数どちらかがO(logｘ)でわかります。

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

問題：ｎ個のpairがある。これを適当な順で並べたとき、ai*(i-1)+bi*(n-i)のコストがかかる。コストの和を最小化せよ

考察：

b-aの小さい順に並べればよいです。

b=aのとき、n*aのコストがかかります。

差があるとき、aが小さいときは右側に、bが小さいときは左側にあるとうれしいのでこのようにすれば最適です。

もし上のように並べた後、どこを変えてもコストは増えます。

ai,bi,aj,bj(bi-ai<bj-aj , i<j)とします。

はじめのコストは

ai*(i-1)+bi*(n-i) + aj*(j-1)+bj*(n-j)

swapしたときのコストは

aj*(i-1)+bj*(n-i) + ai*(j-1)+bi*(n-j)

辺々引くと

(ai-aj)*(i-1) + (ai-aj)*(1-j) + (bi-bj)*(n-i) + (bi-bj)*(j-n)

= (aj-ai)*(j-i) + (bi-bj)*(j-i)

= *1*(j-i)　<0

以上からコストが増えることがわかりました。

O(NlogN)で解くことができました。

問題：整数列Aから[l,r]の頂点だけ残す。連続する部分列いくつになるかをf(l,r)としたとき、l=1~n,r=l~nで和を取れ。

解説：

まず、連続する部分列の個数とは何かを考えます。

1つ前が選ばれていなくて、今見ているところが選ばれていると、求めるべき値が+1されます。

したがってすべての隣接要素で、+1になる場合の数を見ればよいです。

感想：

Eは典型っぽかったのですが、ｌ、ｒから考えて詰まったしまいました。

Removing Blocksみたいに、どこをどうすると全体の値に影響するかに分割して考えるのは典型でした。

ある1つの要素をみたとき、その要素が連続部分列の先頭や最終になるときでした。

これは解けるようになりたいです。

*1:bi-ai) - (bj-aj