AtCoder Beginner Contest 439（Promotion of AtCoderJobs）E,F問題メモ

AtCoder Beginner Contest 439（Promotion of AtCoderJobs）

お正月にちなんだ問題が多くてよき。

E - Kite

問題文

$1$ から $N$ の番号がついた $N$ 人の人が河原で凧揚げをしようとしています。
人 $i$ は地点 $(A_i, 0)$ に立って地点 $(B_i, 1)$ に凧を揚げようとしています。
- ※川に沿った位置を $x$ 軸、高さを $y$ 軸とした2次元座標で人・凧の位置を示しています。
人や凧の衝突、および凧糸が絡まることを避けるため、以下の条件を満たす時、人 $i$ と人 $j$ ($i \neq j$) は同時に凧を揚げることは出来ません。
- 「$(A_i, 0)$ と $(B_i, 1)$ を結ぶ線分」と「$(A_j, 0)$ と $(B_j, 1)$ を結ぶ線分」が交点を持つ。(線分の端点同士が接する場合も含む。)

以上の制約を守った上で、最大で何人が同時に凧を揚げることが出来ますか？

制約

$1 \leq N \leq 2\times 10^5$
$0 \leq A_i \leq 10^9$
$0 \leq B_i \leq 10^9$
入力される値は全て整数

解法

揚げることができる（採用できる）人と凧の配置は、以下のような感じになる。

凧   凧   凧 凧     凧
  ＼  \   /   \   ／
    人 人人   人 人
    １ ２３   ４ ５

つまり、採用する人を $A_i$ の昇順に並べてindexを振りなおしたとき、対応する凧の位置 $B_i$ も狭義単調増加になっていないといけない。
これは必要十分条件であり、この条件さえ満たしていればよい。

LIS（最長増加部分列）に帰着できる。

$A_i$ が昇順になるように、$B_i$ を並べ替える。
並べ替えた $B$ 上で狭義単調増加のLIS長が答え。

(Ai,Bi) = (3,5), (1,4), (2,6)

→ Ai昇順に並べ替えると (1,4), (2,6), (3,5)
→ Bi を取り出すと、B = [4, 6, 5]
→ BのLIS長は 2

ただし、$A_i$ が同じ人がいる場合に注意が必要となる。$A_i$ が同じものの中からは1人しか採用できない。
最小値とか最大値とか、代表的な1人だけを $B$ に取り出す？というのも、上手くいかない。

(Ai,Bi) = (1,2), (2,1),(2,2),(2,3),(2,4),(2,5), (3,4)

→ Ai=2 であるものの中からは (2,3) を採用すれば、(1,2),(2,3),(3,4)の 3 人を採用できる。
   それ以外を採用すると衝突する。
   (2,3) を採用するのが適切ということは、事前には簡単には分からない。

代わりに、「$A_i$ が同じ組内では $B_i$ を降順にして $B$ を構成する」とよい。このような降順の並びは、LISに最大でも1要素しか採用されないことが保証できる。

(Ai,Bi) = (1,2), (2,1),(2,2),(2,3),(2,4),(2,5), (3,4)

→ B = [2, 5, 4, 3, 2, 1, 4] としてLIS長を計算

Python3

from bisect import bisect_left
from collections import defaultdict


def solve(n, kites):
    starts = defaultdict(set)
    for a, b in kites:
        starts[a].add(b)
    bbb = []
    for a in sorted(starts.keys()):
        bbb.extend(sorted(starts[a], reverse=True))
    lis = [-1 << 60]
    for b in bbb:
        if lis[-1] < b:
            lis.append(b)
            continue
        i = bisect_left(lis, b)
        lis[i] = b
    return len(lis) - 1


n = int(input())
kites = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, kites)
print(ans)

F - Beautiful Kadomatsu

問題文

長さ $k$ の数列 $a=(a_1,a_2,\dots,a_k)$ が門松的であることを、以下のようにして定めます。
- $2 \le i \le k-1$ かつ $a_{i-1} \lt a_i$ かつ $a_i \gt a_{i+1}$ を満たす整数 $i$ の個数を $x$ とする。
- $2 \le i \le k-1$ かつ $a_{i-1} \gt a_i$ かつ $a_i \lt a_{i+1}$ を満たす整数 $i$ の個数を $y$ とする。
- $x \gt y$ であるとき、またそのときに限り、数列 $a$ を門松的であると言います。

$(1,2,\dots,N)$ の順列 $P$ が与えられます。
$P$ の (連続でなくともよい) 部分列であって、門松的であるものの個数を $998244353$ で割った余りを求めてください。

制約

入力は全て整数
$1 \le N \le 3 \times 10^5$
$P$ は $(1,2,\dots,N)$ の順列

解法

$x$ は数列の“山の頂点”の数、$y$ は“谷底”の数であり、どのような部分列でも頂点と谷底は必ず交互に現れる。
つまり、$x \gt y$ というのは、「山谷山谷…山」のように出現するということに等しい。

以下の2つをDPで管理する。

$\mathrm{DP}_{up}[i,j]:=P$ の $i$ 番目までの採用有無を決めて、末尾要素が $j$ であり、山が最初に出現し、暫定で谷が最後に出現している部分列の個数
$\mathrm{DP}_{down}[i,j]:=P$ の $i$ 番目までの採用有無を決めて、末尾要素が $j$ であり、山が最初に出現し、暫定で山が最後に出現している部分列の個数

答えは、$\mathrm{DP}_{down}[N,*]$ の総和である。

最後に出現したのが山か谷かは、末尾2要素で判別できる。暫定部分列の末尾要素2つを $Q_{-2},Q_{-1}$ としたとき、 $Q_{-2} \lt Q_{-1}$（上り調子）ならば谷が、$Q_{-2} \gt Q_{-1}$（下り調子）ならば山が最後に出現している。

DPの初期状態をどうするかと、更新方法を決めたい。

初期状態の実装に少し迷う。
数え上げの対象となる部分列は山が最初に出現しなければならないが、1要素だけの部分列は、その後、山と谷のどちらが最初に出現するようになるか不定である。

一方、2要素あれば確定できる。$Q_1 \lt Q_2$ となっていればよい。よって、「DPに部分列を初めて登録するのは、先頭から2番目の要素を確定するとき」とする。
2番目の要素を $P_i$ とする場合、先頭要素にできるのは「$i$ 以前に出現した、$P_i$ よりも小さい要素」なので、 FenwickTree や SortedSet などで出現した値を管理することで求められる。この個数分だけ、2番目の要素を $P_i$ とした対象の部分列が作れる。

更新は、$P_i$ より大きい値から遷移するか、小さい値から遷移するかさえ気にすればよい。（またはupのみ、新規追加できる）

$\mathrm{DP}_{up}[i,P_i]=$ 以下の合計
- $\mathrm{DP}_{up}[i-1,P_i-1以下]$ の総和
- $\mathrm{DP}_{down}[i-1,P_i-1以下]$ の総和
- $i$ 以前に出現した $P_i$ より小さい要素の個数
$\mathrm{DP}_{down}[i,P_i]=$ 以下の合計
- $\mathrm{DP}_{up}[i-1,P_i+1以上]$ の総和
- $\mathrm{DP}_{down}[i-1,P_i+1以上]$ の総和
$j=P_i$ 以外の $\mathrm{DP}_{up}[i,j],\mathrm{DP}_{down}[i,j]$
- $i-1$ の値を引き継ぐ。

よって、DPはFenwickTreeやSegmentTreeで区間和を取得できるように実装し、$i$ ごとに $j=P_i$ の箇所だけ更新すればよい。

Python3

class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


def solve(n, ppp):
    MOD = 998244353
    add = lambda a, b: (a + b) % MOD
    fwt_st = FenwickTreeInjectable(n, int, add)
    fwt_up = FenwickTreeInjectable(n, int, add)
    fwt_dn = FenwickTreeInjectable(n, int, add)
    for p in ppp:
        p -= 1
        ups = fwt_up.sum(p)
        dns = fwt_dn.sum(p)
        up = (ups + dns + fwt_st.sum(p)) % MOD
        dn = ((fwt_up.sum(n - 1) - ups) + (fwt_dn.sum(n - 1) - dns)) % MOD
        fwt_up.add(p, up)
        fwt_dn.add(p, dn)
        fwt_st.add(p, 1)
    ans = fwt_dn.sum(n - 1)
    return ans


n = int(input())
ppp = list(map(int, input().split()))
ans = solve(n, ppp)
print(ans)

解法2

最初と最後が山であることが保証されれば、どのように部分列を作っても必ず「山谷山…谷山」となり、条件を満たす部分列となる。そして、その保証は以下がともに成り立つことと同じである。

取り出した最初の2要素 $Q_1,Q_2$ が $Q_1 \lt Q_2$
取り出した最後の2要素 $Q_{-2},Q_{-1}$ が $Q_{-2} \gt Q_{-1}$

よって、転倒数の時のようにして、各 $i$ につき以下を求め、

$L_i:=i$ 以前で $P_i$ より小さい値の個数
$R_i:=i$ 以降で $P_i$ より小さい値の個数

先頭から2番目と末尾から2番目を $i,j$ と固定すれば（$i \le j$）、答えは $L_i \times R_j \times 2^{\max(0,j-i-1)}$ となる。

ただ、$i,j$ 全探索はTLEなので、先頭から「$L_i \times 2^{j-i-1}$」の部分についての各 $i$ の累積和を持ち・更新しながら計算していく。

累積和を $S=0$ で初期化する。$j=1,2,...$ の順に、

$i=j$ の場合は少し特殊なので、別途計算する。$L_j \times R_j$ を答えに加算する。
それ以外で、末尾から2番目を $j$ とした時の答え $S \times R_j$ を答えに加算する。
$S$ を更新する。
- ここまでの $S$ で数えられている各部分列につき、$P_j$ を採用するかどうかの2通りがある。
- 新たに、$j$ を先頭から2番目として採用するものが $L_j$ 個ある
- よって、$S←2S+L_j$ で更新する。

これで求められる。

目次

AtCoder Beginner Contest 439（Promotion of AtCoderJobs）E,F問題メモ

E - Kite

問題文

制約

解法

F - Beautiful Kadomatsu

問題文

制約

解法

解法2