ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AGC032 D - Rotation Sort

動的計画法(DP)

問題
提出コード

解法

シフトという操作が少しわかりづらいのですが、結局は

  • 任意の要素を取り出し、別の任意の位置に挿入する(現時点より左に挿入するならコストはB、右であればA)

という操作ができることになります。
ので、それぞれの要素を、 右側に移動してそろえる、左側に移動してそろえる、操作しない、の3パターンに割り振ればよいです。
右側に操作するか左側に操作するか、というのは、今作成中の順列で操作しなかった要素の右端を見ればよいです。

dp[i][j] = i番目の要素まで並べた上で、操作しなかった要素の右端がjであるようなもののなかで可能な最小コスト

とします。
dp[i][j] = \left\{\begin{array}{} dp[i][j] + B \ (a_{i} \lt j)\\ min(dp[i][k])(ただし k \lt j) \ (a_{i} = j) \\ dp[i][j] + A \ (a_{i} \gt j) \\ \end{array}\right.

という遷移を行えばよいです。
dp[0][0] = 0が初期値、min(dp[n][j])が答えです。

AGC043 D - Merge Triplets

数え上げ

問題
提出コード

解法

いろいろな数列を試していると、4つ以上の連続する区間が単調減少することはありません。
この原因を考えてみると、長さ3の数列A_{i}を作成しているため、4つ単調減少させようとすると、1つの長さ3の数列 + どこか1か所別の値が選ばれる必要があります。
長さ3の数列の先頭と、のこりの1つの要素のどちらが小さい場合でも、これらを単調減少させつつPの末尾に追加することは不可能です。
単調減少の先頭に注目、というのを少し拡大し、Pの完成形としてありうる数列に対し、

  • 今までの要素の最大値が出てきたときに、その最大値と、その前の要素で区切る

という操作を繰り返すと、長さ3以下のブロックのようなものがたくさん出来上がります。これらのブロックを組み合わせて、その順番でPに追加できるようなA_{i}が作成できれば、答えにカウントできます。
これまたいろいろ手元で試すと、

  • 長さ3のブロックの個数 + 長さ2のブロックの個数がN以下

であれば、A_{i}が作成可能であることがわかります。
長さ3はそのままA_{i}にすればよく、長さ2のブロックに対しては、適当に長さ1のブロックと組み合わせ、それぞれの先頭の要素の小さい方をA_{i}の先頭にすればよいです。残った長さ1のブロックは、適当に昇順に並べます。
これにより、長さ3以下のブロック集合の作成方法が、そのまま答えになることがわかりました。
長さ2のブロックは、先頭 > 末尾となっていればよいです。
長さ3のブロックは、A \lt B \lt Cに対し、CAB,CBAの2通りが考えられます。
長さ3のブロックをi個作成する、とした時、
\frac{\prod_{j = 0}^{i-1} \left(_{n-3j}C_{3} \times 2 \right) }{i!}
通りの組み合わせが考えられます。
そして、残った数の中から長さ2のブロックをk個作成する時、
\frac{\prod_{j = 0}^{k-1}\ _{\left(n-3i - 2j\right)}C_{2} }{j!}
通りの組み合わせが考えられるので、これを全ての(i,j)のペアについて考えればよいです。

感想

昔解けなかった数え上げシリーズが解けていくのは楽しいです！(前も言った気がします)

ARC082 F - Sandglass

問題
提出コード

解法

クエリが時間順で並んでいるので、時刻を進めながらクエリに答えていくことを目指します。
時刻tのクエリに答えるには、r_{i} \lt tとなるようなr_{i}の中で最大の時刻まで時を進めて砂の量を調べ、最後にひっくり返す部分だけシミュレートすれば良いです。
よって、それぞれのr_{i}にて、最初の砂の量がaであった場合にどうなっているか、がわかればよいことになります。
また、砂の量をaで始めたにも関わらず途中で砂時計の上部の砂が空になり、全て下部にたまった場合、砂の量は始め0(X)であった場合と同一視できます。
このような状態になるaは、区間になっているので、その境界を見つけることができればよいです。
途中で空にならなかった場合は、砂時計をシミュレートしていった場合の増減を累積和で記録しておくことで、ある時刻r_{i}における砂の量がわかります。
よって、あとは0,Xと同一視できる区間の境界が求まればよいことがわかりました。
まず明らかにr_{i} - r_{i-1} \geqq Xの場合、任意のaが初めから0もしくはXであったとわかります。
そうでない場合も、増減の累積和を確認し、ある時刻に0(X)になるaの区間をマージしていくことで、高速に求めることができます。

感想

おおまかな方針はたっていたのですが、細かい部分を詰めるのに結構時間がかかりました。実装もあんまり綺麗ではない？気がするのでもう少しどうにかしたいです。

Typical DP Contest I - イウィ

動的計画法(DP)

問題
提出コード

解法

操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。

  • dp[l][r] = [l,r)の区間の文字全てを消すことができるかどうか

という区間DPを考えます。r-lが3の倍数でない時はもちろんNOです。
[l,r)を全て消去するには、

  • l \leq m \leq rを満たすmについて、dp[l][m],dp[m][r]が共にYESとなるものが存在する

  • S_{l},S_{r-1}がi、S_{m}がwであり、dp[l + 1][m]とdp[m+1][r-1]がYES

のいずれかを満たしていればよいです。(dp[l][l\のような空の区間についてもYESとみなしています)
よって、上記のいずれかを満たしていればYESとすることで、ある区間について全て削除できるかどうかがわかるようになります。
さて、

  • sum[l][r] = [l,r)について行うことができる操作の最大回数

として、再び区間DPをすることでこの問題に答えていきます。
dp[l][r]がYESのとき、sum[l][r]は明らかに(r-l)/3となります。
そうでない場合は、
sum[l][r] = max(sum[l][m] + sum[m][r])
によって計算できます。
以上により、答えを求めることができました。

感想

昔はとっかかりすらつかめなかったものがさらりと解けると嬉しいですね！考察、実装ともにサクサク行けたので良かったです。　

嘘解法はよくないですね！！！(上の解説は修正済みです)

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

動的計画法(DP)

問題
提出コード

解法

[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|]を求めればおしまいです。

感想

とても面白かったです。

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]
という遷移を行えばよいです。
これで、作成できる州の頂点数がわかったので、あとは最小値を計算すれば終わりになります。

感想

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

AGC029 D - Grid game

全探索

問題
提出コード

解法

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

  • 高橋君:常に移動する

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

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

感想

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