AISing Programming Contest 2019 参加記録

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

C - Alternating Path

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

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

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

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

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

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

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

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$

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

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