ツバサの備忘録

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

ABC153 E - Crested Ibis vs Monster

問題
提出コード(1)
提出コード(2)

解法

dp[i][j] = i番目までの魔法を撃ち終えて、jだけダメージを与えたときに消費する魔力の最小値
とすると、

  • j \geqq A_{i}のとき
    dp[i +1][j] = min(dp[i][j],dp[i + 1][j - A_{i}] + B_{i})

  • j \lt A_{i}のとき
    dp[i + 1][j] = dp[i][j]

となります。
初期値はdp[0][0] = 0、答えは、min(dp[N][j]) (j \geqq H)です。
見るべきjの範囲は、H + max(A_{i})までなので、最大でも2 \times 10^{4}程度になり、このDPによる計算が間に合います。
これが提出コード(2)です。

dp[i][j] = i番目までの魔法を撃ち終えて、j以上ダメージを与えたときに消費する魔力の最小値
とすると、
dp[i + 1][j] = min(dp[i][j],dp[i + 1][max(0,j-A_{i})] + B_{i})

となります。初期値は上と同様、答えはdp[N][H]です。
これが提出コード(1)になります。

AOJ 2631 - Clique Coloring

問題
提出コード

解法

それぞれの頂点について、i回目に選ばれたか選ばれてないか、について考えると、2^{n}パターンあります。
これらをビットで表すと、\sum (立っているビットの数-1)だけ、全体から1つ頂点を減らすことができます。
また、i回目とj回目に同時に選ばれる頂点が2つ以上あることはありません。
つまり、2つ以上ビットが立っているパターンについては、そのような頂点があるか、ないかの2択になります。
2つ以上ビットが立っているパターンは、2^{n} - n - 1通り(1つもビットが立ってないのが1通り、1つのみビットが立っているのがn通り)ありますが、この値をXとして、2^{X}通りのパターンについて枝刈り全探索をすればよいです。
i,jが同時に立っているビットを既に選択したかどうか、次にどのパターンを選択するか、そして現在いくつの頂点を削減できたか、の情報を引数にもち、再帰でDFSをしました。
今見ているパターンを選択する場合は、引数にあるi,jが同時に立っているビットの情報を更新(矛盾すればその場で打ち切り)、それぞれの立っているビットについて選ばれた回数を計算(a_{i}を超えることはできません)し、再帰をします。

感想

数週間考えました…
このタイプは苦手です。

ABC152 F - Tree and Constraints

問題
提出コード

解法

あらかじめ、頂点iからjへのパスに使われる辺の集合を表すビット列T_{ij}を、前計算で計算しておきます。これは、任意の頂点iからBFSで辿っていけば良いです。
M個の条件からいくつか選んだ、条件の集合Sに対して以下のような数を計算します。

  • Sに含まれる条件を全て満たさないような辺の色の決め方の場合の数

すると、包除原理によって、Sに含まれる条件の個数が偶数なら求めた値を加算、奇数なら減算、を2^{M}通りの全てのSについて繰り返すと、求める答えとなります。

上で計算したかった値をC_{S}とします。
Sに含まれる条件は全て満たさない、という仮定があるので、Sに含まれる条件に指定されている辺は全て白くしなければなりません。
逆に、それ以外の辺については何も制約がないので、黒白どちらでも問題ありません。
条件に指定されていない辺の個数をXとすると、
C_{S} = 2^{X}となります。
あとはSに対するXが求まればよいです。
これは、Sに含まれる全ての条件について使われる辺を洗いだし、それらの和集合を求めれば、その個数をN-1から引けばよいです。これは、最初に前計算しておいたビット列を用いると、OR演算を用いて簡単に計算することができます。

感想

問題を見た時点で包除っぽい、となってから、Mの制約に気づき、素直に考察が進んだと思います。

ABC152 E - Flatten

問題
提出コード

解法

A_{i}B_{i}の値は、明らかにA_{i}達の最小公倍数になります。
ですが、愚直にやっては途中でオーバーフローをしてしまうため、最小公倍数の素因数を先に列挙してあげることで、後で10^{9}+7でMODを取りながら計算してあげると、オーバーフローせずに最小公倍数を10^{9} +7で割った余りが求められます。
あとは、求めた値をXとして、B_{i} = X / A_{i}の総和を求めてあげればよいです。
素因数を求めるには、全てのA_{i}について、O(\sqrt A_{i})でそれぞれを素因数分解し、素因数と、その個数を求めます。そして、それぞれの素因数について、その個数の最大値を求めてあげればよいです。

ABC152 D - Handstand 2

問題
提出コード

解法

(A,B)のうち、Aをある値に決めた際にペアの相手となりうるBの個数がいくらか、を高速で求めることができれば、Aについて全探索をして数え上げれば良いです。
Aの値を決め打ったときに、Bの末尾の値と先頭の値は固定されてしまいます。
前者はAの先頭(これをPとします)、後者はAの末尾(これをSとします)です。
これ以降は、S...Pとなるような数を、桁ごとに数え上げていきます。 まず、SPの値が等しいとき、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)
を計算してあげればよいです。

AOJ 2748 - 夏合宿の朝は早い

問題
提出コード

解法

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

ABC149 F - Surrounded Nodes

問題
提出コード

解法

ある頂点が白であったときに、その頂点が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}で割ったものが答えになります。