差分

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

--- programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/12] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/13] – ikatakos
@@ 行 13: / 行 13: @@
   * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる
   * 白と黒を交互に踏んで上下左右に移動したい
-  * そのような移動で行き来できる（黒マス, 白マス）の組の個数を答えよ
+  * そのように移動できる（黒マス, 白マス）の組の個数を答えよ
   * $1 \le H,W \le 400$
@@ 行 25: / 行 25: @@
   □□■□    □□■□
-その中での（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。
+その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。
 一度探索したマスはそれ以降調べる必要は無い。
@@ 行 34: / 行 34: @@
   □□■□    □□■□
-経路探索でよく使う「このマスは訪れたか？」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。
+経路探索で使う「このマスは訪れたか？」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。
 <sxh python>
@@ 行 108: / 行 108: @@
 ==== 解法 ====
-二分探索で解いたという感想が目立つが、使わなくても解ける。（汎用性は無さそう）
 まず、$x$ が小さい時から大きい時にどうなっていくかを考えると、上記の例を再利用して、
@@ 行 154: / 行 152: @@
 上の例を見ても分かるが、$A_i$ が小さい方から半分までのカードの中では、先手は、取るとしても大きい方から数えて奇数枚目のカードしか取らない（5,9を取り、3や7や11を取ることは無い）。取り方のルールから考えると、先手が半分以下のカードを取る時は、それより大きいカードが全て取られ、それ以下のカードが全て残っている状態だから。
-なので、次に先手と後手で取るカードが入れ替わるのは、9と15である。その後、13と17、17と19と続く。要は$i$が、小さい方は1個飛ばし、大きい方は1つずつ進む。
+なので、次に先手と後手で取るカードが入れ替わるのは、9と15である。その後、13と17、17と19と続く。要は入れ替わるカードの $i$ が、数字の小さい方は2つずつ、大きい方は1つずつ大きくなる。
 ==実装==
-変数$tmp$を、現在の先手の合計とし、$x=1$の様に完全に2分された時のスコアで初期化する。
+変数$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$となる。
-境界を小さい方から1つずつ確定する毎に、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、$tmp$を更新する。
+ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$
 最後まで残ったクエリは、$x=21$の様に完全に交互になる。
+ソートせずに、境界を事前計算しておいてクエリ毎に二分探索でもよいが、多分Pythonだと遅い。
 <sxh python>