目次
文書の過去の版を表示しています。
AISing Programming Contest 2019 C,D問題メモ
C - Alternating Path
問題
- $H \times W$ の盤面がある
- 各マスは白か黒に塗られていて、各マスの色は入力として与えられる
- 白と黒を交互に踏んで上下左右に移動したい
- そのような移動を繰り返して行き来できる(黒マス, 白マス)の組の個数を答えよ
- $1 \le H,W \le 400$
解法
あるマスから到達できるマスは、その中の他のマスから出発しても、同じ組み合わせに行き来できる。
■□■□ ❶①❷② ❶から出発して行けるマスを○にした □■□□ ③❸④□ □□■■ → □⑤❹■ ①②❷❸などから出発しても、同じ範囲に行けるし、同じ範囲にしか行けない □□■□ □□■□
その中で条件を満たす(黒マス、白マス)の組の個数は、「黒マスの個数×白マスの個数」となる。
左上から順に1マスずつ見ていき、まだ未探索のマスがあれば、そこから探索を開始する。黒・白マスの数を数えながら行けるところまで行き、それ以上どこにも行けなくなったら黒の数×白の数を答えに加算する。
一度探索したマスはそれ以降調べる必要は無い。
❶①❷② 済済済済 ③❸④□ 済済済□ ←次はここから探索スタート □⑤❹■ → □済済■ □□■□ □□■□
経路探索で使う「このマスは訪れたか?」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。
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$
$l$ を2、$r$ を1加算し、$l=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)))