AISing Programming Contest 2019 C,D,E問題メモ

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

C - Alternating Path

• $H \times W$ の盤面がある
• 各マスは白か黒に塗られていて、各マスの色は入力として与えられる
• 白と黒を交互に踏んで上下左右に移動したい
• そのような移動を繰り返して行き来できる（黒マス, 白マス）の組の個数を答えよ
• $1 \le H,W \le 400$

あるマスから到達できるマスは、その中の他のマスから出発しても、同じ組み合わせに行き来できる。

■□■□    ❶①❷②  ❶から出発して行けるマスを○にした
□■□□    ③❸④□
□□■■ → □⑤❹■  ①②❷❸などから出発しても、同じ範囲に行けるし、同じ範囲にしか行けない
□□■□    □□■□

その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。

左上から順に1マスずつ見ていき、まだ未探索のマスがあれば、そこから探索を開始する。黒・白マスの数を数えながら行けるところまで行き、それ以上どこにも行けなくなったら黒の数×白の数を答えに加算する。

一度探索したマスはそれ以降調べる必要は無い。

❶①❷②    済済済済
③❸④□    済済済□ ←次はここから探索スタート
□⑤❹■ → □済済■
□□■□    □□■□

経路探索で使う「このマスは訪れたか？」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。

D - Nearest Card Game

• 互いに異なる整数 $A_1 \lt A_2 \lt ... \lt A_N$ が書かれた $N$ 枚のカードが場にある
• 先手と後手の2人が順にカードを取っていく
  • 開始前に、ある整数 $x$ を決める
  • 先手は、その時に場にある最も大きいカードを取る
  • 後手は、その時に場にある最も $x$ に近いカードを取る。同率の場合は小さい方を取る
• $Q$ 個のクエリが与えられる
  • $i$ 番目のクエリでは $X_i$ が与えられる
  • 各クエリについて、$x=X_i$ とした場合に先手が取るカードの合計点を求めよ
• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$

N = 10
A =  3  5  7  9 11 13 15 17 19 21

x = 10 のとき
先手: 21 19 17 15  5  → 77
後手:  9 11  7 13  3

まず、$x$ が小さい時から大きい時にどうなっていくかを考えると、上記の例を再利用して、

（カードを取る順番では無く、最終的に取ることになるカードを昇順に並べている）
x = 1 のとき
先手:                13 15 17 19 21
後手:  3  5  7  9 11

x = 10 のとき
先手:     5             15 17 19 21
後手:  3     7  9 11 13

x = 13 のとき
先手:     5     9          17 19 21
後手:  3     7    11 13 15

x = 21 のとき
先手:     5     9    13    17    21
後手:  3     7    11    15    19

$x=1$ のとき綺麗に大小で2分割された状態から、数値が小さい方から順に交互になり始め、$x=21$ だと完全に交互になっている。

この変化する境界を探りたい。

そもそもなんで取るカードの組が変化するかというと（$x=1→10$ の変化を例に）$x$ がある程度大きくなると、後手はそれまで取っていた小さい方のカード（5）ではなく、先手が取っていた大きいカード（13）を先手より先に取るようになるから。

x = 10
先手:                   15 17 19 21 (4手目まで)
後手:        7  9 11                (3手目まで)
場  :  3  5          13
          ~          ~~
xがある値未満までは5の方を先に取っていたが、
ある値以上では13の方を先に取るようになる

その境界は、ずばり5と13の中間である9である。（同率の場合は小さい方を取るため、x=9までは5を先に取る）

$x=10$ 以上では、先手が取る合計は $13-5=8$ だけ減少する。

これを繰り返して境界と、その境界での先手の合計点を確定できる。

ただし、どのカードが入れ替わるかに少し注意。

上の例を見ても分かるが、$A_i$ が小さい方から半分までのカードの中では、先手は、取るとしても大きい方から数えて奇数枚目のカードしか取らない（5,9を取り、3や7や11を取ることは無い）。取り方のルールから考えると、先手が半分以下のカードを取る時は、それより大きいカードが全て取られ、それ以下のカードが全て残っている状態だから。

なので、次に先手と後手で取るカードが入れ替わるのは、9と15である。その後、13と17、17と19と続く。要は入れ替わるカードの $i$ が、数字の小さい方は2つずつ、大きい方は1つずつ大きくなる。

変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時の先手の合計点で初期化する。

クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。

最初に入れ替わるカードを特定する。後手→先手になるカードのindexを$l$とすると、$N$ が奇数なら$l=0$、偶数なら$l=1$。先手→後手になるカードのindexを$r$とすると、$r=\frac{N}{2}$。

境界を小さい方から1つ確定する。$\frac{A_l+A_r}{2}$ となる。$x$がこの値以下だと、先手の合計点は現在の$tmp$となる。

ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$

$l$ を2、$r$ を1加算し、$l=r$ になる直前まで繰り返す。

最後まで残ったクエリは、$x=21$の様に完全に交互になる。

ソートせずに、境界を事前計算しておいてクエリ毎に二分探索でもよいが、多分Pythonだと遅い。

E - Attack to a Tree

• $N$ 頂点の木があり、$i$ 番目の辺は $(U_i,V_i)$ を結んでいる
• 各頂点には $A_1,A_2,...,A_N$ のゼロでない値が決められている
• 辺を切って、全ての連結成分が以下のいずれかの条件を満たすようにしたい
  • 連結成分内に正の値しかない
  • 連結成分内の値の合計が負
• 切るべき辺の最小数を求めよ

二乗の木DPというやつを使う。

• 二乗の木 DP - (iwi) ｛ 反省します - TopCoder部

• 根を決めて、葉から親に向かって統合していく木のDP
• 統合するときに、2つの部分木のサイズを $|l|,|r|$ とすると、$O(|l| \times |r|)$ の計算量がかかる
• 全体の計算量は、統合が $O(N)$ 回行われ、1回毎に頂点数×頂点数の計算をするのだから、あわせて $O(N^3)$ ？？
• だが、頂点数は最初の方は必ず小さいので、均すと実は $O(N^2)$ で行けるんだよーというテクニック

• 木上の何かの数を数える問題で使うことがある

今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。

• (A) $DP1[v][i]=$
  • 頂点 $v$ を根とする部分木で、
  • 今まで切った辺が $i$ 本の時の、
  • $v$ を含む連結成分の頂点の値が全て正であるような切り方の中で
  • $v$ を含む連結成分の和の最小値
• (B) $DP2[v][i]=$
  • 頂点 $v$ を根とする部分木で、
  • 今まで切った辺が $i$ 本の時の、
  • $v$ を含む連結成分はどうなっててもいいので、
  • $v$ を含む連結成分の和の最小値

ただし、$v$ を含む連結成分“以外”は、条件を満たすように切られているものとする。

$i$ の範囲の上限は、部分木のサイズとなる。

(B)では、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。

本来は(A)の場合は和は関係ないので、$i$ 本の時にできるかできないかのみ保持しておくだけでよかったらしい。

DPの中身の例
  v以下の部分木の辺数が3なので、DP[v][i] は i=0..3 の値をとる
                   v  →根
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

DPの更新を楽にするため、「不可」を示す数を極端に大きな数(inf)とする。（頂点の和になり得ない数。全頂点が最大値の$10^9$であり、$N=5000$ なので、$5 \times 10^{12}$ より大きい数） すると、上の例の DP1[v][1] のように、不可な切り方と可能な切り方が混在する場合でも、可能な切り方同士の時と同様 min を取ることで更新が行える。

葉頂点 $w$ の場合、1頂点のみなので次のようなDPとなる。

• $w$ が正の場合
  • $DP1[w][0] = A_w$
  • $DP2[w][0] = A_w$
• $w$ が負の場合
  • $DP1[w][0] =$ 不可
  • $DP2[w][0] = A_w$

葉以外の頂点 $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$ で切断可能な形でないといけない

これで欲しい情報が手に入った。