目次
文書の過去の版を表示しています。
AISing Programming Contest 2019 参加記録
C - Alternating Path
問題
- $H \times W$ の盤面がある
- 各マスは白か黒に塗られていて、各マスの色は入力として与えられる
- 白と黒を交互に踏んで上下左右に移動したい
- そのように移動できる（黒マス, 白マス）の組の個数を答えよ
- $1 \le H,W \le 400$
解法
あるマスから到達できるマスは、その中の他のマスから出発しても、同じ組み合わせに行き来できる。
■□■□ ❶①❷② ❶から出発して行けるマスを○にした □■□□ ③❸④□ □□■■ → □⑤❹■ ①②❷❸などから出発しても、同じ範囲に行けるし、同じ範囲にしか行けない □□■□ □□■□
その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。
一度探索したマスはそれ以降調べる必要は無い。
❶①❷② 済済済済 ③❸④□ 済済済□ ←次はここから探索スタート □⑤❹■ → □済済■ □□■□ □□■□
経路探索で使う「このマスは訪れたか？」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。
h, w = list(map(int, input().split()))
sss = ['x' * (w + 2)] + list('x' + input() + 'x' for _ in range(h)) + ['x' * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
ans = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(i, j):
w_cnt, b_cnt = 0, 0
q = [(i, j, sss[i][j] == '.')]
while q:
y, x, is_white = q.pop()
if checked[y][x]:
continue
checked[y][x] = True
if is_white:
w_cnt += 1
else:
b_cnt += 1
for di, dj in move:
ni = y + di
nj = x + dj
if checked[ni][nj]:
continue
nc = sss[ni][nj]
if nc == 'x':
continue
elif (nc == '.') == is_white:
continue
else:
q.append((ni, nj, nc == '.'))
return w_cnt * b_cnt
for i in range(1, h + 1):
for j in range(1, w + 1):
if checked[i][j]:
continue
ans += dfs(i, j)
print(ans)
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だと遅い。
import sys
n, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
xxx = sorted(((int(line), i) for i, line in enumerate(sys.stdin.readlines())), reverse=True)
total = sum(aaa)
tmp = sum(aaa[n // 2:])
ans = [sum(aaa[-1::-2])] * q
if n % 2 == 0:
l, r = 1, n // 2
else:
l, r = 0, n // 2
while l < r:
al, ar = aaa[l], aaa[r]
m = (al + ar) // 2
while xxx and xxx[-1][0] <= m:
x, i = xxx.pop()
ans[i] = tmp
if not xxx:
break
tmp += al - ar
l += 2
r += 1
print('\n'.join(map(str, ans)))
