Loading [MathJax]/jax/output/CommonHTML/jax.js

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/04] ikatakosprogramming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/05] (現在) – [解法] ikatakos
行 225: 行 225:
  
   * 木上の何かの数を数える問題で使うことがある   * 木上の何かの数を数える問題で使うことがある
-  * 一方の部分木にもう一方を繋ぐ or 繋がない で状態遷移する 
  
 今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。 今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。
行 232: 行 231:
     * 頂点 v を根とする部分木で、     * 頂点 v を根とする部分木で、
     * 今まで切った辺が i 本の時の、     * 今まで切った辺が i 本の時の、
-    * v を含む連結成分の__頂点の値が全て正であるような切り方__の中で+    * v を含む連結成分の__頂点の値が全て正であるような切り方__の中で
     * v を含む連結成分の和の最小値     * v を含む連結成分の和の最小値
   * (B) DP2[v][i]=   * (B) DP2[v][i]=
行 240: 行 239:
     * v を含む連結成分の和の最小値     * v を含む連結成分の和の最小値
  
-ただし、v を含む連結成分以外は、条件を満たすように切られているものとする。+ただし、v を含む連結成分"以外"は、条件を満たすように切られているものとする。
  
-条件1つでは、連結成分和が負にならないといけないので、辺を切った数が同じなら、和出来るだけ低く保つのが必ずよい。 +i 範囲上限は、サイズとなる。
-「連結成分内の頂点が全て正」の場合は和は関係ないので DP1 は必ずしも最小値でなくてもよいような気も一瞬するがこれは暫定であるため、将来的に負の頂点と統合されて「連結成和が負」の方の条件で切られるこなるかも知れない。 +
-よって両方とも、和を低く保つようにDPを行うのがよい+
  
 +(B)では、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。
  
-FIXME+本来は(A)の場合は和は関係ないので、i 本の時にできるかできないかのみ保持しておくだけでよかったらしい。
  
 +<code>
 +DPの中身の例
 +  v以下の部分木の辺数が3なので、DP[v][i] は i=0..3 の値をとる
 +                    →根
 +4 --- -7 --- 3 --- 5 ...    DP1[v][0]  = 不可  DP2[v][0]  = 5
  
 +4 -|- -7 --- 3 --- 5 ...    DP'1[v][1] = 不可  DP'2[v][1] = 1
 +4 --- -7 -|- 3 --- 5 ...    DP'1[v][1] = 8     DP'2[v][1] = 8
 +4 --- -7 --- 3 -|- 5 ... × 切り方が条件を満たしていない
 +                         → DP1[v][1]  = 8     DP2[v][1]  = 1
  
 +4 -|- -7 -|- 3 --- 5 ...    DP'1[v][2] = 8     DP'2[v][2] = 8
 +4 -|- -7 --- 3 -|- 5 ...    DP'1[v][2] = 5     DP'2[v][2] = 5
 +4 --- -7 -|- 3 -|- 5 ...    DP'1[v][2] = 5     DP'2[v][2] = 5
 +                         → DP1[v][2]  = 5     DP2[v][2]  = 5
  
 +4 -|- -7 -|- 3 -|- 5 ...    DP1[v][3]  = 5     DP2[v][3]  = 5
 +</code>
  
 +===DP===
 +
 +DPの更新を楽にするため、「不可」を示す数を極端に大きな数(inf)とする。(頂点の和になり得ない数。全頂点が最大値の109であり、N=5000 なので、5×1012 より大きい数)
 +すると、上の例の ''DP1[v][1]'' のように、不可な切り方と可能な切り方が混在する場合でも、可能な切り方同士の時と同様 ''min'' を取ることで更新が行える。
 +
 +==葉==
 +
 +葉頂点 w の場合、1頂点のみなので次のようなDPとなる。
 +
 +  * w が正の場合
 +    * DP1[w][0]=Aw
 +    * DP2[w][0]=Aw
 +  * w が負の場合
 +    * DP1[w][0]= 不可
 +    * DP2[w][0]=Aw
 +
 +==葉以外==
 +
 +葉以外の頂点 v の場合、次のように子供の結果と統合する。
 +
 +まず、統合元を用意する。葉頂点と同じように作る。この時、暫定のDPを、DP1[v],DP2[v] と表記することにする。
 +
 +子を1つずつ統合する。子の1つを u とし、DP1[u],DP2[u]DP1[v],DP2[v] に統合する処理を考える。
 +
 +  * サイズ
 +    * 新しい DP1[v] のサイズは len(DP1[v])+len(DP1[u]) となる
 +    * INFで初期化する
 +  * DP1
 +    * v を含む連結成分の全頂点が正でないといけないので、v も正である必要がある
 +      * v が負なら DP1[v] は全てINF
 +    * u からの辺をくっつける時、DP1[v][i+j]DP1[v][i]+DP1[u][j]
 +    * u からの辺で切る時、DP1[v][i+j+1]DP1[v][i]
 +      * ただし DP1[u][j]<INF、つまり u で切断可能な形でないといけない
 +  * DP2
 +    * u からの辺をくっつける時、DP2[v][i+j]DP2[v][i]+DP2[u][j]
 +    * u からの辺で切る時、DP2[v][i+j+1]DP2[v][i]
 +      * ただし DP2[u][j]<0、つまり u で切断可能な形でないといけない
 +
 +これで欲しい情報が手に入った。
  
 <sxh python> <sxh python>
programming_algorithm/contest_history/atcoder/2019/0112_aising2019.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0