Processing math: 54%

目次

ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)E,F,G問題メモ

ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)

Gみたいな実装をバグらせず書きたいね。

E - K-colinear Line

E - K-colinear Line

問題

解法

K=1 のとき、1点を通る直線は無限にあるのでInfinity。

以下、K2 とする。これならそもそも2点のペアというのが有限個で、2点決めれば直線は1つに決まるので直線も有限個。

直線の方程式は、y=ax+b と表す方法がわかりやすくはあるんだけど、 垂直な線が表現できなかったり、傾き a や切片 b が小数になったりの問題がある。

ax+by+c=0 で表現すると、垂直な線も表現でき、適当に倍化することによって全パラメータを整数にできる。
この (a,b,c) のパラメータ3点セットで直線が一意に決まる。

ただし、同じ直線が違うパラメータにならないよう、以下に注意する。

全2点ペアで、そこを通る直線の (a,b,c) を求め、それごとに個数をカウントしていくと、 たとえば k 点を通る直線なら、k(k1)2 回カウントされるはず。

K(K1)2 回以上カウントされている (a,b,c) の個数が答え。

Python3

F - Keep Connect

F - Keep Connect

問題

解法

きちんと場合分けして遷移の考察を必要とするDP。

縦2~5 [マス or 頂点] 程度で横にだけ長い [グリッド or グラフ] 上の数え上げ問題などは、 左から順に考えて、考慮した中で最後の1列(または何列か)の取り得る状態で場合分けしたDPが解法となる場合がある。

今回の場合は、「i 列目の上・下の頂点が、左上の頂点と連結か?」を考えればよさそう。

 0   1         i
●--○-- .. --◎--
|  |        |
○--○-- .. --◎--

全体を連結にできる可能性が残っている中で、取り得る状態は以下の3つとなる。

たとえば、以下のような状態なら 2:下だけ連結 となる。
だが、この状態からでも i+1 番目以降で上下を連結させれば、全体を連結にすることはできる。

●--○  ○--◎
    |
○--○--○--◎

いずれの場合も、i1 列目以前の頂点は、左上頂点●か、i 列目の頂点◎の、3つのうちいずれかには繋がっていないとダメ。
よって、i1 列目以前の状態を場合分けして管理する必要は無く、条件を満たすもののみ考えればよい。

以下のDPを考える。

初期状態は、左端の縦の1本を残すなら状態0、削除したら状態1なので、それぞれを1、他は0で初期化する。

i+1 番目への遷移は、ii+1 列目にかかる「コ」の字の3辺の削除有無を考える。全通り試しても 23=8 通り。
1個1個試していくと、連結を保ちうるのは

残す辺削除本数遷移
00,1,2→全て0
10→0
10→0
10→0,1→1,2→2
¯¯20→1
_20→2

なので、それぞれの削除本数にも注意して遷移させていくと、 最終的に k=1,2,...,N1 に対する DP[N1][0][k] のそれぞれが答えとなる。

Python3

G - GCD cost on the tree

G - GCD cost on the tree

問題

解法

概要は公式Editorialと同じ。

実装が重ための木DP。でもわりと素直な解法ではあるので、実装力勝負、かも。

木DPで答えを求める方法を検討する。適当に根を決めて根付き木とする。

木DPは、各頂点 v について「子から『何か』を伝えられ、他の子および v 自身の情報とマージして、親に同型の『何か』を伝える」過程の、その「何か」にどういう情報を持たせ、どういう更新を行えばよいかを決めることが基本となる。

DP定義

で、いろいろ考えると(雑な省略)、以下の情報があれば答えを求められることがわかる。

ちょっと入れ子構造がややこしいが、g については取り得る値が飛び飛びなので辞書型で管理する。

グラフ例(丸付き数値はAi)

                 ㉔      {1: [3, 8],  4: [1, 2],  24: [1, 1]}
               /  \
{25: [1, 1]}  ㉕    ㉘   {7: [2, 4],  28: [1, 1]}
                    /\
{21: [1, 1]}       ㉑⑦  {7: [1, 1]}

v の部分木内で完結するコスト

v の全ての子 u=u1,u2,... について DP[u] が計算済みとして、そこから v を含み、v の部分木内で完結するパスのコストを求める。

大別して、以下の2種類のパスのコストを求めることになる。

v を一端とするパスのコスト

v の部分木以下の頂点」と「v」を結ぶパスの分のコストを求める。

説明のため、以下の補助的な情報を定義する。

上のグラフ例で、例えば tmp[㉔][㉘] を求めるとする。

DP[㉘] = {7: [2, 4], 28: [1, 1]} なので、そこに を加えるなら、

もし複数の更新前GCDで、更新後のGCDが同じになったら、単純に合算すればよい。

DP[㉘] の各要素について計算したものをまとめると、tmp[㉔][㉘] = {1: [2, 6], 4: [1, 2]} となる。

すると、「㉘の部分木以下と㉔とを結ぶパス」についてのコストの合計は、 tmp[㉔][㉘]のそれぞれの要素 {g: [c, t]} について、g \times t を合計したものとなる。

つまり、この例では 1 \times 6 + 4 \times 2 = 14 となる。

tmp[㉔][㉕] など㉔の他の子でも同様に求める。

v の子孫同士を結ぶパスのコスト

v の子 u_1 の部分木以下の頂点」と「u_2(\neq u_1) の部分木以下の頂点」を結ぶパスの分のコストを求める。

    v
   / \
 u1   u2
 /\   /\
:: ::

更新後の tmp[v][u_1]tmp[v][u_2] から求める。

両者の要素の組み合わせを二重イテレートで全部試す。
たとえば、u_1 側から \{12: [3,7]\} に該当する頂点、u_2 側から \{18: [5,11]\} に該当する頂点を結ぶとすると、

あとは、該当する全パスの F(○,○) の合計値を知りたいが、定義に立ち戻るとこれはパス上の頂点数なので、

に分けて考えてよい。

u_1 側の 3 個の頂点のうち任意の1つが、u_2 側の 5 個の頂点と結ばれる5種類のパスについて、 その「v より u_2 側だけの延べ頂点数」は 11 個。(各パスに v 自身を含む)
よって 3 個では 33 個。

同様に、u_2 側の 5 個の頂点のうち任意の1つが、u_1 側と結ばれる3種類のパスについて、 「v より u_1 側だけの延べ頂点数」は 7 個。5 個では 35 個となる。

ただし、それぞれの合計には v が重複している。
3 \times 5=15 通りのパスに、1つずつ余分が含まれるので、これを除く。

つまり、15通りのパスの F(○,○) の合計は 33+35-15=53、コストは 6 \times 53 = 318 となる。

一般化すると、\{g_1: [c_1,t_1]\}\{g_2: [c_2,t_2]\} を結ぶパスの総コストは、以下のようになる。

3つ以上の子がある場合

u_1,u_2 についての計算が終わったら、それをマージする。 マージは単純に、同じ g があったら足し合わせ、無ければ作ればよい。

tmp[v][u1]    = {1: [3, 6],  5: [2, 4],  10: [1, 1]}
tmp[v][u2]    = {1: [2, 3],  15: [1, 1]}
↓
tmp[v][u1&u2] = {1: [5, 9],  5: [2, 4],  10: [1, 1],  15: [1, 1]}

そして、tmp[v][u1&u2] と、tmp[v][u3] について同じことを繰り返していけばよい。

マージテクを使えば、多少計算量が落ちるかも。
まぁでも、8秒もあるのでその辺はサボっても間に合いそう。

tmp[v] を使う理由

ここまでの、v の子孫同士を結ぶパスのコストの求め方は、 tmp[v][u_1] などの代わりに DP[u_1] を使っても(細かな計算は変わるが)一応可能である。

ただし、マージする部分でまずい部分が出てくる。

tmpを使えば、マージした後の要素は A_v の約数に限られる(制約の中ではたかだか128個)。

一方 DP をそのまま使った場合、A_v の値が未反映のため、マージ後の要素数が膨れ上がる可能性がある。
このままいくつもの子を二重イテレート・マージすると、TLEとなってしまうケースが存在する。

DP[v] をまとめる

v の子孫同士を結ぶパスのコストを計算する過程で、マージを行った。

上記で述べたマージで、全ての u_i の情報を1つにまとめたら、 そこに、v 自身から始まるパスを表現する \{A_v: [1, 1]\} をマージする。

これが DP[v] となる。(v が葉の場合は、\{A_v: [1, 1]\} がそのまま DP[v] となる)

まとめ

木DPで答えを求める。頂点 v について DP[v] を求める処理は以下の通りである。

まず、各子 u=u_1,u_2,... について、DP[u]v を加えて更新した tmp[v][u] を計算する。
その過程で v を一端としたパスのコストが計算できる。

tmp[v][u_1],tmp[v][u_2],... をマージしつつ、v の子孫同士を結ぶパスのコストを計算する。

1つになるまでマージしたら、v 自身から始まるパスを表現する \{A_v: [1, 1]\} をマージし、DP[v] とする。

木DPが最後まで行われる過程で計算されたコストの総和が、答えとなる。

Python3