2019-11-15

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

解法

全方位木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を行いつつ、根の付け替えを行い答えを求めることができます。

感想

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

2019-10-22

第１６回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$ の与えられ方についてはじめ勘違いしていたので危なかったです…
(๑>﹏<๑｀)ぷぇーン現象

2019-10-22

第１３回JOI予選 D - 部活のスケジュール表 (Schedule)

動的計画法(DP)

問題
 提出コード

解法

$dp[i][S] = i$ 日目に参加した部員の状態が $S$ であるような、 $1$ から $i$ 日目までの部員の組み合わせの通り数
とします。
すると、
$S$ の中に、責任者が含まれていなければならない
という条件があるので、もし $S$ の中に責任者がいなければ、

$dp[i][S] = 0$

となります。
そうでない場合は、
$S \cup T \neq \varnothing$
となるような $T$ の総和を求めればよく、

$dp[i][S] = \sum dp[i-1][T] (S \cup T \neq \varnothing)$

を計算すればよいです。

感想

はじめ、状態が8種類しかないところに気づけなかったので危なかったです。

2019-10-16

ARC064 E - Cosmic Rays

ダイクストラ法幾何

問題
 提出コード

解法

あるバリア内は好きな座標に移動できます。
ので、あるバリアから、別のバリアへと移動することを考えます。
そのとき、2つのバリアについて重複する箇所が存在すれば、そのバリア同士は自由に行き来することができます。そうでないときは、2つの円の最短距離を求めれば、その距離の部分のみ、宇宙線を浴びることになります。それよりも短い距離で2つのバリアを行き来することはできません。
結局、2つのバリアの距離は、
$(中心座標の距離) - (2つの円の半径の和)$
で求めることができ、また、2つのバリアで重複箇所がある場合は、この値が0以下になるので、最終的に、2つのバリアを行き来する際に浴びる宇宙線の時間は
$max(0,(中心座標の距離) - (2つの円の半径の和))$
となります。
スタート地点、ゴール地点は、中心座標そのまま、半径が0の円とみなすことができるので、あとは、 $N + 2$ 個のバリアについて、任意のバリアのペアを行き来した際に浴びる宇宙線の時間を計算してそれをコストとしつつ、ダイクストラ法を用いることで、スタート地点からゴール地点へ行く際に浴びる宇宙線の時間の最小値が求まります。

2019-10-10

AOJ 1232 - Calling Extraterrestrial Intelligence Again

二分探索

問題
 提出コード

問題概要

3つの整数 $m,a,b$ が与えられます。
$pq \leqq m$ かつ $a/b \leqq p/q \leqq 1$ となるような $(p,q)$ のうち、 $pq$ が最大となるようなペアを求めてください。
制約は、 $4 \lt m \lt 100000, 1 \leqq a \leqq b \leqq 1000$ です。

解法

まずはエラトステネスの篩を利用して、素数を洗い出します。
$q$ について全探索をすると、 $p$ の最適解は、ある $q$ に対して、
$p \leqq m/q$ 、 $aq/b \leqq p \leqq q$ を満たすような最大の素数になります。
ので、二分探索で $p$ の最大値を毎回求め、答えを求めていけばよいです。

のですが、AC後に他の解説ブログを見たところ、 $m/q$ という制約のおかげで、 $p$ も全探索できるらしいです…ちょうど調和級数の形になりますね。

感想

篩で洗い出す素数の個数を2回間違えました(最初は少なすぎてWAが出て、その後増やしすぎてTLEになりました)…反省します。

2019-09-28

ABC142 F - Pure

問題
 提出コード

解法

方法は、 $i$ 番目から $i$ 番目に戻ってくるサイズが最小の閉路について、問題の条件を満たしているかどうか調べる、というものです。
これを全ての $i$ について調べ、存在すればそれを答えればよいです。
何故なら、与えられたグラフの中で、最小のサイズの閉路を見つけると、それが問題の条件を満たすグラフになるからです。
まず、問題の条件を満たす閉路が1つあったとします。
そこに、辺を1つ追加すると、その閉路は問題の条件を満たさなくなってしまいます。
しかし、その閉路についてよく見ると、追加した辺を上手く使うことで、問題の条件を満たすような閉路が必ずどこかに存在しています。

f:id:emtubasa:20190928230144p:plain

例えば、黄色と青の辺からなる、問題の条件を満たす閉路が存在したときに、橙の辺を追加したとしても、黄色＋橙の辺と、それにつながってる頂点のみを選ぶことで再び問題の条件を満たす閉路が完成します。
こうして完成した閉路に、適当な頂点と辺を追加したものが問題で入力されるグラフになるので、この一番小さい閉路を探せばよいことになります。
そして、それは上記の方法で求めることができます。
具体的には、閉路を探すパートについてはBFSとその復元(1つ前に通った頂点をメモしておく)を行い、問題の条件を満たすかどうか検査するパートでは、選んだ閉路につながっている辺についてチェックし、どこかで出次数か入次数が2以上になっている頂点が存在しないか見ればよいです。
結果的には $O(N(N+M))$ ぐらいで解けます。

感想

上手い実装方法がわからなかったのでこうなりましたが、バグなくかけたのでまぁ良かったです。

2019-09-28

ABC142 E - Get Everything

bitDP

問題
 提出コード

解法

制約がbitDPをしろと言っているので、bitDPをします。
$dp[S] =$ 現在開けた宝箱の状態が $S$ のときに、そこからかかる費用の最小値
とします。
$S$ を整数型の変数1つで表し、2進数の桁に宝を割り振り、0:まだ開いていない、1:開いている、とすると
初期値は $dp[2^{N}-1] = 0$ で、答えは $dp[0]$ です。
$dp[S]$ を求めることについて考えると、
状態が $S$ の際に $i$ 番目の鍵を使うと、 $S \cup T_{i}$ (ただし、 $T_{i}$ は $i$ 番目の鍵を使用して開けることのできる宝箱の集合)
となります。
鍵は $M$ 種類あり、これを全部試せばよく、
$dp[S] = min(dp[S \cup T_{i} ] +a_{i})$
となります。 $S \cup T_{i} = S$ のパターンは注意する必要があり、スルーしなければなりません。
あとはこれを繰り返せば答えが求まります。
$O(2^{N}MN)$ なのですが、 $T_{i}$ を前計算してあげると $O(2^{N}M)$ になります(自分は前計算してないです)