ツバサの備忘録

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

Educational DP Contest / DP まとめコンテスト U - Grouping

問題
提出コード

解法

制約から見てbitDPです。

  • dp[S] = 現在グループを組めていないウサギの状態がSのときに、それ以降のグループ分けで得ることができる得点の最大値

とします。すると、Sの部分集合Tを用いて、
dp[S] = max(dp[S\setminus T ] + sum[T])
と書くことができます。
ただし、sum[T]は、Tというグループを作成したときに得られる得点です。これは、前計算によってO(2^{N}N^{2})で計算できます。
先ほどのDPの遷移の計算量を見積もってみます。
ある集合Sについて、残っているウサギの数を|S|と表現すると、部分集合T2^{|S|}通りあります。
残っているウサギの数が|S|となるような集合Sの選び方は_{N}C_{|S|}です。ここで、本来は|S|が0となるような選び方をしないのですが、計算をしやすくするために0も選ぶことができるとすると、|S|0からNまであり得ることに注意して、
\displaystyle \sum_{i=0}^{N} 2^{i} \  _{N}C_{i}
となり、これは
\displaystyle \sum_{i=0}^{N} 2^{i}  \times 1^{N-i} \times   _{N}C_{i}
であり、結局二項定理の式そのものなので、
(2+1)^{N} = 3^{N}
となります。
ということで、最初のDPの遷移はO(3^{N})で計算できるということがわかりました。
あとは、前計算とDPの遷移を行うことで、dp[S_{all}]を見れば答えがわかります(S_{all}は全てのウサギが入っている状態です)。初期状態は、ウサギが1羽の任意の集合Uに対して、dp[U] = 0です。
<br\ >

感想

だいぶ前に考察だけ終わらせておいて放置していた問題でした…
bitDPなのでやりたいことはほぼ覚えてました。一見O(4^{N})になりそうで、きちんと計算すると計算量が減るタイプの問題ですね。

ABC126 F - XOR Matching

問題
提出コード

解法

  • M=1の場合
    K=0ならば0 \  0 \ 1 \  1もしくは0 \  1 \ 1 \  0もしくは1 \  0 \  0 \  1を出力すればよく、それ以外ならば-1を出力します。

  • それ以外の場合
    K \geqq 2^{M}の場合、数列に含まれる数字は2^{M}-1までの関係で、どう頑張ってもKを作成することができないので答えは-1になります。
    そうでない場合、
    0, 1, 2, ... K-1, K+1, ... 2^{M}-1, K, 2^{M}-1, ... K+1, K-1, ... 2, 1, 0, K
    という数列を作成することで問題の条件を満たします。
    まず、挟み込んでいる2つの数字a_{i},a_{j}については、それらでxorを取った時点で打ち消しあって0になるので、考えなくてよいです。
    0から2^{M}-1の全ての数字についてのxorを取ると、全ての桁について、立っているビットは全体の半分で偶数であり、結局は0になります。
    そこからある数Xについてのxorだけを取らないことを考えると、これは0Xについてのxorを取ることと変わらないため、結局Xになります。
    ということは、2つのKで挟み込まれている部分のxorがKとなるには、K以外の[0,2^{M})についてのxorを取っていればよく、逆にK以外の数字で挟みこまれている部分のxorがKになるには、Kを1つだけ用意しておいて、それ以外の数字についてのxorが0になっていればよいので、上のような数列を用意してあげればよいことになります。

    感想

    せっかく考察がはやく終わったのに、デバッグに1時間ぐらいかかったうえ、結局バグはサンプルケース(M = 1の部分)だったということに気づいたのが終了数分前でした。
    ACできる考察を用意する前では、コーナーケースとして処理していたのですが、ACできる考察のコードに、その処理を記述し忘れていました…
    この手のバグ取りに時間をかけてしまう(+サンプルを通さない)のはよくない気がしているので気を付けたいですね。

ABC126 E - 1 or 2

問題
提出コード

解法

A_{X_{i}}を指定してその数字を特定したとします。
すると、A_{Y_{i}}Z_{i}の偶奇に関わらず、自動的に数字が特定できます。
そして、これが連鎖的に続くことになり、
他にA_{X_{i}}, A_{Y_{i}}が条件に含まれている部分についても自動的に、もう片方が特定されていきます。
ので、結局はA_{X_{i}},A_{Y_{i}}という条件は、その2つの頂点を繋ぐ辺が存在している、と考えると、N頂点のグラフの連結成分の個数を求める問題になり、これはUnion-Findを利用して、与えられた辺を結び付けていくことで、うまく個数を数えられるようになります。
答えは、root(i) = iとなっているiの個数を求めればいいです。
自分は、iについて全探索をし、root(i)が初登場のときにカウント、そうでなければスルー、という感じでカウントをしました。

感想

はじめはA_{Z_{i}}だと思っていました。
Z_{i}が今回の問題にほぼ無関係であることがわかってからはすぐだったので良かったと思います。

ABC126 D - Even Relation

問題
提出コード

解法

木、とは書かれているのですが辺に重みがあるのでダイクストラをしてしまいました。
ある頂点と別の頂点の距離が奇数の場合、その部分は確実に色が異なります。
これを繰り返すと、結局はある頂点を一つ決めた際に、そこからの距離の偶奇を判定すればよくなります。
ということで、ある頂点を根としたときに、そこから距離が偶数の頂点は根と同じ色を、奇数の頂点は根と違う色を塗ればよいです。
あとは、ある根を適当に決めて、そこからほかの頂点への距離を求めていけばよいので、DFS,BFS,ダイクストラ法等を利用すればよいです。

感想

この手の問題をしっかりと処理できるのはいい傾向ですが、BFSでいい場面でダイクストラを書くことが多い気がするので、そういう部分で少しでもバグを生む可能性を減らしていけたらなぁと思います。

ABC126 C - Dice and Coin

問題
提出コード

解法

サイコロの目がiであったときにすぬけ君が勝つためには、Kを超えるまでコインの表を出し続ける必要があります。
この回数をc_{i}とすると、これはiKを超えるまで2倍しつつカウントしていけば求めることができます。
ということで、iを出した時にすぬけ君が勝つ確率は\frac{1}{2^{c_{i}}}になります。
あとは、この和を取りNで割ることで、答えを求めることができます。

感想

long doubleで精度が足りるのかがわからず、とりあえず出しました。通ってよかったです。
10^{9}と言われるとビクビクします。

CPSCO2019 Session3 E - Enumerate Xor Sum

問題
提出コード

解法

kのときの答えを求めてみます。
Xについては、A_{i}の累積xorをとっておくことでO(1)で求めることができるので割愛します。
A_{i}Xのxorを取った値をYとすると、xorの定義から、それぞれの桁について、A_{i},Xの立ってるビットの個数が1ならばYのその桁は1、そうでなければ0となります。
Xについて立っているビットは最初から決まっているので、A_{i}について、それぞれの桁で立っているビット、立っていないビットの個数が全部で何個あればいいか、というのがわかればよいことになります。
ということは、A_{1}からA_{k}までのそれぞれのビットについて、立っている個数と立っていない個数を調べれば、Xのビットによって場合分けをして、2^{p}を表すビットの部分はA_{1} xor X +... + A_{k} xor X全体で何回足されるか、というのが計算できるようになります。

感想

桁でわける、という典型を思い出したらすんなり解けたのでよかったです。 実装もバグらせなかった(記憶)ので満足かなと思います

diverta 2019 Programming Contest D - DivRem Number

問題
提出コード

解法

問題の条件を整理すると、
N \  mod \  m = xとして、

  • m \times x + x = N

となるので、つまり、

  • (m+1)x = N

となります。
ということで、 m \gt 0かつNを割り切るようなmの総和が答えとなるので、O(\sqrt{N})で約数を列挙し、その総和を求めれば良いです。

感想

割り算の式を思い出すと、ぱっと解ける問題でした。
結構な速度で解けたので満足です。