ツバサの備忘録

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

ABC080 D - Recording

問題
提出コード

解法

まずは、同一チャンネル内で区間が連続するもの、つまり(s,t) = (1,2)(2,4)をまとめて(1,4)のようにしてしまいます。これは、それぞれのチャンネルについて区間をわけ、そして開始時間の昇順でソートをして前から見ていき、今見ている区間の終わりの時間と次の区間の始まりの時間が同時刻であれば合体、というようにしていけばよいです。
あとは、いもす法を用いて、時刻iで必要な録画機の個数を調べていき、その最大値をとれば完成です。
今回、0.5という数字がでてきているので、すべての時刻を2倍してあげます。すると、(s,t)という区間の録画には、
2s-1から、2t-1という閉区間で録画機が必要になります。
なので、sum[i] = 時刻iで必要な録画機の個数、とすると、sum[2s-1]に1追加し、sum[2t]から1減算をすることで、あとはsum[i]について、はじめから累積和をとっていけば、sum[i]を完成させることができます。
あとは、全てのsum[i]のうち最大値をとることで、答えとなります。sumの配列は、時刻を2倍していることから、とりうる時刻の最大値の2倍だけ要素数が必要なことに注意してください。

ABC080 C - Shopping Street

問題
提出コード
ぱっと読んだときに、何を言っているのかさっぱりわからずしばらく考えがまとまりませんでした。

解法

結局、曜日と午前午後、5種類と2種類と考えるのではなく、時間帯が10種類と考えてしまうのが楽だと思います。
こうすると、joisinoお姉ちゃんの開く店の営業時間を10桁のビットで表現することができます。これは、たいした数にはならないので、全探索をすることができます。
営業時間をSとしたときに、N個のお店について、営業時間が被る個数を逐一調べ、その個数に対する利益を計算することができます。
これを、全てのSに対して計算し、合計利益の最大値を調べれば、答えとなります。
だいたい10^{6}程度の計算回数ですむはずです。

ABC079 D - Wall

問題
提出コード

解法

1つのマス目が、他のマス目に影響を及ぼすことも、影響されることもないので、それぞれのマスについて、-1でない場合に1へと変化させる魔力の最小値を求めればよいです。
ということで、マス目の現在の数字(0~9)を頂点、c_{i,j}iからjへ向かうグラフの辺の重みと考えると、現在のマス目の数iから、1への最短経路を求めればいいことになります。
頂点の個数は10個なので、ワーシャルフロイド法を適用して計算することができます。
あとは、前計算でiから1に変化させる魔力の最小値をワーシャルフロイド法で計算しておいて、全ての-1でないマスについて、iから1にする必要な魔力の合計値を求めれば、答えとなります。

Typical DP Contest バチャ

ということで、5日のDPまとめコンテストの予行練習も兼ねてTypical DP Contestを埋めていきました。解いた感想を書いていこうかなと思います。
AtCoder Virtual Contest

目次

A - コンテスト

解法はこちら↓
Typical DP Contest A - コンテスト - ツバサの備忘録
Aは復習問題になります。
基本的なDPだと思います、普段でいくと300点前後でしょうか?
始めたての頃はもちろん悩みに悩んだ問題なので、さらっと解けるようになっていて気持ちがいいです。


B - ゲーム

解法はこちら↓
Typical DP Contest B - ゲーム - ツバサの備忘録
Aから急激に難易度が上昇した気がします。とてつもなく時間がかかりました。
2人で最善を尽くしあうゲームの問題はとてつもなく苦手意識があります。
実装もそこそこ重たいので、苦労しながらのACでした。


C - トーナメント

解法はこちら
Typical DP Contest C - トーナメント - ツバサの備忘録
こういうことをやりたいんだろうなぁ、というものをそのままコードにした感じです。
指数部が整数値でない場合どうすればいいんだろう、と思っていたのですがpowが使えるのですね~、初めて知りました(忘れてるだけかも?)。
これまた配列の添え字関連で悩まされました。

D - サイコロ

解法はこちら↓
Typical DP Contest D - サイコロ - ツバサの備忘録
復習問題その2です。
前回解いたときは解説ACをしたので、きちんと解法の流れが頭の中に残っていたので良かった半面、MLEを一回出したので悔しいです。

E - 数

解法はこちら↓
Typical DP Contest E - 数 - ツバサの備忘録
復習問題その3です。
こちらも、前解いたときは初めての桁DPだったので解説を見ていましたが、他でも桁DPの問題を触っていたおかげで、さらっと解けるようになりました。
その割には30分かかっているのですが…
この手の問題にしては基本的な部類だと思います。

F - 準急

解法はこちら↓
Typical DP Contest F - 準急 - ツバサの備忘録
昔々、ICPCの練習会の際に先輩がこの問題を見ながら類題を解いていた記憶があります(自分も問題を読んでいたのですが、解法がさっぱりだったので投げてました)。
逆転の発想ぽいものが必要な感じだったので、時間がかかりました。

H - ナップザック

解法はこちら↓
Typical DP Contest H - ナップザック - ツバサの備忘録
ただのナップサック問題を数段レベルアップさせたような感じでした。
解法をこれだ!って決めつけていたのですが、それがうまくいってよかったです。違ったら解けてなさそうです。

J - ボール

解法はこちら↓
Typical DP Contest J - ボール - ツバサの備忘録
制約を見た時点であーこれだ、っていうのと、上の記事にも書いていますが期待値の問題で躓いた結果印象に残っている問題があり、こう計算すればいい!というのがすぐにわかったのがいい感じに動きました。
後ろの方の問題の中では現状これが一番さらっと解けたかな?と思います。と書こうとしたのですが、真ん中らへんでした(先は長いですね)。

K - ターゲット

解法はこちら↓
Typical DP Contest K - ターゲット - ツバサの備忘録
昔既読を付けたことがあるのですが、当時は解けていませんでした。なぜか解説を見ることもしていなかったようです。
時間は結構かかりましたが、無事に自力で解けました。昔解けなかったものが解けるようになるのはうれしいですね。

M - 家

解法はこちら↓
Typical DP Contest M - 家 - ツバサの備忘録
先輩が通していたので、負けないぞー!と思って解きました。
1問1問が重いので、やりきった感がでますね...代わりに疲れますけど。


ということで、最後は時間があまりない+難しくて解けないのコンボによりほぼできませんでしたが、10問ほど通すことができました。
DPの気持ちが前よりはわかるようになるといいですね~

Typical DP Contest M - 家

問題
提出コード

解法

bitDPです。だんだん詰め合わせ感が増えてきました。
m[i][j] = 同じ階層でiからjに移動するパターン数
とすると、これをR\times Rの行列に見立ててH乗すると、m[1][1]が答えになります。
m[i][j]を求めることさえできれば、あとはこの行列式2^{k}を求めていき、O(R^{2}logH)程度で答えが求まります。
ということで、この行列式を完成させることを考えます。
dp[i][j][S] = iからSの部屋を通り、jにいくパターン数
とします。部屋が16までしかないので、通る部屋の状態Sをビット列で持つことができます(自分は、スタート地点とゴール地点のi,j両方のビットも立てました)。
このとき、m[i][j]は、dp[i][j][S]の全ての状態Sに対する総和になります。
このDPは、スタート地点iから幅優先探索をすることで求めることができます。
今、Sの部屋を通り、jの部屋にいるとします。すると、Sに含まれていないかつ、jからいくことのできる部屋kについては、部屋k2^{k}で表されることを利用して、
dp[i][k][S+2^{k}] += dp[i][j][S]
という遷移を行えばよいです。
ということで、すべての部屋をスタート地点に選んだ幅優先探索を行い、このDPを埋めることで、m[i][j]を完成させることができます。
あとは、H乗すれば、答えが求まります。

Typical DP Contest K - ターゲット

問題
提出コード

解法

区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。
まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標xrがわかっているとき、円と軸が接する2点は、x-rx+rになります。
すると、このx-rからx+rを、一つの区間としてみることができます。i番目の円C_iに対するx_i - r_iL_ix_i + r_iR_iとします。
あるサイズのターゲットが存在するとき、もう一つサイズを増やすには、
今あるターゲットの中で最大の円C_iと、新しく加わる円C_jが次のような関係になっている必要があります。
L_j \lt L_iかつR_i \lt R_j
図で表すとこのような状態です。 f:id:emtubasa:20190101125255p:plain
さて、ここで区間スケジューリングのように、区間の終わり、つまりR側に注目すると、Rを降順でソートすることで、円をいくつか選び、その円でサイズKのターゲットが作成できたとき、K個を大きさ順に並べると、上のソートした順番と同じになります。
ので、Rについて降順でソートしておけば、あとはLについてのみ考慮すれば、前から順番に円を選んでいくだけでターゲットが作成できるということです。
としたいのですが、コーナーケースが存在します。R_i = R_jとなるようなケースになります。このような場合は、Lについて昇順になっていると、L_iL_jのみでターゲットのサイズを増やせるかどうかの判定ができないので、降順にならべておけばよいです。

ここで、LISを思い出すことができれば、
 dp[K] = サイズKのターゲットを作成できるとき、その中で最小の円c_iについてのL_iの最小値
とすると、この問題を解くことができます。
c_jを合わせてサイズK+1のターゲットを作成するときに必要な条件が、L_i \lt L_jであるので、L_iはできるだけ小さくしておきたいからです。
dp[K]の中の要素は昇順に並んでいますので、c_iについて見ているとき、L_iのlower_boundを探しその部分を更新していき、なければ今最大のKに1追加した場所、つまりdp[K+1]L_iを格納する、という操作を行えばよいです。これをN回繰り返すと、値が格納されているKのうち最大の値が答えになります。

Typical DP Contest J - ボール

問題
提出コード

解法

bitDPです。
期待値の考え方については、こちらの問題のおかげですんなりいきました。

ARC085 C - HSI - ツバサの備忘録

dp[S] = 座標においてある物の状態がSである場合に、そこから全ての物を倒すまでに投げるボールの回数の期待値
とします。座標は0~15までしかないので、このようなことができます。座標xに物が存在するとき、右からx+1番目のビットに1を立てます。すると、この状態は2^{x}で表現することができます。
さて、初期状態はdp[0]  = 0となります。
ある状態Sの際にボールをxめがけて投げると、x-1,x,x+1のどこかに物が存在していれば、倒すことができます。確率はすべて1/3なので、座標xにボールが落ちたときにSからS_{x}に遷移すると仮定すると、dp[S]は次のように表現することができます。
dp[S] = \frac{1}{3} (dp[S_{x-1}] + dp[S_{x}] + dp[S_{x+1}]) + 1
式変形すると、次のようになります。
3dp[S] = dp[S_{x-1}] + dp[S_{x}] + dp[S_{x+1}] + 3
さて、これを再帰なりなんなりを用いて、全てのxについて計算した上で最小値を求めればいいのですが、注意が必要です。
S_xが、実はSと同じ状態になる可能性があります。xに物が存在しなかった場合です。
例えば、x-1x+1には物が存在して、xには物が存在しなかった場合は、
3dp[S] = dp[S_{x-1}] + dp[S] + dp[S_{x+1}] + 3
となります。
これは、式変形をさらに行い、
2dp[S] = dp[S_{x-1}]  + dp[S_{x+1}] + 3
とすることができます。
また、x-1,x,x+1のどの場所にも物が存在しなかった場合、この式を適用することはできず、またそもそもこれが最適解になることはありえない(1回分無駄うちしていることになります)ので、スルーすることに注意しましょう。
あとは、このDPをうまく実装して、全てのxに対しての計算を行い、最小値を求めていけば、答えを求めることができます。