2020-07-10

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

解法

$[l,r]$ が回文になる条件は、a ~ zについて、 $[l,r]$ に含まれる個数が全て偶数になる、もしくはどれか1つのみが奇数になる、のどちらかです。
a $= 0$ , b $=1$ , ..., z $=25$ とします。
先頭の文字から $i$ 番目の文字までを見て、奇数個になる文字 $c$ について、 $\sum_{c} 2^{c}$ を計算したものを $b_{i}$ とします。
$[l,r]$ が回文になる条件は、 $b_{r}$ と $b_{l-1}$ の排他的論理和を取った際に立つ2進数のbitが1個以下になる、というものに言い換えられます。

$dp[i] = i$ 文字目までで、分割できる回文の個数の最小値

を考えると、
$dp[i] = min(dp[j]) + 1 (ただしp(b_{i} \oplus b_{j}) \leq 1)$
という遷移が成り立ちます。
ここで、 $p(x)$ は $x$ を2進表記した際に立つビットの個数とします。
これだけみると $O(|S|^{2})$ になりますが、それぞれの2進表記で一番小さい値となるものをメモしておけば、27通りについて確認するだけで問題ありません(2進表記は、 $b_{i}$ が累積xorを取っているだけなので最大 $|S| + 1$ 通りです)。
あとはこれを計算し、 $dp[|S|]$ を求めればおしまいです。

感想

とても面白かったです。

2020-07-10

ARC099 E - Independence

ワーシャル-フロイド法二部グラフ

問題
 提出コード

解法

頂点 $i$ と $j$ の間に辺が張られていない場合、これらを同じ州に含めることができません。
これは全ての張られていない辺について成り立ちます。逆に、同じ州に含めることができない頂点対に辺を張ったグラフを考えると(これは与えられるグラフの補グラフです)、それぞれの連結成分が二部グラフになっている必要があることがわかります。
ということで、まず構築できる条件がわかったのでチェックします。
二部グラフ判定は、補グラフについてワーシャルフロイドを適用した後、全ての頂点のタプル $(i,j,k)$ について、 $i$ と $j$ の距離の偶奇が、 $i$ から $k$ の距離と $k$ から $j$ の距離の和の偶奇と一致しているかどうかを見ればよいです。
さて、辺の数を最小にする問題を考えます。
ある州に $x$ 個の頂点を含ませた場合、そこに存在する辺の本数は

$x(x-1)/2$

です。また、もう片方の州は $n-x$ 個の頂点が存在しているはずで、こちらも同様に辺の本数を数えることができます。
ということで、州の個数が $x$ にできるかどうかを判定し、できる個数のうち辺が最小のものを選べば答えとなります。
あとは、 $x$ 個からなる州が作成可能かどうかわかればよいです。
先ほどの補グラフに再び注目します。
ある連結成分についてみると、二部グラフの頂点のグループは一意に定まります(適当な頂点からの距離を調べ、偶奇でグループ分けすればよいです)。
ですが、どちらのグループを州に含めるか、というのはそれぞれの連結成分ごとに自由に決められます。
ということで、

$dp[i][j] = i$ 番目の連結成分までみて、 $j$ 個からなる州の集合が作成可能かどうか(bool値)

というdpが考えられます。
今見ている連結成分のグループの個数のペアが $(a,b)$ だった際、
$dp[i][j] = dp[i-1][j-a]\ OR \ dp[i-1][j-b]$
という遷移を行えばよいです。
これで、作成できる州の頂点数がわかったので、あとは最小値を計算すれば終わりになります。

感想

補グラフと二部グラフがうまく考察できたので嬉しいです。面白かったです。

2020-07-09

AGC029 D - Grid game

全探索

問題
 提出コード

解法

高橋君が動かない、という操作を選択した場合、青木君は動かない、という操作を行ってゲームを終了させればよいので、高橋君が駒を動かさない、という選択肢は存在しません。
よって、高橋君が動けなくなるように青木君がうまく動けばよいです。
駒が $i$ 列目にある際にゲームが終了すると仮定します。
青木君は、 $i-1$ 回、どこかで移動を行うことになります。
このときに青木君はどのタイミングで移動を行えばよいか？を考えます。
ゲームが終了するのは、 $(x,i)$ という障害物が存在する場合で、かつ $(p,i) (ただしp\lt x)$ に駒を動かすことができるときです。
この際に高橋君が行う操作の回数は、 $x-1$ 回です。
ということで、高橋君が行う操作の回数は、ストップする障害物の位置のみに依存し、青木君がどのような行動をとるか、には依存しません。
なので、できるだけ上の行に存在する障害物でストップさせたいので、極力はやく、 $i$ 列目に移動することが最適になります。
ということで、 $i$ 列目でストップする際は、

高橋君:常に移動する
青木君: $i$ 列目より左に居た場合、右に障害物がなければ移動する、そうでなければ移動しない

という操作が最適になります。
あとは、 $i$ 列目でストップする場合の回数を全ての列について計算すればよいです。
$i$ 列目に移動したときに何行目にいるか、というのは愚直にシミュレートすればよいです。

感想

すらすらと考察できたので、あとは実装スピードです。

2020-07-09

AGC029 C - Lexicographic constraints

二分探索

問題
 提出コード

解法

$x$ 種類以下で問題の条件を満たすような文字列たちを作成できるか？という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、ある $x$ について問題の条件を満たすかどうか、を見ながら二分探索を行えばよいです。
先頭の文字列から順に見ていったときに、次に作成する文字列は、作成できる文字列の中で辞書順最小のものを選んだ場合が一番得をします。
なので、今作成し終えた文字列の状態を見て、次に作成する辞書順最小の文字列が何か？というのがわかればよいです。
文字列をランレングス圧縮のようにして、
$i$ 文字目までが $c$ という文字になっている
という情報で書き換えます。
すると、次に作成する文字列の長さが $a_{j}$ であったとき、

$i \lt a_{j}$ であれば、辞書順最小の文字を末尾に追加
そうでなければ、すでに作成し終えている文字列の末尾のうち、 $a_{j}$ 以下でかつ $x$ 未満の文字を次の文字に置き換え、その後辞書順最小の文字で埋める

という操作をすればよいです。
上記の条件を満たすような文字が存在しなければ、作成できないということになります。

感想

初手で貪欲に走ったので反省…

2020-07-08

Typical DP Contest G - 辞書順

動的計画法(DP)

問題
 提出コード

解法

まず、

$m_{i,j} = i$ 文字目の次に $j$ という文字が現れるインデックスの最小値

を計算します。
これは、 $m_{i-1,j} = m_{i,j}(j \neq s_{i}), m_{i-1,s_{i}} = i$ という更新を行えばよいです。
さて、

$dp[i] = i$ 文字目を先頭で使った際にできる、部分文字列の種類数

というDPを考えます。
$i$ 文字目を使った際に考えられるパターンは、

$i$ 文字目の1文字のみ
$i$ 文字目の次に、 $j$ という文字を繋げる

の2つです(後者は最大26通りありますが…)。前者は明らかにトータル1通りです。
後者については、 $i$ の直後に現れる $j$ を取ってくると、 $i$ 番目の文字の次に $j$ を置いたパターンの部分文字列が網羅できます。
なので、結局
$dp[i] = 1 + \sum_{j} dp[m_{i,j}]$
という遷移になります。
では、最終的に求めたい文字列はどうなるでしょうか。
まず、先頭の文字がa,b,...zであるような部分文字列全てについて足しても $K$ にならない場合は、明らかにEelとなります。
それ以外の場合は、前から貪欲、aから順番に見ていき、総和が $K$ 以上になるならその文字を選択…という操作を繰り返します。
実装の際は、先頭にダミーの文字を入れると実装が少し楽になります。

今見ているインデックスを $id$ として、次に選ぶ文字をaから順番に見ていきます。 $dp[m_{id,j}]$ を見て、これが $K$ 以上ならば $j$ が次の文字になります。そうでなければ、 $K$ から $dp[m_{id,j}]$ を引き、次の文字をチェックしていきます。
今見ている文字が最後の場合となるパターンを $K$ から引き忘れないようにすれば、答えが求まります。

感想

最近ABCやその他の場所で、ある状態を構成し数え上げる際に重複するパターンを、貪欲にチェックする操作のみ考慮することで重複を消す、という考え方を使ってきたので、それと似たような考え方でできました。
それよりむしろ、メモリ制限が厳しかったです…空間計算量はまだまだ難しいですね

2020-07-03

AGC009 C - Division into Two

数え上げ累積和

問題
 提出コード

解法

集合 $X,Y$ を、集合0、集合1とし、 $A,B$ を $L_{0},L_{1}$ とします。

$dp[i][j] = i$ 番目の要素まで見て、 $i$ 番目の要素を集合 $j$ に入れるような振り分け方のパターン数

を数えます。
$[l,i]$ という区間が集合 $j$ に入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このような操作ができる条件は、

$S_{i+1} - S_{l-1} \geq L_{1-j}$
$S_{k+1}-S_{k} \geq L_{j} (l \leq k \lt i)$

の二つを満たすことです。
逆に、これらの条件を満たす $l$ について、 $[l,i]$ を集合 $j$ に入れる、という操作ができるので、
$dp[i][j] = \sum_{l} dp[l-1][1-j]$
という遷移が考えられます。
1つめの条件は、それぞれの $i$ について二分探索を用いて計算ができます。
$S_{i + 1} - L_{1-j} \lt S_{k}$ となるような $k$ を二分探索で求めます。すると、 $l$ として選べるのは $k-1$ 以下です。