ツバサの備忘録

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

ABC160 F - Distributing Integers

問題
提出コード

解法

k = 1のみの場合について答えることができればあとはうまく伝播させて全方位木DPにしてしまえばよいので、k = 1の場合を考えます。

  • dp[i] = iを根とする部分木についての、数字の配置パターン数

  • c_i = iを根とする部分木の頂点数

とします。cの計算方法については、よくある問題なので省略します。
数字の配置パターン数、というのは、その部分木に存在する頂点の数字を並び替えた数列のパターン数です。
dp[i]について考えるとき、子の数列それぞれの要素をいったん同じものとみなして並べ方を考え、最後に子の数列それぞれのパターン数をかければいいことになります。
子それぞれの数列を持ってきて、マージソートのようにしてマージするパターン数がわかれば、iの子の集合をSとして、
(マージのパターン数) \times \prod_{j \in S}{dp[j]}
となります。
マージのパターン数は、同じものを含む順列について考えていることになるので、

同じものがあるときの順列

ここを参考にすればよく、
\displaystyle dp[i] = \frac{(c_{i}-1)!}{\prod_{j \in S}{c_{j}!}} \times \prod_{j \in S}{dp[j]}
となります。
これでk = 1の場合について解けました。
あとは全方位木DPを用いればよく、c,dpそれぞれは和と積で構成されているので、今みている頂点から根を子へうつす際に、今見ている頂点についての値を、全頂点についての計算から、うつす子の値を除いたものに計算しなおせばよいです。

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

問題
提出コード

問題概要

n要素の数列aと、m要素の数列bが与えられます。
nm列の行列で、それぞれの行について、全要素のxorをとるとaに、それぞれの列について全要素のxorをとるとbになるようなものが存在するならば1つ求めてください。

解法

行う操作がxorなので、全要素を2進数の桁ごとに見て、最後に合算すればよいことがわかります。
ので、これ以降はa,bが0,1からなる数列で、行列も0,1からなるものを求めることだけを考えればよいです。
構築できない条件を探してみます。
0,1からなるということと、xorが絡んでいることから、偶奇に着目します。
すると、数列aの総和と、bの総和の偶奇が異なる場合、構築できないことがわかります。
数列aの各値は、その行に存在している値の総和の偶奇と一致するように構築する必要があります。ということは、aの総和は、行列の要素全てに対する総和の偶奇と一致しているはずです。
このことはbにも同様のことが言えます。
よって、行列全体の総和の偶奇は、aの総和の偶奇と一致していて、かつ、bの総和の偶奇と一致している必要があります。
ということで、aの総和とbの総和の偶奇が一致しない場合には構築できないことがわかりました。
では、一致している場合には構築できるかどうか、を見ていきます。
わかりやすく、aの総和の偶奇で場合分けをします。

  • aの総和、bの総和が奇数の場合
    これはすごくシンプルで、(i,j)の値を決める場合、a_{i} = b_{j} = 1であれば1、それ以外なら0とすればよいです。
    a_{i},b_{j}の要素が1の際、その行(列)で1となっている要素の個数が奇数個になっている必要がありますが、a,b1となっている要素の個数が奇数個であるため、上記のような構築をすればよいです。

  • aの総和、bの総和が偶数の場合
    この場合は少々厄介です。
    単純な構築ができなかったため、どこかに値を押し付けて、最後に微調整を加えることを考えます。
    すると、
    (1,b_{i})を、b_{i}と一致させる
    (a_{i},1)を、a_{i}と一致させる
    とすると、a_{1},b_{1}以外はうまく構築できます。
    あとは最後に微調整をすればよく、(1,1)a_{1} \ xor \ b_{1}とすればよいです。

    感想

    こんな構築もあるみたいです。すごい。

構築問題 メモ

構築の思考パターンメモです。主にはまやんさんの構築まとめに載っている問題をを埋めていきます。

www.hamayanhamayan.com

2べきを考える

+1および×2の遷移を作成して任意の値を構築

問題
提出コード
既にある文字列に対して、先頭の文字を両端に追加する→×2
既にある文字列に対して、先頭の文字と異なる文字を両端に追加する→+1
の操作となります。
解説にもあるように、aTa|b|aTaのようなケースが作成できてしまうと、数が増えてしまうので、Tが回文とならないようにする必要があります。これは、文字の種類を3種類以上用意して、ローテーションで新しい文字を割り振ればOKです。
構築の実装は、一番上のビットから順番に見ていき、

  • 今見ているビットが立っている→ビットを立てる(+1の操作)

  • 今見ているビットが立っていない→ビットを立てない(操作なし)

を行い、その後で右のビットにうつる際に、×2の操作を行えば構築完了です。
N=1のケースや一番最初に追加する文字の選択に気を付ければ終わりです。初めに1文字何か入れておけば問題ないです。

その他

ARC102 D - All Your Paths are Different Lengths

ARC102 D - All Your Paths are Different Lengths - ツバサの備忘録
2^{i}までを上手く構築し、残りの[2^{i} + 1,L)についてもそれを利用して構築します。

特徴のあるグラフをベースに考える

完全グラフ

Tenka1 Programmer Contest (2018) D - Crossing

Tenka1 Programmer Contest (2018) D - Crossing - ツバサの備忘録

完全グラフそのものです。

スターグラフ

ABC132 E - Friendships

問題
提出コード
スターグラフをまず構築した後に、問題の条件を満たすまで辺を追加しつづけます。

N頂点M辺の単純連結無向グラフが与えられた場合に、適当な全域木を取って考えると見通しがよくなることがあります。

WUPC2019 C - Permutation City

WUPC2019のお話(解法編) - ツバサの備忘録

再帰DFSをしつつ、葉の方から、今見ている頂点とその子に対して処理を行います。

AGC035 B - Even Degrees

問題
提出コード
こちらも同様、葉から見ていき、今見ている頂点の子の情報を集めた後、辻褄が合うように自身の状態を確定します。

ABC155 F - Perils in Parallel

問題
提出コード
前半の難しいパートを終えると、上の問題に帰着できます。

二部グラフ

日立製作所 社会システム事業部 プログラミングコンテスト2020 C - ThREE

問題
提出コード
適当に根を決めると、そこからの距離の偶奇で置くべき数字が変わってきます。
そこで二部グラフになっていることがわかり、あとは頂点数によって構築方法を場合分けします。

XOR

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

emtubasa.hateblo.jp

構築の典型というよりかは、XORの典型を用いるとスムーズにいく、という感じでしょうか。
しいて言うなら、とりあえずシンプルに構築して、最後に微調整を行う という考えがポイントでしょうか…?

未分類

TODO 昔の記事をまとめる

JOI2017/2018 予選 D - 水ようかん (Mizuyokan)

問題
提出コード

解法

  • dp[i][j] = i番目までのようかんを切り終えて、ピースの最小値がjになるように切り分けたときに取り得る"ピースの最大値"の最小値

とします。こうすることで、答えはmin(dp[n][j] - j)で求めることができます。
すると、[k,i]でピースを作成すると仮定した際に遷移がどうなるかを考えればよいため、S_{l,r} = \sum_{i = l}^{r}L_{i}として、
dp[i][j]  = min(max(dp[k-1][j],S_{k,i})) (ただし j \leqq S_{k,i} を満たす)
と考えたくなります。初期値はdp[i][S_{1,i}] = S_{1,i}です。
しかし、このままではおそらくACすることはできません(参考)

以下のようなケースを考えます。

2
10
1

これは、サンプル2のようかんを左右反転させただけなので、明らかに答えは9です。
しかし、上のままの解法だと、おそらく答えが合わないかと思います。
この原因は、上のDP解が左端のようかんが最小値になる場合のみについて考えていることによるものです。
このケースのように、右端が最小のピースになったり、3つ以上に切り分けたうちの真ん中が最小になるケースも存在します。
これを解消するために、DPの定義を少し書き換えます。

  • dp[i][j] = 最後まで切り分けた結果、ピースの最小値がj以上になると仮定したときの、i番目までのようかんを切り終えたときに取り得る"ピースの最大値"の最小値

すると、遷移はそのまま、初期値はdp[0][j] = 0とすることで、このDPを計算できます。
答えも最初と同様min(dp[n][j] - j)で求めることができます。が、仮定と矛盾する場合、つまりピースの最小値がj以上となる切り分け方が存在しなかった場合は排除しなければなりません。この場合は、dp[n][j] = S_{1,n}になっているため、容易に場合分けをして排除することができます。
切り分け方は存在するが、ピースの最小値がjぴったりにならないものも存在します。が、今回はj以上、という仮定を置いているので、jぴったりにならない場合は、j+1以降のどこかでぴったりになるはずです。dp[n][j] - jは、jが大きい方が値が小さくなるので、min(dp[n][j] - j)によって問題なく最小値を取り出すことができます。

AOJ 2312 - 魔法少女さやかちゃん

問題
提出コード

解法

添え字は0-indexedとします。 区間の総和は、BITや累積和を用いて高速に取得できるものとします。
P_{l,r} = \frac{\sum_{i = l}^{r}S_{i}}{L}
とします。
仮に円環でなく直線上に音符を配置しているとした場合、明らかに音符をK_{i}の昇順に配置するのが最適です。
しかし今回は、音符を並べて円環を作成しています。この場合、
(K_{i}の最小値)...(その他の音符)... (K_{i}の最大値 )...(その他の音符)...(K_{i}の最小値)
となっているはずです。
つまり、円環を2つに分け、二本の直線とみなすと、それぞれが広義単調増加(減少)になっていればよいことがわかります。
あとは、K_{i}を昇順でソートし、二本の直線のうちどちらに配置するか、ということを考えればいいことになります。ということで、以下のようなDPを考えます。

  • dp[i][j] = 片方の右端がi、もう片方の右端がjになっているときの最小コスト(ただし、i = j = 0もしくは i \gt j )

初期値はdp[0][0] = 0です。 dp[i][j]の遷移は、場合分けで表されます。

  • i \neq j-1の場合
    この場合、i-1と同じ直線にiを配置することになります。よって、
    dp[i][j] = dp[i-1][j] + P_{i-1,i}
    となります。

  • i = j-1の場合
    この場合、i-1を配置した直線とは違う直線にiを配置します。
    つまり、iと隣接する音符は、[0,i-1]のいずれか(i-1i-1 = 0のときのみ可能性が存在します)であるため、
    dp[i][j] = min(dp[i-1][x] + P_{x,i}) (ただし0 \leqq x \leqq i-1)
    となります。

これを計算すると、min(dp[n-1][i] + P_{i,n-1})が答えになります。

AOJ 2826 - ゲームバランス

問題文
提出コード

解法

倒すまでに最小M回以上かかるなかで最大となるXを二分探索で求めます。
ゲームクリアできない場合、1 + X \leqq s_{1}になります。二分探索時は、ゲームクリアまでにM回以上かかっている、と仮定します(最後に求まったXを確認した場合にゲームクリアできなかった場合は答えが-1になります)。
以降は、ゲームクリアができると仮定して話を進めます。
そして、そもそも、X=1の場合に戦闘がM回未満になる場合は-1になります。これを排除しておきます。
Xを固定した際に、何回かかるかを調べます。
現在のレベルをlとします、初期値は1です。
ここから、レベルがlの際に一番レベルが上がる敵を毎回倒すことをシミュレートします。M回を超えたらそれ以上シミュレートする必要がないので、そこで打ち切ります。s_{N}を倒せるレベルになっていたら、その場合もシミュレートを終了します。
レベルが一番上がるのは、lとの差が最も小さい強さを持つ敵です。
そこで、強さl以上を持つ敵の中で一番弱い敵を二分探索で調べます。
そして、その敵が倒せるかどうかを判定します。
倒せる場合はその際に上がるレベルをメモします。
次に、先ほど調べた敵の1つ手前にいる敵について、上がるレベルをメモします。この際は、自分のレベルがlのため確実に倒せることから、倒せるかどうかの判定をする必要はありません。
そして、今調べた2体のうち、よりレベルが上がる方を選択して倒します。
これを繰り返します。

AOJ 2966 - G トレジャーハンター (Treasure Hunter)

問題文
提出コード

解法

解説の通りこちらを参考にして通しました。
再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点pを使用した際の最適解配列X_{p0}と、使用しなかった際の最適解配列X_{p1}を返します。
今いる頂点をpとします。子をaとします。

  • 1つめの子に対する再帰
    引数で渡された配列Vをそのまま子の引数にします。
    戻ってきた値について、
    X_{p0}の処理は、それぞれの添え字iについて、X_{p0}[i] = max(V[i],X_{a0}[i],X_{a1}[i])で更新します。
    X_{p1}についての処理は、今いる頂点とa両方を使用するときは、コストc_{pa}がかかることに注意し、X_{p1}[i] = max(V[i],X_{a1}[i-c_{pa}])で更新します。

  • 2つ目以降の子に対する再帰
    X_{p1}について考えます。
    X_{p1}をまず引数にして再帰します。
    そして、先ほどとほぼ同様の処理、具体的にはX_{p1}[i] = max(X_{p1}[i],X_{a1}[i-c_{pa}])による更新をします。
    X_{p0}について考えると、知りたいのは、aを根とする部分木についての最適解であるため、Dという配列を用意し、全てを0で初期化して、これを改めて引数として再帰します。
    そして、得られた結果について、 X_{p0}[i] = max(X_{p0}[i],X_{a0}[i],X_{a1}[i])で更新します。

これらの処理が済んだら、pについて使用する方はお宝の価値を加算して、X_{p0},X_{p1}を戻り値として返します。