ABC351のA~F問題をpythonで解説していきます。
A - The bottom of the ninth
問題
チーム高橋とチーム青木が、チーム高橋を先攻として野球を行なっています。
現在、$9$ 回表までが終了し、$9$ 回裏が始まろうとしています。
試合において、チーム高橋は $i$ 回表 $(1\leq i\leq 9)$ に $A_i$ 点を取り、チーム青木は $j$ 回裏 $(1\leq j\leq 8)$ に $B_j$ 点を取りました。
ここで、$9$ 回表の終了時点でチーム高橋の得点はチーム青木の得点以上です。
チーム青木は $9$ 回裏に最低何点取れば勝利することができるか求めてください。
ただし、$9$ 回裏の終了時点で同点であった場合は引き分けとなり、すなわちチーム青木が勝利するためには $9$ 回裏の終了時点でチーム高橋より真に多くの点をとっている必要があるものとします。
なお、（ある時点における）チーム高橋の得点はそれまでの回の表に取った点数の合計であり、チーム青木の得点はそれまでの回の裏に取った点数の合計です。
考察
チーム青木が逆転するためには、チーム高橋との総得点の差+1点が必要なので、それを計算すればよいです。
コード
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(sum(A) - sum(B) + 1)
B - Spot the Difference
問題
縦 $N$ マス、横 $N$ マスのグリッドが $2$ 個与えられます。それぞれグリッド $A$, グリッド $B$ と呼びます。
グリッドの各マスには英小文字が書かれています。
グリッド $A$ の上から $i$ 行目、左から $j$ 列目に書かれている文字は $A_{i, j}$ です。
グリッド $B$ の上から $i$ 行目、左から $j$ 列目に書かれている文字は $B_{i, j}$ です。
2 つのグリッドは $1$ ヵ所だけ書かれている文字が異なります。すなわち、$A_{i, j} \neq B_{i, j}$ である $N$ 以下の正整数の組 $(i, j)$ はちょうど $1$ 個存在します。この $(i, j)$ を求めてください。
考察
1ヵ所だけ違う場所の座標を答えればいいので、座標を全探索すればよいです。
コード
N = int(input())
A = [list(input()) for _ in range(N)]
B = [list(input()) for _ in range(N)]
for i in range(N):
for j in range(N):
if A[i][j] != B[i][j]:
print(i + 1, j + 1)
exit()
C - Merge the balls
問題
空の列と、$N$ 個のボールがあります。$i$ 個目 $(1\leq i\leq N)$ のボールの大きさは $2^{A_i}$ です。
これから $N$ 回の操作を行います。
$i$ 回目の操作では、$i$ 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。
- 列にあるボールが $1$ つ以下ならば操作を終了する。
- 列にあるボールのうち右から $1$ 番目のものと $2$ 番目のものの大きさが 異なる ならば操作を終了する。
- 列にあるボールのうち右から $1$ 番目のものと $2$ 番目のものの大きさが 等しい ならば、$2$ つのボールを取り除き、「取り除かれた $2$ つのボールの大きさの和」の大きさのボール $1$ つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。
$N$ 回の操作の後で、列にあるボールの数を求めてください。
考察
これは実装問題であり、問題文通りシミュレーションができればよいです。実装にはdequeを使うと直感に合うと思います。
コード
from collections import *
N = int(input())
A = list(map(int, input().split()))
q = deque()
for a in A:
q.append(a)
while len(q) >= 2:
r = q.pop()
l = q.pop()
if l == r:
q.append(l + 1)
else:
q.append(l)
q.append(r)
break
print(len(q))
D - Grid and Magnet
問題
$H$ 行 $W$ 列のマス目があり、いくつか（$0$ 個のこともある）のマスには磁石が置かれています。
マス目の状態は $H$ 個の 長さ $W$ の文字列 $S_1,S_2,\ldots,S_H$ で表され、 $S_i$ の $j$ 文字目が # のとき上から $i$ 行目かつ左から $j$ 列目のマスには磁石が置かれていることを、 . のとき何も置かれていないことを表しています。
高橋君は鉄の鎧を着ており、あるマスにいるとき次のように移動することができます。
- 現在いるマスの上下左右に隣り合うマスのいずれかに磁石が置かれているとき、どこへも移動することができない。
- そうでないとき、上下左右に隣り合うマスのいずれかを選んでそのマスに移動することができる。
ただし、マス目の外に移動することはできない。
磁石が置かれていない各マスについて、そのマスの自由度を、「最初高橋くんがそのマスにいるとき、そこから移動を繰り返して到達できるマスの個数」として定義します。 マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を求めてください。
ただし、自由度の定義において、「移動を繰り返して到達できるマス」とは、最初にいるマスからそのマスまで移動を繰り返して到達する方法（$1$ 回も移動しないものも含む）が $1$ つ以上存在するようなマスのことであり、 最初のマスから始めてすべてのそのようなマスを巡るような移動方法が存在する必要はありません。特に（磁石の置かれていない）各マス自身は、そのマスから「移動を繰り返して到達できるマス」につねに含まれることに注意してください。
考察
全マスそれぞれからスタートして動けるマスをBFS等を使って全探索する方法が思い浮かびますが、これだと何度も盤面全体を探索することがあり、最悪の場合$O(HW*HW)$になる可能性があります。そのため、一度探索したマスは探索しないなどする必要があります。ここで、新たに始発点を決めるたびに探索したマス情報をリセットする必要がある点に注意が必要です。なぜなら、磁石で動けなくなる点は、何度か探索範囲に含められることがあるからです。
コード
from collections import *
dxdy1 = ((0, 1), (0, -1), (1, 0), (-1, 0)) # 上下右左
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
visited = [[0] * W for _ in range(H)]
ans = 0
num = 0
for i in range(H):
for j in range(W):
if S[i][j] == "#" or visited[i][j] != 0:
continue
num += 1
q = deque()
q.append((1, i, j))
cnt = 0
while q:
d, y, x = q.pop()
visited[y][x] = num
cnt += 1
out = False
for dx, dy in dxdy1: # 上下左右磁石判定
nx = x + dx
ny = y + dy
if 0 <= nx < W and 0 <= ny < H and S[ny][nx] == "#":
out = True
if out: # 磁石だったらこれ以上探索できない
continue
for dx, dy in dxdy1:
nx = x + dx
ny = y + dy
if (
0 <= nx < W
and 0 <= ny < H
and S[ny][nx] == "."
and visited[ny][nx] != num
):
visited[ny][nx] = num
q.append((d + 1, ny, nx))
ans = max(ans, cnt)
print(ans)
E - Jump Distance Sum
問題
座標平面上に $N$ 個の点 $P_1,P_2,\ldots,P_N$ があり、点 $P_i$ の座標は $(X_i,Y_i)$ です。
$2$ つの点 $A,B$ の距離 $\text{dist}(A,B)$ を次のように定義します。
最初、ウサギが点 $A$ にいる。
$(x,y)$ にいるウサギは $(x+1,y+1)$, $(x+1,y-1)$, $(x-1,y+1)$, $(x-1,y-1)$ のいずれかに $1$ 回のジャンプで移動することができる。
点 $A$ から点 $B$ まで移動するために必要なジャンプの回数の最小値を $\text{dist}(A,B)$ として定義する。
ただし、何度ジャンプを繰り返しても点 $A$ から点 $B$ まで移動できないとき、$\text{dist}(A,B)=0$ とする。
$\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i,P_j)$ を求めてください。
考察
結論から言うと、xとyが一緒に変化する斜め移動は扱いが大変なので、45度回転させた軸を新たにx軸、y軸と考えるとよいです。これは、$(x,y)→(x+y,x-y)$とすることで実現でき(これからは変換後のx座標、y座標のみ考えます)、このとき斜め移動は、x座標を+2か-2、もしくはy座標を+2か-2する操作へと言い換えられます。また、このことからある点(x1,y1)と(x2,y2)が移動可能かどうかは、x1とx2の偶奇、y1とy2の偶奇がともに一致しているかどうかで判断できることがわかります。
あとは、移動できるとわかった点のグループそれぞれに対して、全点対間のマンハッタン距離が求められれば良いです。
例えばある移動できる点同士の集合を$ E={E_{1},E_{2},\ldots,E_{|E|}} $とすると、
$\sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} \text{dist}(P_{E_{i}},P_{E_{j}}) = \frac{1}{2} \sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} |x_{E_{j}} - x_{E_{i}}| + \frac{1}{2} \sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} |y_{E_{j}} - y_{E_{i}}|$
を求められればよく、
$\sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} |x_{E_{j}} - x_{E_{i}}|$ は、
$(x_{E_{1}}, x_{E_{2}}, \ldots, x_{E_{|E|}})$ を昇順にソートしたとき絶対値を外せて、最後に$x_{i+1}-x_{i}$が何度距離の総和に寄与するかを考える主客転倒を用いると、
$\sum_{i=1}^{|E|-1}{(x_{i+1} - x_{i}) * (i * (|E|-i))}$
で計算できることがわかります。あとは$y$も同様に計算するだけでよいです。
コード
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY = [(x + y, x - y) for x, y in XY]
group = [[] for _ in range(4)]
for x, y in XY:
group[(x % 2) * 2 + (y % 2)].append((x, y))
ans = 0
for g in group:
Lg = len(g)
X = [x for x, y in g]
Y = [y for x, y in g]
X.sort()
Y.sort()
tmp = 0
for i in range(1, Lg):
tmp += (X[i] - X[i - 1]) * (Lg - i) * i
tmp += (Y[i] - Y[i - 1]) * (Lg - i) * i
ans += tmp
print(ans // 2)
F - Double Sum
問題
整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。
次の式を計算してください。
$$
\displaystyle \sum_{i=1}^N \sum_{j=i+1}^N \max(A_j - A_i, 0)
$$
なお、制約下において答えが $2^{63}$ 未満となることは保証されています。
考察
少し考えると、この式は$\sum_{i=1}^N ((A[i+1:]でA[i]以上の値の和)-(A[i+1:]でA[i]以上の個数)*A[i])$
と表すことができ、これはRSQのセグメント木を2本使うことで実装できることがわかります。具体的には、$A$を後ろの要素から見ていき、ある値以上の値の和を求めるためのセグメント木と、ある値以上の個数を求めるためのセグメント木を適切に更新していけばよいです。ここで、$A[i]$は0以上10⁸以下であるため座標圧縮が必要な点に注意してください。
コード
from collections import defaultdict
# https://raw.githubusercontent.com/shakayami/ACL-for-python/master/segtree.py
class segtree:
n = 1
size = 1
log = 2
d = [0]
op = None
e = 10**15
def __init__(self, V, OP, E):
self.n = len(V)
self.op = OP
self.e = E
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
for i in range(self.n):
self.d[self.size + i] = V[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
def set(self, p, x):
assert 0 <= p and p < self.n
p += self.size
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
return self.d[p + self.size]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
sml = self.e
smr = self.e
l += self.size
r += self.size
while l < r:
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
smr = self.op(self.d[r - 1], smr)
r -= 1
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def max_right(self, l, f):
assert 0 <= l and l <= self.n
assert f(self.e)
if l == self.n:
return self.n
l += self.size
sm = self.e
while 1:
while l % 2 == 0:
l >>= 1
if not (f(self.op(sm, self.d[l]))):
while l < self.size:
l = 2 * l
if f(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, f):
assert 0 <= r and r <= self.n
assert f(self.e)
if r == 0:
return 0
r += self.size
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (f(self.op(self.d[r], sm))):
while r < self.size:
r = 2 * r + 1
if f(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def __str__(self):
return str([self.get(i) for i in range(self.n)])
def get_list(self):
return [self.get(i) for i in range(self.n)] # オリジナルで追加
def compress(arr): # 座標圧縮
(*XS,) = set(arr)
XS.sort()
return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}
N = int(input())
A = list(map(int, input().split()))
enc = compress(A)
dec = defaultdict(int)
for key, val in enc.items():
dec[val] = key
def op(x, y):
return x + y
seg1 = segtree([0] * N, op, 0)
seg2 = segtree([0] * N, op, 0)
ans = 0
for a in reversed(A):
idx = enc[a]
kosu = seg1.prod(idx, N)
wa = seg2.prod(idx, N)
ans += wa - (a * kosu)
seg1.set(idx, seg1.get(idx) + 1)
seg2.set(idx, seg2.get(idx) + a)
print(ans)