ABC217 参加記録 - Xenous の精進記録

5完0ペナ 66分でした

A - Lexicographic Order

辞書順での比較は python では <、 > でできます。単純に比較して答えとします。

S, T = input().split()
if S < T: print('Yes')
else: print('No')

B - AtCoder Quiz

集合として持っておき、同じものを除いていき、残ったものを答えとします。

S = set(['ABC', 'ARC', 'AGC', 'AHC'])
tmp = input(); S.remove(tmp)
tmp = input(); S.remove(tmp)
tmp = input(); S.remove(tmp)
S = list(S)
print(S[0])

C - Inverse of Permutation

数列 $p$ で各要素の位置を持っておき、ソートした後に、その位置を出力すれば良いです。

N = int(input())
p = list(map(int, input().split()))
q = []
for i, pp in enumerate(p):
    q.append((i, pp))
q.sort(key=lambda x: x[1])
ans = []
for i, pp in q:
    ans.append(i+1)
print(*ans)

D - Cutting Woods

答えに辿り着くまで時間を要しました。

実装方針としては、分割していくよりも、逆に合体させていく方が考えやすかったので、そちらで実装します。具体的には、クエリを逆順に見て、

$c = 1$ なら、 $x$ で木材を結合する
$c = 2$ なら、 $x$ が含まれる木材の長さを答える。

となります。

まず分割が起こった $x$ をリストとして保持しておきます。これらに最後尾の $L$ を入れて、unionfind で結合を管理します。

f:id:Xenous:20210904233757p:plain — $x$ と unionfind と長さの対応づけ

unionfind の要素と、その木材の長さを対応づけしておきます。結合が発生したら、結合前の長さの和を、親の方に代入するような形で持っておきます。

次に、 $x$ が含まれる木材の長さですが、 $x$ が含まれる木材に対応する unionfind の要素番号を見つけて、そこから長さを参照するようにします。例えば $x_{d}$ を含む木材は、分割をした座標のリストを二分探索することで、unionfind の要素番号との対応づけをすることができます。

最後に、元とは逆の順序で木材の長さを答えているので、これを元に戻して出力すれば答えです。全体として $O(Q\log{Q})$ で実行できます。

提出コード

from bisect import *
import sys

input = sys.stdin.readline


class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の親の要素番号
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    L, Q = map(int, input().split())
    query = []
    div = [L]
    for _ in range(Q):
        c, x = map(int, input().split())
        query.append((c, x))
        if c == 1: div.append(x)
    
    N = len(div)
    div.sort()
    x_to_uf = dict()
    for i, x in enumerate(div):
        x_to_uf[x] = i
    uf = UnionFind(N)

    uf_to_dist = dict()
    bf = 0
    for i in range(N):
        af = div[i]
        uf_to_dist[i] = af - bf
        bf = af

    ans = []
    for _ in range(Q):
        c, x = query.pop()
        if c == 1: # 合体させる
            a = uf.find(x_to_uf[x]); b = uf.find(x_to_uf[x]+1)
            dist_a = uf_to_dist[a]; dist_b = uf_to_dist[b]
            uf.union(a, b)
            uf_to_dist[uf.find(a)] = dist_a + dist_b
        else: # 長さを答える
            a = uf.find(x_to_uf[div[bisect_left(div, x)]])
            ans.append(uf_to_dist[a])
    ans.reverse()
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

E - Sorting Queries

操作のうち、最後尾への追加、先頭の取り出しと削除については、deque を使用すれば $O(1)$ で実行可能です。しかしソートをそのままやってしまうと、ソート自体に $O(N\log{N})$ かかるので、全体で $O(QN\log{N})$ で実行時間に間に合わない場合が出てきます。（ $N$ は配列の要素数）

よくよく考えると、ソートした後取り出す数字は、小さい順になります。これはソート時の要素数の回数までは必ず成立します。したがって、この部分だけは heapq を使って、 $O(\log{N})$ で追加・取り出しを行うようにします。

ソートが起こったら、deque にある要素を heapq 側に入れていく、という操作になります。

全体として $O(Q\log{Q})$ となります。

提出コード

from collections import deque
from heapq import *

def main():
    Q = int(input())
    res_deque = deque([]); cnt = 0
    res_heap = []
    heapify(res_heap)
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            res_deque.append(query[1])
        elif query[0] == 2:
            if len(res_heap) == 0:
                ans = res_deque.popleft()
            else:
                ans = heappop(res_heap)
            print(ans)
        else:
            for _ in range(len(res_deque)):
                x = res_deque.popleft()
                heappush(res_heap, x)

if __name__ == "__main__":
    main()

F - Make Pair

区間DPで解けそうな問題でしたが時間が間に合わずでした。後日解きます。