ツバサの備忘録

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

Educational DP Contest / DP まとめコンテスト Z - Frog 3

Li Chao Tree 動的計画法(DP)

問題
提出コード

解法

dp[i] = i番目の足場へ行く最小コスト
とします。すると、
dp[i] = min(dp[j] + (h_{i} - h_{j})^{2} + C) (j \lt i)
となります。
これを式変形すると、
dp[i] = min(dp[j] + h_{j}^{2} - 2h_{i}h_{j}) + h_{j}^{2} + C
となります。h_{j}^{2} + Cは最後に足して問題ないことがわかります。
a_{j} = -2h_{j}, b_{j} =dp[j] + h_{j}^{2} とすると、
dp[i] = min(a_{j}h_{i} + b_{j}) + h_{j}^{2} + C
という式になり、調べたいのは、
a_{j}x + b_{j}のx = h_{i}の際の最小値
となります。
これは直線の式になっているので、
たとえばCHT アルゴリズムで検索をすると下のような記事が、

http://satanic0258.hatenablog.com/entry/2016/08/16/181331

また、Li Chao Treeで検索をすると下のような記事が出てきます。

https://smijake3.hatenablog.com/entry/2018/06/16/144548

あとは、これらのアルゴリズムを用いて、

  • h_{i}でクエリを投げる(得られた最小値をxとします)

  • a_{i} = -2h_{i},b_{i} = x + 2h_{i}^{2} + Cの直線を追加する

という操作を繰り返すと、h_{N}のクエリの答えxに、h^{2} + Cを加えたものが答えになります。
h_{1}のみ、クエリを投げずにa_{1} = -2h_{1},b_{1} = h_{1}^{2}の直線を追加します。

感想

上記のアルゴリズム達は、直線を管理するアルゴリズム、ということだけ知っていたので、もしかしてこれかな？と思い検索をかけるとぴったりハマったので嬉しかったです。

Educational DP Contest / DP まとめコンテスト Y - Grid 2

包除原理 動的計画法(DP)

問題
提出コード

解法

包除原理を用いて解きます。
dp[i][j] = j個以上の壁を通り、i番目の壁に到達するような通り方の場合の数
とします。ここで、壁について、行、列の順で昇順ソートしておくと、i番目の壁を通る際に、i+1番目以降の壁を先に通ることはありえなくなるので、うまく計算することができます。
また、スタート地点を0番目の壁、ゴール地点をN+1番目の壁、とすることで、初期化はdp[0][0] = 1とすることができます。
dp[i][j] = \sum dp[k][j-1] \times _{r_{i} + c_{i} - r_{k} - c_{k}} C _{r_{i}-r_{k}} ( ただし、i \gt k, c_{i} \gt c_{k})
r_{i} \gt r_{k}は、初めにソートしたときに満たすようになっています。
右側のコンビネーションの項は、k番目の壁からi番目の壁に行く行き方です。
これを計算すると、答えが(偶数個の壁を通り(H,W)へ行く行き方)-(奇数個の壁を通り(H,W)へ行く行き方)
となるので、dp[i][j]のjの部分を、0,1の2通りに集約することができます。こうすることで、計算量がO(N^{2})におさまり、
dp[N+1][0] - dp[N+1][1]
になります。

感想

包除原理は普段解けないことが多いのですが、割とスッキリ解けたのでよかったです。

Educational DP Contest / DP まとめコンテスト X - Tower

動的計画法(DP)

問題
提出コード

解法

現在、積まれているブロックの重さの総和をGとします。
ここに、2種類のブロックi,jを、どちらの順番で新しく下に置くかを考えます。

  • iの方がjより上にくる場合
    G \leqq s_{i} \cap G + w_{i} \leqq s_{j}

  • jの方がiより上にくる場合
    G \leqq s_{j} \cap G + w_{j} \leqq s_{i}

1つめの条件は、結局2つのブロックを乗せることにした時点で満たしていなければならないので、無視します。
ということで、それぞれの条件の2つ目を比較すると、
G \leqq s_{j} - w_{i},G \leqq s_{i} - w_{j}
となり、s_{j} - w_{i}とs_{i} - w_{j}のうち大きい順番の方が、Gの許容範囲が大きくなります。
s_{j} - w_{i} \leqq s_{i} - w_{j}の場合、jをiの上に乗せたほうがよいです。
この条件を式変形すると、s_{j} + w_{j} \leqq s_{i} + w_{i}となるので、
結局はs_{i} + w_{i}の昇順でブロックを並べると、その順番で上から積んでいくのが最善になります。
あとは、基本的にナップサックと同じで、
dp[i][j] = i番目のブロックまで見て、重さの総和がjになるようなブロックの選び方をしたときの、価値の総和の最大値
として、
dp[i + 1][j] = max(dp[i][j], dp[i][j - w_{i}] + v_{i})
(ただし、j \lt w_{i} もしくはj - w_{i} \gt s_{i}の際はdp[i][j])

を計算すればよいです。
答えは、dp[n][j]の最大値、初期化は全て0です。

感想

この問題で似たような考え方をしたので、あっさりと解くことができました。
が、証明は難しいです…(後付けで考えました)

Educational DP Contest / DP まとめコンテスト W - Intervals

動的計画法(DP) Segment Tree(セグ木)

問題
提出コード

解法

dp[i] = i文字目を"1"にした場合に、[1,i]で得られる得点の最大値
を考えます。
すると、
iが間に含まれているものを除いた区間達について計算した場合の、[1,i-1]で得られる得点の最大値に、iが間に含まれている区間の得点の総和が、dp[i]の値になります。
これを上手く計算するには、

  • dp[x] = max(dp[y]) (y \lt x)を計算する

  • x = r_{i}を満たす全てのl_{i},r_{i},a_{i}について、dp[z] (l_{i} \leqq z \leqq r_{i})にa_{i}を加算する

という操作を、xが小さい方から順番に繰り返していけば良いです。
このようにすることで、それぞれの区間が重複して加算されるのを防ぐことができます。
答えは、dp[i]の中で最大のものを計算すればよいです。

感想

区間の重複加算を防ぐ方法を思いつくのに時間がかかりました…セグ木は便利ですね！

ICPC 2019 Asia Yokohama Regional参加記

番外編 ICPC

ということで、チーム CoprimEとして、ICPCのアジア予選に参加してきました。
チームメイトはTsuzu君、mi君です。

1日目

～リハーサル前

コーチのご厚意で一部奢っていただきました。


リハーサル

Tsuzu君が環境構築、僕がA、mi君がBを読みました。
Aはやるだけなので僕がそのまま通しました。
Bはほぼ同じ問題を僕が解いたことがあったのですが、とりあえず2人も実装してみようということで実装しました。が、二人とも実装が詰まったので自分がバトンタッチして通しました。
Cは非想定らしい、解法っぽいものを残り5分ぐらいで思い浮かんだのですが間に合わず終了しました。


リハーサル後

観光をしました。

ABCにも出ましたが、Fが解けず黄色前半パフォだったため、黄色には届きませんでした。


2日目

本番

コンテスト開始直前になって、急に開始時間が5分はやまりました。まわりを眺めると、okimotiチームのrisujirohさん(だったはず)がトイレにまだ行っていたようで、大変そう…と思いながら問題を解き始めました。

コンテスト開始後は、リハーサル同様Tsuzu君が環境構築、僕がA、mi君がBを読みました。
Aは自分がそのまま実装、BはTsuzu君が実装してACしました。
その後、まわりを眺めつつ、問題をE,G,Hに絞り進めていましたが、Hの実装をまわりのチームがACし始めた直後ぐらいに始めたにも関わらず、最後までバグを取り切ることができませんでした。
自分はコードを2回、1から書き、Tsuzu君も1回1から書き直していました…
結局、コンテスト後に試したところ、自分は1行を変えただけで通りました。
同時に進めていたGもバグを取り切れず、結局2完52位で終了しました。

コンテスト後

Googleブースにあった、入力例のサンプルのみが与えられてそこから問題をエスパーする、というものを最後までやっていました。最後まで解けなかった上答えが答えだったのでかなり悔しかったです…チームメンバーはいろいろなブースをまわって楽しんでいたようです、賢い。

3日目

オフィスツアーです。疲労もあり結構疲れていました…

https://twitter.com/emtsu_ba/status/1196283821005533184?s=20

(最後はMicrosoftさんを見に行ったわけではないです)

感想

強豪チームがバンバン問題を解いていく様子を生で見ることができたり、普段は行けないような場所に行けたりしたので楽しかったです。

コンテスト前に、普段競プロをあまりやっていない同学年の友達に声をかけてもらったり、コンテスト中に反応をしていてくれたみたいで嬉しかったです。が、きちんと練習をしていればもっと上を目指せるチームだったはずなので、応援してくれた方々や、国内予選を戦った他の早稲田のチームには申し訳ない気持ちでいっぱいです。
来年はチームがどうなるかまだまだわかりませんが、チャンスがあればまたアジア予選に出場し、今度こそ納得のいく成績を取れるようにしたいです…
今、自分の大学の1年生や2年生で競プロ活動が活発になっていて、精進量がずば抜けている人もちらほら見かけます。自分が現状全く精進をしていないのもあり、このままだと抜かされる(もう負け始めている？)気がしているのですが、だからといって後輩たちに枠を譲るつもりは全くないので、また1から頑張ろうと思います。


負けません。


最後に、ICPCの運営をしてくださった方々、誘った際に快く承諾してくださったTsuzu君とmi君、そしてコーチを引き受けてくださったryoissyさん、ありがとうございました。

Educational DP Contest / DP まとめコンテスト V - Subtree

全方位木dp 動的計画法(DP) 前計算

問題
提出コード

解法

全方位木dpをします。
初めに頂点1が根である際の値を求めます。
dp_{j}[i] = jを根とする部分木について、iを黒で塗った際の部分木の塗り方
とすると、頂点iの子の集合をS_{i}として、
\displaystyle dp_{j}[i] = \prod_{p \in S_{i}}(dp_{j}[p] + 1)
となります。
ans[i] = iを根とした際の求めるべき答え
とすると、
\displaystyle ans[1] = \prod_{p \in S_{1}}(dp_{1}[p] + 1)
となります。
dp_{i}が求まっている際に、その子であるjについての答えans[j]を求めるため、dp_{j}へシフトすることを考えます。
書き換えるべき場所は、dp_{j}[i]とdp_{j}[j]のみになります。
dp_{j}[j]については、定義に基づいて計算すればよいので、dp_{j}[i]を求めることのみ考えます。
\displaystyle dp_{j}[i] = \prod_{p \in S_{i},p \neq j}(dp_{i}[p] + 1)
となるので、あとはこれを計算すればよいのですが、愚直に計算をすると間に合いません。
ある数列a_1, a_2, a_3, ... a_nについて、\frac{\prod_{k=1}^{n}a_k}{a_i}を高速に計算する方法を考えます。
これは、累積和同様に数列の前方からの累積積と、後方からの累積積をあらかじめ計算しておくと、それぞれの累積積について、i番目の手前の値をかけ合わせることで、前計算O(N)のみで、O(1)で計算することができます。
あとは、これを利用することで、dfsを行いつつ、根の付け替えを行い答えを求めることができます。

感想

全方位木の概要は知っていたので考察はすんなり進んだのですが、累積積を利用する部分を思いつくのが難しかったです…

第１６回JOI本戦 A - フェーン現象 (Foehn Phenomena)

未分類

問題
提出コード

解法

それぞれのタイミングでの、A_{i} - A_{i-1}の差がわかれば、S,Tのどちらかをかけつつ総和を求めればよいです。
それぞれの差について注目すると、ある区間[l,r]が与えられたときに、A_{i} - A_{i-1}に影響が出るのは、(A_{l-1},A_{l}),(A_{r},A_{r+1})の2つのペアのみになります。これ以外の部分、およびこれ以外のタイミングで影響を及ぼすことはありません。
ので、はじめに全てのA_{i} - A_{i-1}を求めておき、クエリが来るたびに、上記の2つのペアに対してXを加(減)算して、その部分だけ計算しなおす、ということを繰り返せば、高速に答えを求めることができます。

感想

Nの与えられ方についてはじめ勘違いしていたので危なかったです…
(๑>﹏<๑｀)ぷぇーン現象