2020-01-19

ABC152 D - Handstand 2

数え上げ

解法

$(A,B)$ のうち、 $A$ をある値に決めた際にペアの相手となりうる $B$ の個数がいくらか、を高速で求めることができれば、 $A$ について全探索をして数え上げれば良いです。
$A$ の値を決め打ったときに、 $B$ の末尾の値と先頭の値は固定されてしまいます。
前者は $A$ の先頭(これを $P$ とします)、後者は $A$ の末尾(これを $S$ とします)です。
これ以降は、 $S...P$ となるような数を、桁ごとに数え上げていきます。まず、 $S$ と $P$ の値が等しいとき、 $S$ という1桁の数が $B$ の候補になります。答えに1加算します。 $X$ 桁(ただし2以上)の $S...P$ で、 $B$ の候補になるようなものが何通りあるかを考えます。
まず、 $X$ 桁の場合、少なくとも $S \times 10^{X-1} + P$ 以上の数字であることが確定します。
そして、 $S...P$ の $...$ の部分は、 $X-2$ 桁であり、 $00...0$ から $99...9$ までの $10^{X-2}$ 通りあることがわかります。
これらのパターンが、 $N$ 以下であるかどうかチェックしつつ加算するには、 $min(10^{X-2},(N- S \times 10^{X-1} + P) /10 + 1)$
を計算してあげればよいです。

2019-12-31

AOJ 2748 - 夏合宿の朝は早い

強連結成分分解(Strongly Connected Component)

問題
 提出コード

解法

人を頂点、(起こす、起こされる)を辺としたグラフについて、強連結成分分解をして同一視される頂点は、一つにまとめることができます。
まとめる頂点集合を $S$ としたときに、まとめた結果新しくできる頂点全体で寝坊する確率は、
$\displaystyle \prod_{i \in S} (iが寝坊する確率)$
とすることができます。
強連結成分分解をした結果DAGになっているはずですが、そのDAGの中で、入次数が0の頂点集合 $T$ について、
$\displaystyle \prod_{i \in T} (1 - (iが寝坊する確率))$
を計算すると、求めるべき答えとなります。

2019-12-30

ABC149 F - Surrounded Nodes

深さ優先探索(DFS)

問題
 提出コード

解法

ある頂点が白であったときに、その頂点が $S$ に含まれる確率を計算します。すると、この確率は、どの頂点についても独立に計算できるので、全ての頂点について同じことを計算して足すことで、その総和が答えとなります。
また、確率は、 $S$ に含まれるパターン数を、 $2^{N}$ で割ったものになるので、 $S$ に含まれるパターン数を数えていきます。まず、今計算したい頂点が木全体の根であった場合について考えます。
根に対する子が $k$ 個存在していたとすると、その $k$ 個の頂点を根とする部分木について黒い頂点があるかどうかを調べたときに、2つ以上の部分木に黒い頂点が存在していれば、今計算したい頂点が $S$ に含まれることになります。
ある部分木 $i$ について、その部分木に含まれる頂点の個数を $c_{i}$ とします。すると、
全てが白になるパターンは明らかに1通りなので、少なくとも1つ以上の頂点が黒になるパターンは、 $(2^{c_i}-1)$ 通りになります。
ので、 $k$ 個の部分木について、2つ以上の部分木に、1つ以上の黒い頂点が含まれているようなパターンは、全体から、全て白の頂点になるパターンと、1つの部分木のみが黒い頂点を含み、それ以外の部分木は全て白の頂点になるパターンを引けばよいので、

$2^{N-1} - 1 - \sum(2^{c_{i}}-1)$

となります。
ある頂点 $x$ を根とした部分木の全体の頂点数は、適当にDFSをすることによって求めることができるので、上の計算をすることによって、木全体の根が白だった場合に、 $S$ に含まれるパターン数を計算することができました。
あとは、ある頂点が木全体の根でなかった場合に、その頂点が白かつ $S$ に含まれるパターン数です。
このときは、 $N - (今見ている頂点を根とする部分木の頂点数)$ を一つの部分木とします。これは、親を辿っていくことができる部分になります。この部分木と、もともとある子の部分木について、上と同様の計算をしてあげればよいです。

f:id:emtubasa:20191230163351p:plain

f:id:emtubasa:20191230163619p:plain

1つめの図が、根について見ているパターンです。枠で囲まれているのが、考慮すべき部分木です。
2つめの図が、根の子における頂点を1つピックアップしたパターンです。こちらも、枠で囲まれているのが、考慮すべき部分木です。
2つめの図において、茶色の部分木の頂点数を調べるには、青、水、緑の部分木の頂点数の総和+今見ている頂点自身を、 $N$ から引いてあげればよいです。
青、水、緑の部分木の頂点数は、1つめの図で頂点数を数える時点で計算済みのはずなので、これで簡単に計算することができます。もしくは、 $N$ から、赤い枠の頂点数をひけばよいです。
全ての頂点数について、 $2^{N-1} - 1 - \sum(2^{c_{i}}-1)$ を計算したら、これを $2^{N}$ で割ったものが答えになります。

2019-12-30

ABC149 E - Handshake

二分探索

問題
 提出コード

解法

明らかに、得点の和が高いペアから順番に握手をしていくのが最適です。
ある得点 $X$ が達成できるとすると、明らかに $X$ 未満の任意の得点 $Y$ は、全く同じ手を選ぶことで達成でき、達成できないときは $X$ 以上の得点はどう頑張っても達成できないので、

$X$ 以上の得点を達成できるか

について単調性が存在します。
この $X$ について二分探索をしたいのですが、うまくいきません(僕はいきませんでした)。ので、少し見方を変えます。
得点の和が高いペアから順番に握手をしていくのが最適だったので、ある得点 $P$ について、

$P$ 以上となるペアについては握手を行い、 $P$ 未満となるペアについては握手をしない

という区切り目が存在するはずです。
$P$ 以上となるペアの個数が $M$ 個以上になると、 $M$ 回握手することができます。
$P$ 以上となるペアの個数についても、 $P$ が減少すれば個数が増加し、単調性が存在しています。ので、

$P$ 以上となるペアの個数が $M$ 以上になる

ような、最大の $P$ を二分探索で求めることができます。
すると、その $P$ 以上のペアの総和を求めればよいです。
片手が $A_{i}$ のとき、もう片方の手は、 $(P-A_{i})$ 以上の $A_{j}$ を選ぶことができます。この $A_{j}$ の個数は、 $A$ が降順ソートされていれば、二分探索で求めることができます。
これにより、ペアの個数を求めることができました。
総和についてもほぼ同様で、 $A_{1}$ から $A_{j}$ までの総和と、 $A_{i}\times(選べるA_{j}の個数)$ の総和を全ての $i$ について足したものになります。
これは、後者についてはそのまま個数をかければよく、前者については累積和をあらかじめ計算しておくことで、高速に計算することができます。
あとは、コーナーケースである、

$P$ 以上となるペアの個数がぴったり $M$ ではなかった場合

についての差分を計算すればよいです(サンプル2参照)。
得点の和が $P+1$ 以上となるペアは $M$ 個未満になってしまうはずなので、今 $P$ 以上となるペアの個数が $M+q$ 個あるとしたときに、総和から除くべき $q$ 個のペアは、得点が $P$ となっているものについてです。
ということで、 $Pq$ を、全体の総和から引いてあげれば求める答えとなります。

感想

見るからに二分探索をしたいなぁ、と思っていたのですが、うまく二分探索をする方法を考えるのに詰まってしまいました。
見方の変え方が課題です。

2019-12-30

ABC149 D - Prediction and Restriction

動的計画法(DP)

問題
 提出コード

解法

次に出す手は、 $K$ 手前の手にのみ依存します。
よって、じゃんけんの出す手は、 $K$ で割った余りごとに独立して考えることができます。
$dp[i][j] = i$ 番目に出す手が $j$ であるときにおける、 $i \ mod \ K$ の手番についての得点の総和の最大値
とすると、答えは $\displaystyle \sum_{i=N-K + 1}^{N} max(dp[i][j])$
となります。
$dp[i][j] = max(dp[i-k][k] + (jで勝てる場合はその得点) ) (j \neq k)$
となります。

感想

貪欲でも解けるらしいのですが、証明を短時間で行うのが難しそうな上、DPの方が確実な気がします。
言われてみれば確かに…ってなりました。

2019-12-23

ARC050 B - 花束

二分探索

問題
 提出コード

解法

$P$ 個の花束を作成できるかどうか、を調べます。
まず、2種類の花束どちらも、1つの花束につき少なくとも1本使用することになるので、最低 $P$ 本ずつ使用することになります。
この部分を除くと、

赤い花を $x-1$ 本使用する
青い花を $y-1$ 本使用する

の2通りの操作どちらかを行うことで、1つの花束を作成することができます。
ので、結局、
$\frac{R-P}{x-1} + \frac{B-P}{y-1} \geqq P$
であれば、 $P$ 個の花束を作成することができます。
この条件を調べて、 $P$ 個の花束を作成することができるとわかったとき、 $P$ 個未満の花束は明らかに作成することができます。
ということで、単調性が存在するため、上の条件を満たす最大の $P$ を二分探索で求めれば答えとなります。

感想

個数を決め打ち、どちらか片方のコストを0にして考えやすくする、といったよくある考え方が詰まっている気がします。

2019-12-22

ARC044 B - 最短路問題

数え上げ

問題
 提出コード

解法

頂点1が距離0でない場合や、頂点1以外が距離0である場合は、明らかに答えが0になるので処理しておきます。
それ以外のグラフについて考えます。
あらかじめ、距離が $x$ の頂点の個数 $c_{x}$ をそれぞれカウントしておきます。
距離が $x$ である頂点は、距離が $x-1$ である頂点、 $x$ である頂点、 $x+1$ である頂点に向けて辺を張ることができます。 $x+1$ である頂点との辺は、距離が $x+1$ である頂点から張る辺について考慮するときに計算すればよいので、距離が $x$ である頂点について考えるとき、 $x-1$ の頂点と $x$ の頂点に向けて張る辺についてのみ計算していきます。

距離 $x-1$ の頂点に向けての辺の張り方
距離 $x$ の頂点を1つ選びます。すると、この頂点は、距離が $x-1$ である頂点のうちすくなくとも1つの頂点に向けて辺が張られていなければなりません。
今選んだ頂点と、 $c_{x-1}$ 個の頂点との辺の張り方は、 $2^{c_{x-1}}$ 通りありますが、この中で選んではいけないパターンは、どこにも辺が張られていないパターンただ1つです。
ということで、距離 $x$ の頂点1つに対し、距離 $x-1$ の頂点との辺の張り方は $2^{c_{x-1}} - 1$ 通りとなります。
これが、 $c_{x}$ 個の頂点について同じことが考えられるので、最終的に距離 $x$ の頂点と $x-1$ の頂点についての辺の張り方は、
$(2^{c_{x-1}}-1)^{c_{x}}$ 通り
です。
距離 $x$ の頂点同士を結ぶ辺の張り方
距離 $x$ の頂点同士を結ぶ辺の張り方は、 $_{c_{x}}C_{2}$ 通りです。今回は、全ての辺について、張る、張らないの2パターンを自由に選べます。
ということで、
$2^{_{c_{x}}C_{2}}$
通りの張り方が存在します。