典型90問まとめ 001～010 - 強くなりたい

簡単な解法を自分用にメモしておこうと思います。

001 - Yokan Party（★4）

答えに単調性があるので二分探索を考えます。

答えを決め打ちしての二分探索です。具体的には答えはM以上か？ということを考えます。

仮にK回以上分割してスコアSが得られたとします。このときK回より多く分割していることからより少ない回数で分割すればS以上のスコアが達成できます。

M以上のスコアが取れるかを考える→長さがM以上になったら切断することを考える→得られるスコアはS(>=M)→切断回数がK回以上ならよりS以上(つまりM以上)のスコアが達成できる

この判定を二分探索で繰り返します。

正しいカッコ列を全列挙する問題です。

制約が小さいことに着目してbit全探索を考えます。

bit全探索を用いて条件を満たさないカッコ列を含めてリストアップし、その中から条件を満たすものだけを出力します。

正しいカッコ列であることは次の2条件と同値です。

1. '('と')'の数が等しいこと
2. 文字列の途中で')'の数が'('の数を上回らないこと

要約すると与えられるグラフは木であり、木の直径を求めよという問題である。

いったん都市1から各都市までの最短距離を求め、そこからわかった都市1から最も遠い都市を始点として再び各都市までの最短距離を求める。

すると木の直径がO(N)で求まる。

やることはすぐわかるけど実装がちょっと大変。

$\displaystyle B_{ij} = (Aのi行目の総和) + (Aのj列目の総和) - A_{ij}$

なので各行、各列の総和を前もって計算しておく。

二分探索を使って以下を満たすiを求めれば良い。

$\displaystyle A_{i-1}< B <= A_i$

dpでできそうな感じがするので遷移を考える。

$dp[i][j] = (S[0:i]で\rm{atcoder}[0:j]を作る方法が何通りあるか)$

とすると遷移はS[j] = T[i]のとき

$dp[i][j] = dp[i-1][j] + dp[i-1][j-1]$

そうでないときは

$dp[i][j] = dp[i-1][j]$

となる。

区間の総和を求めるので累積和の出番ですね。特に難しいところはないです。