目次
AtCoder Beginner Contest 130 D,E,F 問題メモ
D - Enough Array
問題
- 長さ $N$ の正整数列 $A=a_1,a_2,...,a_N$ と整数 $K$ が与えられる
- $N$ の連続する部分列で、以下の条件を満たすものの個数を求めよ
- (条件) 部分列に含まれる要素の総和が $K$ 以上
- ただし、部分列の各要素が同じでも、取り出された位置が異なるならそれらは別々に数える
- $1 \le a_i \le 10^5$
- $1 \le N \le 10^5$
解法
尺取法の典型的な問題。
条件を満たす最短の部分列となるように部分列の左右の境界を動かしていく。左右のindexを $l,r$ で管理して、
- 現在の部分列の合計が $K$ 未満なら、右端を1つ伸ばして $a_r$ を合計に加える
- 現在の部分列の合計が $K$ 以上なら、左端を1つ縮めて $a_l$ を合計から除く
K=10 部分列の合計
6 1 2 7 3 1 9 ↓
0 0 はじめは空の部分列
1 - 6 右に1つ伸ばす。まだKに足りない
2 --- 7 もう1つ伸ばす。まだ
3 ----- 9 もう1つ伸ばす。まだ
4 ------- 16 もう1つ伸ばす。Kに届いた。
各要素は正なので、右端をこれ以上右にしたものは、全て条件を満たす。
これを含めて4つ作れるので、答えに4を足す
5 ----- 10 左を1つ縮める。まだK以上。
さっきと同様に右端は4通り作れるので、答えに4を足す
さっきとは左端の位置が違うので、さっき加算したものとは別の部分列となる。
6 --- 9 左を1つ縮める。K未満になった。
7 ----- 12 右を1つ伸ばす。K以上になった。答えに3を足す
8 --- 10 左を1つ縮める。まだK以上。答えに3を足す
9 - 3 左を1つ縮める。K未満になった
10 --- 4 右を1つ伸ばす。まだK未満
11 ----- 13 もう1つ伸ばす。K以上になった。答えに1を足す
12 --- 10 左を1つ縮める。まだK以上。答えに1を足す
13 - 9 左を1つ縮める。K未満になった
もう右に伸ばせないので終わり
答えは 4+4+3+3+1+1=16
n, k = list(map(int, input().split()))
aaa = list(map(int, input().split()))
l, r = 0, 0
s = 0
ans = 0
while r < n:
while s < k and r < n:
s += aaa[r]
r += 1
while s >= k:
ans += n - r + 1
s -= aaa[l]
l += 1
print(ans)
また、累積和を計算しておいて、二分探索でも求められる。
「各 $a_i$ を左端としたときに、条件を満たす部分列の右端のうち、最も左の要素 $a_j$」を、各 $i$ について求めればよい。
累積和を $b_1,b_2,...,b_N$ として、はじめて $b_i+K \le b_j$ となる $j$ は、bisect.bisect_left で求まる。
また、今回のように同じ配列に対して何回も二分探索クエリを投げるときは、numpy.searchsorted が高速に動作するようだ。
K=10
i 0 1 2 3 4 5 6 7
A 6 1 2 7 3 1 9
累積和 0 6 7 9 16 19 20 29 （最も左端からの部分列を数えるため、便宜的に先頭に0を付ける）
10 16 17 19 26 29 30 39 それぞれ +K する。
累積和がこれ以上なら、そこを右端とする部分列は条件を満たす
4 4 5 5 7 7 8 8 二分探索でindexを求める
4 4 3 3 1 1 0 0 N+1 からそれぞれを引いて「自身より右にある要素の個数」を求める
（最初に先頭に0を追加したため、相対的にindexが+1されているので、引かれる数も+1する）
この合計が答え
一般的なポイントとして、
- 累積和を用いる際は、便宜的に先頭に0を付けた方がよいことがある
- 二分探索では、検索値と同じ要素が配列にあった場合、左に挿入するか右に挿入するかで求めるindexが異なる。どちらが適切かは問題によって異なるので注意する
import numpy as np n, k = list(map(int, input().split())) aaa = [0] + list(map(int, input().split())) acc = np.array(aaa, dtype=np.int64).cumsum() idx = np.searchsorted(acc, acc + k, side='left') print(((n + 1) - idx).sum())
E - Common Subsequence
問題
- $1～10^5$ の整数からなる、2つの整数列 $S,T$ が与えられる
- この2つからそれぞれ（連続とは限らない）部分列を取り出したとき、整数列として等しい組の個数を求めよ
- $S$ から取り出した2つの部分列が整数列としては同じでも、取り出した位置が異なる場合は区別する。$T$ についても同様。
- $1 \le |S|,|T| \le 2000$
解法
Binary Indexed Tree上のDPで通した。解説PDFの方が、より効率はよい。
このように2つの数列の共通部分列のうち最長のものの長さを求める問題は、Longest Common Sequenceとして動的計画法の有名な解法がある。 今回はパターン数を求める点で少し異なるが、考え方は流用できる。
$S$ の $i$ 番目の要素を $S_i$、$T$ の $j$ 番目の要素を $T_j$ とする。
もし $S_i=T_j$ なら、「$S_1～S_{i-1}$ と $T_1～T_{j-1}$ からとれる共通部分列」の全てから、末尾に $S_i$ を1つ付けることで新たな共通部分列が作れる。
逆に、$S_i$ や $T_j$ 以降の要素を使わないと作れない共通部分列からは、$S_i$ と $T_j$ を共通要素として使う部分列は作れない。
1 2 3 4 i j k ------------------------------- S 3 4 5 6 ... 7 T 4 3 6 ...... 7 5 iとjより前のSとTからは、(3), (4,6), (3,6) などが作れる。そのそれぞれから、 Si=Tj をくっつけて、(3,7), (4,6,7), (3,6,7) など新しい共通部分列が作れる Tk を使えば (3,5) という部分列も作れるが、j<k なので、 5の後ろに7を付け加えることは出来ないため、(3,5,7) という共通部分列は作れない
「$S_1～S_{i}$ と $T_1～T_{j}$ からとれる共通部分列の個数」を算出するには、「$S_1～S_{i-1}$ と $T_1～T_{j-1}$ からとれる共通部分列の個数」など、それ未満の組での計算結果があればよい。
それをすぐ取得できるようなデータ構造を持っておけば、全ての $i$ と $j$ を走査することで、$S$ と $T$ からとれる共通部分列の個数がわかる。
解説pdfには二次元累積和が使われていたが、BITを使う解法。
$DP[i] = T_1～T_j$ と $S$ との共通部分列を考えたとき、$S_i$ が右端になるものの個数
上記のDPを、$j$ が小さい方から上書き更新していく。
下記の例は $j=4$ まですすめたところ。$T_1～T_4$ と $S$ との共通する部分列で、$S_i$ が右端の要素となるものが $DP[i]$ 個あったとする。
i 0 1 2 3 4 5 6
---------------------
T 5 3 7 4 6
T1～T4 5 3 7 4
S 3 6 4 5 6 7
DP 1 1 0 2 1 0 3 Siが右端となる共通部分列の数, j=4まで考慮
| | | `-(5) `-(7),(3,7),(5,7) 具体的な共通部分列
() (3) `--(4),(3,4)
これをもとに、$j=5$ を考える。整数 $T_j=6$ が $S$ では2番目と5番目で出てくる。
5番目に着目($i=5$)すると、DPにおいて $i<5$ の部分の合計が、「$S_1～S_{i-1}$ と $T_1～T_{j-1}$ からとれる共通部分列の個数」に相当する。
これは $DP[0]+DP[1]+DP[2]+DP[3]+DP[4]$ で求められ、このような初項からの累積和はBITを使うと高速に求めることが出来る。
この1つ1つから新しい部分列が作れるので、$DP[5]$ に加算すればよい。
T1～T5 5 3 7 4 6
S 3 6 4 5 6 7
! ! S上でT5=6が出現する位置
i 0 1 2 3 4 5 6
DP 1 1 2 2 1 5 3 j=5まで考慮
| `-(6),(3,6),(4,6),(3,4,6),(5,6)
`(6),(3,6)
$i=5$ についてみると、$S_1～S_4$ と $T_1～T_4$ の共通部分列 $(),(3),(4),(3,4),(5)$ について、それぞれの後ろに“6”をつけた5個が新たに作れる。
$i=2$ は、$S_1$ と $T_1～T_4$ で作れるのが $(),(3)$ のみなので、2個を新たに作れる。
このようにして、$DP[i]$ を、$j$ の小さい方から更新していけばよい。
i 0 1 2 3 4 5 6
S 3 6 4 5 6 7
T 5 3 7 4 6
DP 1 0 0 0 0 0 0 |S|+1 の長さのDP配列を用意
T1～T1 5 Tを1文字ずつ見る
Si ! S上でのT1の出現位置...4
DP 1 0 0 0 1 0 0 DP[i<4] の合計...1 なので、DP[4] に1を加算
T1～T2 5 3
Si ! S上でのT2の出現位置...1
DP 1 1 0 0 1 0 0 DP[i<1] の合計...1 なので、DP[1] に1を加算
T1～T3 5 3 7
Si ! S上でのT3の出現位置...6
DP 1 1 0 0 1 0 3 DP[i<6] の合計...3 なので、DP[6] に3を加算
T1～T4 5 3 7 4
Si ! S上でのT4の出現位置...3
DP 1 1 0 2 1 0 3 DP[i<3] の合計...2 なので、DP[3] に2を加算
T1～T5 5 3 7 4 6
Si ! ! S上でのT5の出現位置...2, 5
DP 1 1 0 2 1 5 3 DP[i<5] の合計...5 なので、DP[5] に5を加算
1 1 2 2 1 5 3 DP[i<2] の合計...2 なので、DP[2] に2を加算
i は、同じフェイズの加算結果が重複しないように、大きい方から処理する
最後までいったら、DPの総和が答え ... 15
計算量は $O(|S||T| \log{|S|})$ となり、PyPyなら間に合う。
from collections import defaultdict
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s = (s + self.tree[i]) % 1000000007
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] = (self.tree[i] + x) % 1000000007
i += i & -i
n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))
sid = defaultdict(list)
for i, s in reversed(list(enumerate(sss))):
sid[s].append(i)
bit = Bit(n + 1)
bit.add(1, 1)
for t in ttt:
if t not in sid:
continue
for i in sid[t]:
bit.add(i + 2, bit.sum(i + 1))
print(bit.sum(n + 1))
F - Minimum Bounding Box
問題
- $N$ 個の点、$i$ 番目の点ははじめ $(x_i,y_i)$ にある
- 点には4タイプの移動方向 $d_i=(L/R/U/D)$ が定められている
- R: x軸に平行に正方向
- L: x軸に平行に負方向
- U: y軸に平行に正方向
- D: y軸に平行に負方向
- 点は時刻 $t=0$ に、一斉に各自の方向に向かって速度1で動き出す
- さて、ここで任意の時刻経過後の、バウンディングボックスの面積の最小値を求めよ
- つまり、
- $x_{max}=x$ 座標最大値
- $x_{min}=x$ 座標最小値
- $y_{max}=y$ 座標最大値
- $y_{min}=y$ 座標最小値
- としたとき、$(x_{max}-x_{min}) \times (y_{max}-y_{min})$ の最小値を求めよ
- $1 \le N \le 10^6$
- $-10^8 \le x_i,y_i \le 10^8$、整数
- 制限時間: 5sec
解法
残り時間が無いときはダメ元でえいやっと三分探索
まず、同じ方向に動く点の中での最大・最小は変わらないので、点がいくつあろうと、関係するのは以下の値だけ。
| 影響しうる値 | R | L | U | D |
|---|---|---|---|---|
| $x_{max}$ | $R_{max}$ | $L_{max}$ | $UD_{max}$ | |
| $x_{min}$ | $R_{min}$ | $L_{min}$ | $UD_{min}$ | |
| $y_{max}$ | $RL_{max}$ | $U_{max}$ | $D_{max}$ | |
| $y_{min}$ | $RL_{min}$ | $U_{min}$ | $D_{min}$ | |
$x_{max}$ について考える。
- $UD_{max}$ の値は、x座標については不変
- $L_{max}$ の値は、仮に初期配置で $x_{max}$ だったとしても、時間経過で減っていき、いつかは $UD_{max},R_{max}$ に抜かされる
- $R_{max}$ の値は、時間経過で増えていき、いつかの時点から永久に $x_{max}$ となる
例えば以下のようなパターンがある。
xmax| ＼ ／
| ＼＿＿＿／
|
+------------------> t
xmax| ＼ ／
| ＼ ／ （UDが存在しないまたはL,Rの交点より下）
| ＼／
+------------------> t
xmax| ／
| ＿＿＿＿＿／ （Lが存在しないまたは初期配置でUDmax以下）
|
+------------------> t
xmax|
| ＿＿＿＿＿＿＿＿ （LもRも存在しない）
|
+------------------> t
$x_{min}$ についても同じ事がいえ、$x_{max}$ を上下逆さまにしたようなパターンのグラフとなる。
よってこれらを足し合わせた $x_{max}-x_{min}$ は、折れ線で、傾きが「-2」→「-1」→「0」→「1」→「2」と変化していくグラフになる。
ただし各区間は、長さが0かも知れない（-1の後すぐ2になったり、永遠に0が続いたりするかもしれない）が、順序はこの通りである。
xmax| \ /
-xmin| \ /
| ＼ ／
| ＼＿＿＿／
+------------------> t
そして、$y_{max}-y_{min}$ も同様のことが言える。
さて、ではこの2つを掛け合わせるとどうなるか。
折れ線グラフでは、傾きが変わる $t$ を「変曲点」として、変曲点で区間を分割して考えるとやりやすい。 $x_{max}-x_{min}$ と $y_{max}-y_{min}$ の少なくともどちらかで傾きが変わる点で分割した区間を考える。
x | \ \ / /
y | \ \ / /
| ＼ ＼＿＿／＿＿／
| ＼＿＿＿／
|
+---|---|-|-|--|---|---|-|---> t
変曲点で分割
- 傾きがともに負、または0と負: 明らかに $t$ が大きい方が積は小さい
- 傾きがともに正、または0と正: 明らかに $t$ が小さい方が積は小さい
- 傾きがともに0: $t$ の値に依らず積は一定
- 傾きが正と負: 掛け合わせると $y=-x^2$ のような上に凸のグラフとなる。区間の端点のいずれかで最小値を取る
どの区間を取っても、「区間の端点のいずれかで最小値を取る」ことは共通している。
$x_{max}-x_{min}$ の傾きが変わる点は $x_{max},x_{min}$ のいずれかで傾きが変わる点（$y$ も同様）ので、 $x_{max},x_{min},y_{max},y_{min}$ のそれぞれで変曲点をもとめて、全て試せば良い。
4つの変数でそれぞれに変曲点が最大2つあるので、両端（左端は0, 右端は適当に大きい数字）を合わせても10個。これらを試した最小値が答えとなる。
import sys
def check(t):
maxx = max(ud_maxx, r_maxx + t, l_maxx - t)
minx = min(ud_minx, r_minx + t, l_minx - t)
maxy = max(lr_maxy, u_maxy + t, d_maxy - t)
miny = min(lr_miny, u_miny + t, d_miny - t)
return (maxx - minx) * (maxy - miny)
n = int(input())
lr_maxy, lr_miny, ud_maxx, ud_minx = -1e9, 1e9, -1e9, 1e9
l_maxx, l_minx, r_maxx, r_minx = -1e9, 1e9, -1e9, 1e9
u_maxy, u_miny, d_maxy, d_miny = -1e9, 1e9, -1e9, 1e9
for line in sys.stdin:
x, y, d = line.rstrip().split()
x, y = int(x), int(y)
if d == 'L':
lr_maxy = max(lr_maxy, y)
lr_miny = min(lr_miny, y)
l_maxx = max(l_maxx, x)
l_minx = min(l_minx, x)
elif d == 'R':
lr_maxy = max(lr_maxy, y)
lr_miny = min(lr_miny, y)
r_maxx = max(r_maxx, x)
r_minx = min(r_minx, x)
elif d == 'U':
ud_maxx = max(ud_maxx, x)
ud_minx = min(ud_minx, x)
u_maxy = max(u_maxy, y)
u_miny = min(u_miny, y)
else:
ud_maxx = max(ud_maxx, x)
ud_minx = min(ud_minx, x)
d_maxy = max(d_maxy, y)
d_miny = min(d_miny, y)
inflections = {0}
inflections.add(max(0, l_maxx - ud_maxx))
inflections.add(max(0, (l_maxx - r_maxx) / 2))
inflections.add(max(0, ud_maxx - r_maxx))
inflections.add(max(0, l_minx - ud_minx))
inflections.add(max(0, (l_minx - r_minx) / 2))
inflections.add(max(0, ud_minx - r_minx))
inflections.add(max(0, d_maxy - lr_maxy))
inflections.add(max(0, (d_maxy - u_maxy) / 2))
inflections.add(max(0, lr_maxy - u_maxy))
inflections.add(max(0, d_miny - lr_miny))
inflections.add(max(0, (d_miny - u_miny) / 2))
inflections.add(max(0, lr_miny - u_miny))
print(min(map(check, inflections)))
