A. String Similarity

s の長さが 2n - 1 であるので、s は連続部分列として長さ n で全ての要素が 0 であるようなものと長さ n で全ての要素が 1 であるようなものの両方を持つことはありません。そのため、全て 0 の文字列か全て 1 の文字列のどちらかが答えになります。これに気づかずに s の部分文字列を全列挙し、貪欲に答えを構成していきました。通ったから良かったものの、正当性は何も証明していません。反省。

B. RPG Protagonist

B なのに難しくて焦りました (こんなのばっか)。
$$ sx + wy \le p $$ $$ sa + wb \le f $$ $$ x + a \le cnt_s $$ $$ y + b \le cnt_w $$ を満たすような (x,y,a,b) のうち、x+y+a+b が最大になるものを求めます。こういうのは一つ固定して考えると良いので x を固定してみます。すると、$ y = min( \frac{p - sx}{w}, cnt_w) $ となります (徐算は切り捨て)。(a, b) は、 $$ sa + wb \le f $$ $$ a \le cnt_s - x$$ $$ b \le cnt_w - y $$ を満たすもののうち、a + b が最大になるものを見つければ良いです。実は、a < b とすると、a を取りうる最大の値にして、残りを b に割り振るのが最適です。全然気づかなかったので反省。

C. Binary String Reconstruction

B でめちゃくちゃ詰まってしまったので、取り掛かる頃には 4000 人くらいが通しており、簡単だろうと思いながら解きました。 s から w を構築するために、条件を言い換えると、$s _ i$ = 0 のときは、$w _ {i-x} = 0$ かつ $w _ {i+x} = 0$ となります。これで指定されない w の要素については全て 1 として良いです。こうして構築した w から s を再構築してみて、s ができなければ -1、できたら w をそのまま出力します。

D. Zigzags

これすき。何かを固定してみて Zero Sum Rangesをする、が見えます。私は i と k を固定してみました！どうして？ b[x] := a[i+1] ~ a[k+1] に出現する x の数、c[x] := a[k+1] ~ a[n] に出現する x の数、とすると、a[i] = a[k] となる全ての (i, k) で、全ての x について b[x] * c[x] を足し合わせたものが答えになります。これは愚直にやっては間に合いません。i と k を動かしたときに、b, c がどのように変化するかを考えてみます。i は固定し、k を k+1 に変化させたとすると b[a[k]] が 1 増え、c[a[k+1]] が 1 減ることがわかります。このとき、b[x]c[x] を足し合わせたものは、b[a[k+1]] 減り、c[a[k]] だけ増えることがわかります。なので、b, c, b[x]c[x] を足し合わせたもの、を管理しながら、i, k を動かしていき、a[i] = a[k] のときはb[x]*c[x] を足し合わせたもの、を答えに足していくことで答えが求められます。b, c を連想配列で管理すると TLE してしまいました。Codeforces はシビアですね。log は定数じゃない！

E. Clear the Multiset

これもすき。解けなかったので解説 AC しました。DP[i][j] := 整数 1 ~ i は全て削除し、整数 i のうち j ( $\le$ a[i] ) 個は操作 1 で消しているという状態になるまでの最小操作数、とします。また、この状態を (i, j) とします。(i, j) から、i+1 を削除することを考えます。a[i+1] $\le$ j のときは、i に適用した操作 1 を横に拡張して i+1 を削除することができ、操作数は増えないので、chmin(DP[i+1][a[i+1]], DP[i][j]) と遷移できます。この際、a[i+1] を超える数を操作 1 で消すことはできないので注意。a[i+1] > j のときは、i に適用した操作 1 を横に拡張するだけでは i+1 を消しきれないので、残りをさらに操作 1 で消していくか、操作 2 で一気に消すかの 2 通りの遷移があります。まず、操作 2 を行う場合操作回数が 1 増えて i+1 を全て消すので、chmin(DP[i+1][j], DP[i][j] + 1) となります。この際、a[i+1]個のうち j 個は操作 1 で消したことにした方が得なので、そうしておきます。次に、残りを操作 1 で消すことにする場合、整数 i のうち j+1 個を操作 1 で消しているという状態に遷移すればいいことがわかるので、chmin(DP[i][j+1], DP[i][j] + 1) とできます。これで、遷移は全てですが、i $ \le$ n, j $\le a[i] _ {max} $ なので状態数が、5000*10$^9$ となり到底間に合いません。ここで、j をそんなに多くとる必要があるかを考えてみます。全ての整数を操作 2 で消すことが必ず可能であり、その際の操作数は n になるので、操作数の上限は n とすることができます。すると、j > n の状態はそこから最小の操作数に遷移することは無いことがわかるので、j > n の状態についてはみる必要が無いことがわかります。これで、状態数を n$^2$ に抑えることができました。

感想

かなり酷かったです。A でギャグに気づかず、B でめちゃくちゃ詰まってしまいました。反省だらけです。

現代の量子力学

主に精進の様子を記録する日記帳です

Educational Codeforces Round 94 (Rated for Div. 2)

A. String Similarity

B. RPG Protagonist

C. Binary String Reconstruction

D. Zigzags

E. Clear the Multiset

感想