Codeforces 496
時間内にE2が解けなかったけど、E1/E2みたいな問題がとても好み。
A. Tanya and Stairways
連続している数列のうち、単調増加列の末尾を取り出す。
計算量:$O(N)$
Submission
B. Delete from the Left
比較回数は短い方に合わせれば良いので、文字列の末尾から比較を行う。
計算量:$O(min(|S|,|T|))$
Submission
C. Summarize to the Power of Two
合わせて$2^k$の形になればこれを答えから取り除くことができるので、$2^k = a[i] + a[j]$となる$i,j$を探す。
kは1~31で十分なので、各要素を31回見るようにして自分のペアを見つければ良い。
計算量:$O(log(INT_{MAX})*N)$
Submission
D. Polycarp and Div 3
最後までどうすればよいのかわからない気がするので、dpで解いた。(dpでなくても良かった)
数字の桁の和が3であるときに区切りを入れる。そうでない場合はここで新たに区切りを置くか、別の数字をつなげる選択ができる。
$dp(i,j):=i$桁目まで見たときに、どこかから連続している整数の桁の和が$j$になるときの、3の倍数の整数の個数の最大値
としてdpをすれば良い。
計算量:$O(|S|)$
Submission
E1. Median on Segments (Permutations Edition)
数列中に$M$が一つしか無いので、$M$を起点にしてこの左右の区間幅をいくつ決めることができるかという問題になる。
$M$より大きい/小さいという情報について累積和を持てば、まず$O(N^2)$で計算することができる。
片側をmapに乗せておけば、シュミレーションっぽくsum[R]-sum[L]=1,0を列挙ができるので時間内に解ける。
計算量:$O(NlogN)$
Submission
E2. Median on Segments (General Case Edition)
$M$がたくさんあるので先の解法では重複したり計算量が大きくなってしまう。
中央値が$M$以上であるものは、選んだ連続する数列について過半数が$M$以上であると言いかえることができる。
これは$BIT$で簡単に求めることができる(最近良く見る)。
これを求める関数を$f(M)$としたとき、$f(M)-f(M+1)$としたものが答え。
計算量:$O(NlogN)$
Submission
F. Berland and the Shortest Paths
まず最短路DAGを作る。
その後は$N-1$本の辺を決めれば良いことになる。
根を0としているので、最短路DAGの辺を根方向に張ればちょう$どN-1$本決めることができる。
$K*M<10^6$なので適当に全列挙できる。
計算量:$O(KM)$
Submission