2018-03-29

CF 822 E - Liar

問題

問題概要

長さ $n$ の文字列 $s$ と長さ $m$ の文字列 $t$ が与えられる。 $s$ をいくつかの部分文字列に分解して、その中から任意の個数を選んで順序を崩さないように結合させる。その結合させた文字列を $t$ と一致させるために、できるだけ結合の数減らしたい。 $x$ 個以下の文字列で実現できるかを判定せよ。

$1 \le m \le n \le 10^5$
$s,t$ はアルファベット小文字
$1 \le x \le 30$

アイデア

計算量をとりあえず気にしないのであれば、とりあえずdp[i][j] = sのi文字目まで使った、tのj文字目まで使った状況での分割回数のminを持つとdp[n][m]<=xかどうかで判定ができるが、明らかに間に合わない。

ここで、分割回数の上限 $x$ が小さいことに着目すると、次のようなdpも考えられる：dp[i][j] := sのi文字目まで使った、既に連結した文字列がj個の時、tの何文字目までを作れるかのmax。このようにすると状態数は $n * x$ になる。そして、遷移がどうなるのかというのを考えると、1,2,3, ... 文字を採用するというのを全部試すというのは結局ムリだが、i文字目からスタートする部分文字列を採用する時場合は、最適なのは取れる限りまで取る(中途半端に切るのは無駄)ということしか考える必要がないので、各状態において遷移は「i文字目からスタートするものを採用する/しない」の2つしかいらないことになる。

sのi文字目からと、tのdp[i][j]文字目からのLCPはSuffixArrayにsとtを結合させたものを入れておいて、RMQを使うことで高速に処理することが出来るので、DPの遷移は $O((n+m)xlog(n+m)$ になる。

実装(C++)

2018-03-22

CF 940 F - Machine Learning

問題

Problem - F - Codeforces

問題概要

長さ $n$ の数列 $a$ がある。次のようなクエリを考える：

クエリ 1 $(l,r)$ : 区間 $[ l, r ]$ について、数字 $i$ が現れる回数を $c_i$ として、集合 ${c_0 , c_1 , \ldots , c_{10^9} }$ のmexを答える。
クエリ 2 $(p,x)$ : $a_p$ の値を $x$ に変更する。

以上のクエリが合計で $q$ 個与えられるので、順に処理せよ。

$1 \le n,q \le 100000$
$1 \le a_i \le 10^9$
$1 \le l \le r \le n$
$1 \le p \le n$
$1 \le x \le 10^9$

アイデア

愚直な処理はTLEしてしまう(submission)。

まず、クエリ1で出力すべき値がそこまで大きくない。なぜなら、xを答えにさせるには、最低限の現れる回数をを考えると $1,2, \ldots , x-1$ 回現れる数字がそれぞれあるということなにで、答えは $O(\sqrt{n})$ で抑えられている。

そこで、もし変更がなければMoが出来るなーと思いが巡った(その数字が現れる回数を配列 $ct$ に、現れる回数の個数を配列 $sz$ で管理することにすると、区間を1伸ばしたり縮めたりするのは $O(1)$ で出来、クエリに対しては上の考察から $O(\sqrt{n})$ で答えられる)。

今回は、2種類のクエリが来ると考えるのではなく、クエリ1しか来ないと考えて、クエリ1を次のように3つの数で与えられるクエリということにする：

クエリ $(t,l,r)$ : 既にクエリ2を $t$ 個実行した状態で、区間 $[ l, r ]$ について、数字の出現頻度のmexを答える。

クエリをこの形に言い換えると、状態としてこの3変数を持ち、いずれかの変数を+1,-1したときに $ct,sz$ がどうなるかの更新は $O(1)$ で行うことが可能である。この事実を踏まえて、 $t$ と $l$ に関してはブロックサイズ $S$ ごとに組にして分けることにする。このとき、クエリ毎に $t,l$ は $O(S)$ だけ変化するので、全体として $O(qS)$ 、 $r$ は $\frac{n}{S}$ 回だけ $O(n)$ の変化するので、全体として $O(\frac{n^2}{S})$ の変化をする。 $q$ と $n$ のオーダーが等しいことも考慮すると、ブロックサイズ $S$ として適切なのは $S = n^{\frac{2}{3}}$ であり、このとき全体は $O(n^{\frac{5}{3}})$ となる。