2020-03-28

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$ それぞれは和と積で構成されているので、今みている頂点から根を子へうつす際に、今見ている頂点についての値を、全頂点についての計算から、うつす子の値を除いたものに計算しなおせばよいです。

2020-03-19

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

構築

問題
 提出コード

問題概要

$n$ 要素の数列 $a$ と、 $m$ 要素の数列 $b$ が与えられます。
$n$ 行 $m$ 列の行列で、それぞれの行について、全要素の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,b$ で1となっている要素の個数が奇数個であるため、上記のような構築をすればよいです。
$a$ の総和、 $b$ の総和が偶数の場合
この場合は少々厄介です。
単純な構築ができなかったため、どこかに値を押し付けて、最後に微調整を加えることを考えます。
すると、
$(1,b_{i})$ を、 $b_{i}$ と一致させる
$(a_{i},1)$ を、 $a_{i}$ と一致させる
とすると、 $a_{1},b_{1}$ 以外はうまく構築できます。
あとは最後に微調整をすればよく、 $(1,1)$ を $a_{1} \ xor \ b_{1}$ とすればよいです。

感想

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

いやこれ文章に起こしたら普通に正しかった https://t.co/xvelOu9ldK
— かっつ (@_KKT89) 2020年3月15日

2020-03-16

構築問題メモ

構築まとめ

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

www.hamayanhamayan.com

2べきを考える
- +1および×2の遷移を作成して任意の値を構築
- その他
  - ARC102 D - All Your Paths are Different Lengths
特徴のあるグラフをベースに考える
XOR
- Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix
未分類
- 順列の和差昇順ペアを作成

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

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

第一回日本最強プログラマー学生選手権-予選- D - Classified

D - Classified

二部グラフになればよく、頂点を決め打って奇数距離同士を結ぶ、偶数同士は別のレベルで結ぶ、を繰り返します。ビットを利用すると構築が楽。

XOR

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

emtubasa.hateblo.jp

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

未分類

順列の和差昇順ペアを作成

差が昇順
$N = 2M + 1$ のとき、 $M$ の偶奇で場合分け
E - Rotation Matching
やることはどちらも同じで、前半部分で差が偶数のペア、後半部分で差が奇数のペアを作成する
和が昇順
こちらは $N$ の偶奇で場合分け( $2N$ でペアを作成)
E - Non-triangular Triplets
偶数の場合は $x,x,x+2,x+2...$ という形でならぶ(奇数は等差)

TODO 昔の記事をまとめる

2020-03-12

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

動的計画法(DP)

問題
 提出コード

解法

$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)$ によって問題なく最小値を取り出すことができます。

2020-03-06

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

動的計画法(DP) Binary Indexed Tree(BIT)

問題
 提出コード

解法

添え字は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-1$ は $i-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})$ が答えになります。

2020-02-22

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体のうち、よりレベルが上がる方を選択して倒します。
これを繰り返します。

2020-02-21

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

木上のナップサック動的計画法(DP)

問題文
 提出コード

解法

解説の通りこちらを参考にして通しました。
再帰で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])$ で更新します。