2022-12-07

【いもす法】区間に等差数列を加算したい話

この記事でやること
注意事項
いもす法について
発想：2回累積和を取る
初項が0の場合
初項が一般の場合
ソースコード
例題
- 略解

この記事でやること

数列の区間に等差数列を加算するクエリを高速に処理する方法を解説します。

具体的には、数列 $a_0, a_1, \dots, a_{N-1}$ を $0$ で初期化し、以下のクエリを $Q$ 回処理した後の数列を取得することを、全体 $O(N+Q)$ で行います:

$\text{add_line}(l, r, a, d): 各i \in [l, r) に対し, a_i \leftarrow a_i + (a+d(i-l))$

注意事項

ソースコードはPython3.8を用いております。コピペはご自由にどうぞ。（AtCoder等で使用する際はPyPy3で提出して問題ありません。）

いもす法について

おなじみのやつですが、考え方が非常に重要なので確認しておきます。

いもす法は区間全体に同じ数字を加算をします。このとき、各クエリでは「最後に累積和を取ることで元の数列が復元できるような、情報量を削減した数列」を作っていきます。

ということは、同じように「最後に累積和をとることで等差数列を加算した数列が復元できるような、情報量を削減した数列」を作ることができればよさそうです。

発想：2回累積和を取る

先ほどの画像の数列に対し、もう1度累積和を取ってみます。

等差数列が出てきましたね。これを逆に言い換えれば、「2度累積和を取ることで等差数列が復元できるような、情報量を削減した数列」が存在しそうな気がしてきませんか？

というわけで、実際にそのような数列を元の等差数列から構築してみましょう。

初項が0の場合

まずは初項が0の場合を考えます。これは簡単で、下記の画像の一番上の行が作りたかった数列となります。

具体的な処理を一般的に書くと、 $\text{add_line}(l, r, 0, d)$ に対しては、

$a_{l+1} \leftarrow a_{l+1}+d$
$a_r \leftarrow a_{r}-d(r-l)$
$a_{r+1} \leftarrow a_{r+1}+d(r-l-1)$

とすればよいです。

初項が一般の場合

「初項が0の場合」に、初項のズレを加えていい感じに調整してあげればよいです。

具体的な処理を一般的に書くと、 $\text{add_line}(l, r, a, d)$ に対しては、

$a_{l} \leftarrow a_{l}+a$
$a_{l+1} \leftarrow a_{l+1}+d-a$
$a_r \leftarrow a_{r}-d(r-l)-a$
$a_{r+1} \leftarrow a_{r+1}+d(r-l-1)+a$

とすればよいです。

ソースコード

class Imos:
    def __init__(self, N) -> None:
        """
            N := 配列のsize
        """
        self.N = N
        self.A = [0]*(N+2)
    def add_line(self, l, r, a, d) -> None:
        """
            [l, r) に初項a, 公差d の等差数列を加算
        """
        self.A[l] += a
        self.A[l+1] += d-a
        self.A[r] -= d*(r-l)+a
        self.A[r+1] += d*(r-l-1)+a
    def get_array(self) -> None:
        """
            現在の数列を取得
        """
        ret = [0]*self.N
        ret[0] = self.A[0]
        for i in range(self.N-1):
            ret[i+1] = ret[i]+self.A[i+1]
        for i in range(self.N-1):
            ret[i+1] += ret[i]
        return ret

例題

atcoder.jp

略解

「順送りボタン」のみを使う場合にボタンを押す回数から、「お気に入りボタン」を使うことで削減できる回数を引くと考えます。

各 $i \in [1, N-1]$ に対し、 $a_i \rightarrow a_{i+1}$ の間でお気に入りボタンを使った際に削減できる回数は、下図のように等差数列で定まります。（実際は $a_i \gt a_{i+1}$ の場合もあり、その場合は等差数列が2つに分断されます。）

あとは、各 $i$ に対してこれら削減回数の和を位置ごとに取り、maxとなる位置にお気に入りボタンを設定するのが最適となります。

提出コード

2022-12-04

数弱がつらい話(ABC280感想)

この記事でやること
注意
0回戦敗退
A問題
B問題
C問題
D問題
E問題
F問題
G, Ex問題
感想
最後に

この記事でやること

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder の参戦記（？）を書きます。多少は問題解説を入れますが、基本的にはただの日記です。

注意

提出コードのリンクを貼っていますが、全てPyPy3での実装となります。

コンテスト中に提出したものをそのまま貼ってあるので、可読性を意識せずに書いていることをご了承ください。←意識しなくても書けるようにする努力をしてください。

0回戦敗退

絶起しました。「ちょっと昼寝」のつもりが、目が覚めたら21:30でした。晩御飯も食べていなかったため、諦めて23:00からバチャで参戦。

コンテスト当日に昼寝を取る場合はアラームを設定しましょう。（自戒）

A問題

行ごとに input().count("#") して合計を求めました。

提出コード

C問題

$S, T$ の先頭から見ていき、 $S_i \neq T_i$ となる最小の $i$ を求めればよいです。 $T$ の末尾に挿入されるケースに注意しましょう。

コンテスト中の私は問題文中で $S, T$ のどちらに挿入したのかわからなくなったため、末尾の処理をどちらに挿入されていてもいいように書いたようです。頭が悪い。

提出コード

D問題

AC間に合いませんでした。（は？）

$K$ を試し割り法で素因数分解しておいて、各素因数ごとに $N$ を求めてそれらのmaxを求めればよいです。

一生計算式をバグらせてました。数弱つらい。

提出コード

E問題

期待値dp とかいうやつです。

$\text{dp} [ i] := 体力 i のモンスターを倒すための攻撃回数の期待値$

とすれば、

$\text{dp} [ i] = 1+\text{dp} [ i-1 ] * (1-P/100) + \text{dp} [ i-2 ] * P/100$

と表せます。

modの割り算は逆元の掛け算で計算します。

フェルマーの小定理より、整数 $p$ の倍数でない整数 $a$ の、 $\text{mod} ~p$ での逆元は $a^{p-2}$ と表せるので、Pythonならpow( $a$ , $p-2$ , $p$ ) とすることで求められます。

提出コード

F問題

有向グラフとして見たとき、 $X_i, Y_i$ の弱連結成分に「重みの和が0でない無向閉路(逆辺は重みを-1倍する)」が存在する場合にinfを出力します。

そのような無向閉路の検出は重み付きUnioni-Findというデータ構造を用いれば実現できます。普通のUnion-Findでの経路圧縮時に重みも圧縮するだけなので、そんなに難しくはないです。自前の重み付きUnion-Findの実装では、リンク先の記事とは異なりunion by size による実装をしております。

提出コード

G, Ex問題

わかんないです…。

感想

D問題が通せないのは、数弱にも程があると思いました。

今までも茶、緑diff 程度の数学問題で沼ることが結構あり、前回のD問題でも1階微分して=0となる解を探すだけなことに気付かず、三分探索を書いてバグらせてました。そもそも傾きの単調性を調べるために2階微分してたのに、その時点で何故気付かないんですかね？

（ちなみに、これまでで最も酷かった数弱事件はABC266-Bです。ACしたのはコンテスト終了2分前らしいです。）

数弱を克服したいと思いつつも一生改善できていないことを実感するABCでした。

最後に

毎週土曜20:45にアラームが鳴るよう設定しました。皆さんも絶起には気をつけましょう。

2022-11-13

AtCoderアルゴで入青した話

はじめに
経歴
基本的にやるべきこと
体系的に学ぶこと
その他私がやっていたこと
- 競プロゼミ
- 組合せ論ゼミ
おわりに

はじめに

私事ですが、先日行われた大和証券プログラミングコンテスト2022 Autumn（ABC277）にて念願の入青を達成しました！

本記事では、私がプログラミング経験が完全に0の状態から競プロを始めて、入青に至るまでにやったことをまとめます。今後入青を目指す方にとっての勉強指針の一例にでもなれば幸いです。（参考になるかはわかりませんが…）

経歴

まず、私自身の情報について軽く紹介しておきますと、2022年11月現在、地方国立大の理学部数学・情報系の3年生です。

大学入学時（2020年3月末）に友人からの誘いで競プロを始めましたが、当時はプログラミングを一切触ったことのない全くの初心者でした。そこからはなんやかんやコツコツと勉強して、最初の画像の通りじわじわとレートを積み重ねていきました。

基本的にやるべきこと

単刀直入に言えば、とにかく問題を解きまくることが何よりも大切です。

私の精進グラフを見てもらうと一目瞭然かと思いますが、問題は解けば解くほどレートが上がります。（2022年4月頃にはABCの過去問の青diff以下を埋め終わってしまい精進グラフが伸び辛くなってしまっていますが、典型90、PAST過去問、その他コンテストの問題等精進グラフに反映されない問題を解いています。)

過去問演習には AtCoder Problems が便利です。（ABCの）自分の1つ上の色の問題以下は全部解いてやる！くらいの気持ちで臨みましょう。（もちろん、もっと難しい問題を頑張るのが楽しいのであればそれもいいと思います。）

ここで、「問題を解けと言われても、そもそも解けなくて困ってるんだよ…」と思われる方がいるかもしれませんが、その場合は躊躇わずに解説を読みましょう。知らないアルゴリズムや考察テクニックを一から思いつくのは不可能なので、ある程度考えて「これは解けそうにない」と感じればすぐに解説を読んでしまってよいと思います。そうやって知識を身につけていくうちに、段々と「これは典型で…」の一言で多くの問題が解けるようになっていきます。

また、解説を読んでも理解できない場合もあるかもしれません。公式解説やユーザー解説、解説放送などどれを見てもわからずに詰まったときは、勇気を持って諦めてしまうのも大切です。これはどんな勉強にも共通して言えることなのですが、そのときわからなくてもそのうち戻ってきたらわかるようになっていることって結構あります。基礎的な能力が向上してるんですかね？

体系的に学ぶこと

先述のとにかく数をこなせ論は所謂パワープレーで、（実装力や考察能力といった）基礎能力を伸ばしたうえで典型知識を増やせる代わりに、どうしても時間がかかってしまうという側面があります。そこで、効率を重視したいのであれば、典型90やdpまとめコン、あるいは蟻本や最近発売された鉄則本といった教育用に作られたコンテンツを過去問演習と併用していくのもよいと思います。

まあいずれにせよ数をこなすべきだというところは変わらないので、やりたいようにやりましょう。楽しくいっぱい学ぶのが一番です。

その他私がやっていたこと

これまではこれと言った個性のない「まあ大体の人はそれをやってるよね」という内容を書いていたので、ここからは私がやっていたちょっと個性のありそうなことを紹介します。参考になるかは不明です。

競プロゼミ

緑初期～水初期の約1年間、大学で（競プロ経験のない）友人数人とつよつよの先輩を誘って、競プロの自主ゼミを開いていました。

活動内容としては、毎週のABCの解説と類題の提示、余った時間で典型問題の紹介等で、毎週毎週A4のノート6ページ分くらいを用意してました。色々な解説を読んで、別解を実装してみて、思考の流れを言語化して…そのようなことを半強制的に行う場を設けたことで、頭の中の乱雑した典型知識をがっちりと整理できたような気がします。

組合せ論ゼミ

競プロゼミを始めた1か月後くらいから始めた自主ゼミで、今も続けています。

前提として、私はセンター数学で6割5分すらとれない程度のそこそこな数弱です。なので、ABCでも頻出な数学問題に手も足も出ないような状態でした。

そこで、特に数え上げ問題が解けるようになりたい！と思い立ち数強の友人に「組合せ論のゼミ開いてくれ！」と頼んだ結果、色々あって私が主催することになりました。（どうして…）

まあ、なんやかんや「数学書を読む習慣」が身につくことで難解な暖色diffの解説が少しずつ読めるようになってきている気がするので、効果はそこそこあるのかもしれません。

おわりに

約2年半競プロに打ち込んで、どれだけ平凡でも努力さえすれば意外となんとかなることがわかりました。正直競プロを始めた1年生の頃は緑色にすらなれる気がしなかったので、こうして3年生で青色になれた感動は筆舌しがたいです。

大学生活はあと1年ですが、どこまで精進できるでしょうか…。暖色への道のりはこれまでに比べてより一層険しくなるとは思いますが、少しずつ少しずつ積み重ねていきたいと思います。

2022-09-16

二重連結性とlowlinkの話

この記事でやること
注意事項
モチベーション
lowlinkの基本
- 前提：DFS木と後退辺・横断辺
- lowlinkでやること
lowlinkの活用例
- 橋と二重辺連結成分
- 関節点と二重頂点連結成分
ソースコード全体
類題
参考資料

この記事でやること

グラフの橋、関節点、二重辺連結成分、二重頂点連結成分といった概念と、それらを求める際に用いる「lowlink」という手法を解説します。

注意事項

この記事で扱うグラフは、全て単純な連結無向グラフとします。
ソースコードは全てPython3.8を用いております。コピペはご自由にどうぞ。（AtCoder等で使用する際はPyPy3で提出して問題ありません。）

モチベーション

グラフが与えられたときに、ある2頂点についてそれら結ぶ互いに素な（同じ辺/頂点を通らない）2つ以上のパスが存在するか？という問題を考えます。

これはグラフの二重連結性に関する問題と言えますね。

この問題の場合は最大フローで解けそうですが、もっと複雑な問題になってくると計算量が壊れてしまいます。そこで、特に二重連結性に関する問題を効率よく解く手段が欲しいわけですね。

lowlinkの基本

前提：DFS木と後退辺・横断辺

lowlinkの話に入る前に、知っておく必要のある用語と命題について解説します。

DFS木

グラフにおいて適当な頂点 $s$ を始点としてDFS（深さ優先探索）したとき、使用した辺を取ることで構成される、 $s$ を根とする木。特にこの記事では、DFS木上の各辺を葉方向の有向辺とします。

後退辺

グラフから全域木 $T$ を取ります。このとき使われなかった辺 $\{u, v\}$ について、 $u$ と $v$ が $T$ における祖先と子孫の関係にあるとき、後退辺といいます。

横断辺

グラフから全域木を取ります。このとき使われなかった辺のうち後退辺でないものを横断辺といいます。

命題：グラフからDFS木を取ったとき、使われなかった辺は全て後退辺となる

証明

背理法で示します。

DFS木 $T$ について、横断辺 $\{u, v\}$ が存在すると仮定します。

また、DFSにおける各頂点 $i$ の行きがけ順(pre-order)を $\text{ord}[i]$ で表すとします。

一般性を失わず、 $\text{ord}[u] \lt \text{ord}[v]$ とします。

$\{u, v\}$ は横断辺であることから、 $v$ に訪れるのは $u$ から帰ったあとであるはずです。

つまり、任意の $u$ の隣接点 $w \in \text{adj}[u]$ について、 $\text{ord}[u] \gt \text{ord}[w]$ が成り立ちます。

ここで、 $v \in \text{adj}[u]$ より $\text{ord}[u] \gt \text{ord}[v]$ となり、矛盾　☐

ちなみに、全ての使われていない辺が後退辺となる全域木はDFS木ですが、実は全て横断辺となる全域木も存在します。どんな木でしょう？

参考↓

atcoder.jp

lowlinkでやること

ordの定義

先ほどの証明で使った定義通り、DFSにおける各頂点 $i$ の行きがけ順(pre-order)を $\text{ord}[i]$ で表すとします。

lowの定義

DFSによって $\text{ord}$ と、以下で定義される $\text{low}$ を求めておきます：

$\text{low}[i] :=$ 頂点 $i$ から後退辺を高々 $1$ 回まで使って到達できる頂点の集合 $L[i]$ について、 $\underset{j \in L[i]}{\text{min}}\{\text{ord}[j]\}$

例です。定義と照らし合わせて確認してみてください。

この $\text{ord}$ と $\text{low}$ を用いて、二重連結性に関するアレコレを求めていく手法をlowlinkといいます。

ordとlowの求め方

まずDFSをしながら $\text{ord}$ を埋めていき、 $\text{low}$ もその値で初期化します。その最中に後退辺 $(u, v)$ が見つかれば、 $\text{low}[u]$ を $\text{ord}[v]$ でchmin*1します。

次に、ボトムアップ順に各頂点 $u$ について、 $\text{low}[u]$ を各 $u$ の子 $v \in \text{son}[u]$ について $\text{low}[v]$ でchminしていくことで、 $\text{low}$ を求めることができます。

実装例

下記の実装例では、DFSをするついでに各頂点の子を表す二重配列 $\text{son}$ 、頂点のトポロジカルソート順を表す配列 $\text{tps}$ の作成を行っています。

計算量は $O(N+M)$

class LowLink():
    def __init__(self, adj):
        self.n = len(adj)
        self.ord = [None]*self.n
        self.low = [None]*self.n
        self.son = [[] for _ in range(self.n)] # son[i] := 頂点iの子を格納したlist
        self.back_edge = [[] for _ in range(N)] # back_edge[i] := 頂点iから出る後退辺の終点を格納したlist
        self.tps = [] # 頂点のトポロジカルソート

        # DFSでord, son, tpsを求め、lowを初期化
        t = 0 # 今までに訪れた頂点数
        stack = [(None, 0)] # 直前にいた頂点, 今いる頂点
        while stack: 
            pre, now = stack.pop()
            if self.ord[now] is not None: # 直前に通った辺が後退辺ならば
                if self.ord[pre] < self.ord[now]: continue # 後退辺を根側から進んでいた場合は無視
                self.low[pre] = min(self.low[pre], self.ord[now]) # low[pre]をord[now]でchmin
                self.back_edge[pre].append(now)
                continue
            if pre is not None:
                self.son[pre].append(now)
            self.tps.append(now)
            self.ord[now] = t # 行きがけ順を書き込む
            self.low[now] = self.ord[now] # low[now]をord[now]で初期化
            t += 1
            for next in adj[now]:
                if next == pre: continue
                stack.append((now, next))
        
        # ボトムアップ順にchminしてlowを求める
        for u in reversed(self.tps[1:]):
            for v in self.son[u]:
                self.low[u] = min(self.low[u], self.low[v])

lowlinkの活用例

ここからは、先ほど求めた $\text{ord}$ と $\text{low}$ を用いて、二重連結性に関するアレコレを求める方法を解説していきます。

橋と二重辺連結成分

橋(bridge)

削除するとグラフが連結でなくなるような辺。

どの閉路にも含まれない辺とも言い換えられます。

現実ネットワークで考えると「断線したらヤバい辺」にあたります。

二重辺連結成分(two-edge connected component)

グラフから橋を全て削除したときの連結成分。

任意の異なる2つの二重辺連結成分 $A, B$ について、以下の性質が成り立ちます。

任意の異なる2頂点 $a_1, a_2 \in A$ について、辺について互いに素なパス $a_1 - a_2$ が少なくとも2つ存在する
任意の2頂点 $a \in A, b \in B$ について、辺について互いに素なパス $a - b$ を2つ以上取ることはできない

二重連結成分分解の方法

グラフから橋と二重辺連結成分を列挙する方法を考えます。

適当な頂点からDFSして $\text{ord}$ と $\text{low}$ を求めておきましょう。

橋の判定

後退辺は明らかに橋ではないので、木上の辺のみ見ていきます。

辺 $(u, v)$ が閉路に含まれる

$\Leftrightarrow$ $v$ から後退辺を高々 $1$ 回まで使って $u$ または $u$ の祖先に到達できる

より、閉路に含まれない、すなわち橋であるための必要十分条件は

辺 $(u, v)$ が橋である

$\Leftrightarrow \text{low}[v] \gt \text{ord}[u]$

となります。

緑の辺が橋。 $\text{low}[v] \gt \text{ord}[u]$ となっている

緑の辺が橋。 $\text{low}[v] \gt \text{ord}[u]$ となっている

二重辺連結成分の列挙

橋を通らないようにDFSして連結成分を求めていけばいいですね。

例えば頂点 $0$ からスタートすると、 $0, 1, 2, 5, 6, 8, 9$ と連結成分が求まる

実装例

各連結成分の頂点集合を二重配列で持つ $\text{tecc}$ 、元グラフの頂点から連結成分を逆引きするための配列 $\text{tecc_idx}$ を求めたいです。

根から始め、橋があれば「その先の頂点を始点としてまたDFSしますよー」というフラグを追加する、という感じの方針で実装します。

二重連結成分分解のついでに、連結成分を1点に縮約することで得られる、連結成分を頂点、橋を辺とした木を構築します。

（この木を作っておくことで、一般的に木で扱えるような色々なテクニックを用いて問題を効率よく解けたりします。）

この木を表現するために隣接リスト $\text{tecc_tree}$ も追加で作ります。

計算量は $O(N)$

    # 二重辺連結成分分解
    def two_edge_connected_component(self):
        tecc = [] # tecc[i] := 連結成分iに属する頂点の番号を格納したlist
        tecc_idx = [None]*self.n # tecc_idx[i] := 頂点iが属する連結成分の番号(上記teccにおけるindexに対応)
        tecc_tree = [] # 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト
        sub_roots = [(None, 0)] # 橋を見つけるごとに、その先は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            tecc.append([]) # 今いる頂点の連結成分を格納するlistを追加
            tecc_tree.append([]) # 今いる頂点の連結成分の隣接先を格納するlistを追加
            while stack:
                pre, now = stack.pop()
                tecc[idx].append(now) # 今いる頂点を連結成分idxに追加
                tecc_idx[now] = idx # 今いる頂点の連結成分の番号idxを記録
                if pre is not None and idx != tecc_idx[pre]: # 直前に橋を通ってきていたら
                    tecc_tree[idx].append(tecc_idx[pre]) # その橋で繋がれた2つの連結成分を辺で結ぶ
                    tecc_tree[tecc_idx[pre]].append(idx)
                for next in self.son[now]:
                    if self.low[next] > self.ord[now]: # 橋なら
                        sub_roots.append((now, next)) # その先は別の連結成分
                    else: # そうでないなら
                        stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
            idx += 1
        return tecc, tecc_idx, tecc_tree

例題

atcoder.jp

解説

二重辺連結成分分解して縮約した木を考えます。この木上の辺は全て橋なので、異なる2頂点間を結ぶパスで、辺について素なものは高々1つしか取れません。よって、（ $A, B, C$ を木上の対応する頂点で置きなおしたとして） $A \rightarrow B \rightarrow C$ というトレイルで同じ辺を通らないためには $B$ が $A-C$ パス上に存在することが必要十分条件となります。

この判定方法は色々考えられますが、私の提出コードではオイラーツアー*2を使用しました。

二重辺連結成分分解し縮約した木上で、A-Cパス上にBが存在するかを判定すればよい

ACコード

Submission #34875923 - AtCoder Regular Contest 039

関節点と二重頂点連結成分

関節点(articulation point)

削除するとグラフが連結でなくなるような頂点。

現実ネットワークで考えると「ダウンしたらやばい中継点」にあたります。

二重頂点連結成分(biconnected component)

頂点の部分集合 $A \subset V$ が二重頂点連結成分である

$\underset{\text{def}}{\Leftrightarrow}$ 任意の頂点 $a \in A$ について、 $A \setminus \{a\}$ は連結であり、かつ $A$ は極大である

最後の「極大である」というのは、前半の二重頂点連結性に関する条件を満たす $A^\prime, A$ について $A^\prime \subset A$ なら $A$ の方を二重頂点連結成分としますよー、という意味です。

この定義から、関節点は複数の二重頂点連結成分に属する場合もあることに注意してください。

二重頂点連結成分分解の方法

グラフから関節点と二重頂点連結成分を列挙する方法を考えます。

適当な頂点からDFSして $\text{ord}$ と $\text{low}$ を求めておきましょう。

関節点の判定

関節点を考える上で重要なのは「”どの頂点に対して”関節点なのか」という点。

まず、根について考えます。

少し観察すれば直ちに下の事実が得られるはずです。

根 $r$ が子 $v$ に対して関節点

$\Leftrightarrow$ 根 $r$ の出次数が $2$ 以上

次に、根以外の頂点について考えます。

DFS木上で根以外のある頂点を削除したとき、それによって根側から分離される頂点はどれか？を見る必要があります。

では、頂点 $u$ を削除した際に子 $v$ が分離されるとはどういうときでしょうか？

橋を列挙したときと同様に考えると、 $v$ から $u$ の祖先である頂点に後退辺を高々1つだけ到達できれば分離されないことになるので

根でない頂点 $u$ が子 $v$ に対して関節点

$\Leftrightarrow \text{low}[v] \ge \text{ord}[u]$

となります。

$\text{low}[v] \ge \text{ord}[u]$ のとき、 $u$ は $v$ に対して関節点となる

$\text{low}[v] \ge \text{ord}[u]$ のとき、 $u$ は $v$ に対して関節点となる

二重頂点連結成分の列挙

二重頂点連結成分は辺集合で見ると重複無しに分解できます。となると辺基準の分解しておくと嬉しい場合もある（かもしれない、要出典）ので、辺基準の分解と頂点基準の分解を両方行うことにします。

辺基準の分解で考えると、二重連結成分分解は「木上の、親側の端点を削除したら子側の端点が根から分離されてしまう辺」すなわち下図の緑の辺からスタートして、緑の辺を通らないようにDFSすることで実現できるとわかるでしょう。

例えば辺 $(1, 2)$ からスタートすると、 $(1, 2), (2, 5), (5, 1)$ と連結成分が求まる

例えば辺 $(1, 2)$ からスタートすると、 $(1, 2), (2, 5), (5, 1)$ と連結成分が求まる

頂点基準で分解する場合は、辺基準で分解中に通った頂点を順次記録していけばよいですね。

実装例

辺基準で分解した際の各連結成分の辺集合を二重配列で持つ $\text{bce}$ 、頂点基準で分解した際の各連結成分の頂点集合を二重配列で持つ $\text{bcv}$ 、各頂点が関節点であるかどうかを表すbool値配列 $\text{is_ap}$ を作っています。

二重辺連結成分分解と同様、根から始め、緑の辺があれば「その先の頂点を始点としてまたDFSしますよー」というフラグを追加する、という感じの方針で実装しました。

注意点として、DFSを開始するごとにそのパートの連結成分を格納する空listを用意していますが、根が関節点（出次数が2以上）の場合のみそのパートでは連結成分が構成されないという例外があるので、そのときは一時的に作ったlistをすぐにpop()しています。

計算量は $O(N+M)$

（ $\text{bce}$ を作らない、つまり、後退辺を無視するなら $O(N)$ ）

    # 二重頂点連結成分分解
    def biconnected_component(self):
        bce = [] # bce[i] := 連結成分iに属する辺を格納したlist
        bcv = [] # bcv[i] := 連結成分iに属する頂点を格納したlist
        is_ap = [False]*self.n # is_ap[i] := 頂点iは関節点であるか(True/False)
        sub_roots = [(None, 0)] #「ある子に対する関節点」を見つけるごとに、その子以降は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            bce.append([]) # 今いる頂点の連結成分に含まれる辺を格納するlistを追加
            bcv.append([]) # 今いる頂点の連結成分に含まれる頂点を格納するlistを追加
            if stack[0][0] is not None: # 直前に通った頂点(関節点)が存在するなら
                bcv[idx].append(stack[0][0]) # それを連結成分idxに追加
            while stack:
                pre, now = stack.pop()
                if pre is not None: # 直前に通った辺が存在するなら
                    bce[idx].append((pre, now)) # 通ってきた辺を連結成分idxに追加 
                bcv[idx].append(now) # 今いる頂点を連結成分idxに追加
                if now == 0: # 今いる頂点nowが根で
                    if len(self.son[now]) >= 2: # 関節点であるなら
                        for next in self.son[now]:
                            is_ap[now] = True # 関節点であことを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        bce.pop() # 「根の関節点のみ」の連結成分は存在しないが追加してしまっているので、例外的に削除する
                        bcv.pop()
                        idx -= 1
                    else: # 関節点でないなら
                        for next in self.son[now]:
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                else: # 根でなく
                    for next in self.son[now]:
                        if self.low[next] >= self.ord[now]: # 子nextに対して関節点なら
                            is_ap[now] = True # 関節点であることを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        else: # 関節点でないなら
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                if now == 0 and len(self.son[now]) <= 1:
                    for back in self.back_edge[now]: # 今いる頂点から出る後退辺は同じ連結成分なので
                        bce[idx].append((now, back)) # 連結成分idxに追加
            idx += 1
        return bce, bcv, is_ap

block-cut tree

二重辺連結成分分解では連結成分を縮約するだけで木が構築できました。では、二重頂点連結成分分解でも同様な「意味のある木」を構築したいです。

しかし、そのままだと関節点が複数の連結成分に共有されていて縮約は難しそうですね。そこで、「連結成分そのもの」を表す頂点を用意し、各関節点についてそれが含まれる連結成分を表す頂点を辺で結ぶことにします。

このようにして作られる木をblock-cut treeと呼ぶそうです。

実装例

データの表現方法としては、関節点の個数を $\text{num_ap}$ とおき、木上の頂点について関節点について順に $[0, \text{num_ap})$ の番号を割り振り、連結成分を表す頂点は $[\text{num_ap}, \text{木の頂点の個数})$ の番号を割り振って隣接リスト $\text{bc_tree}$ を作っています。

また、各木の頂点が持つ元グラフに関する頂点集合を

関節点 ⇒ それ1つの単元集合
連結成分を表す頂点 ⇒ 元の連結成分から関節点を除いた頂点集合（空集合になる可能性もある）

と定義して二重配列で持った $\text{bc}$ 、また元のグラフの頂点から木上の頂点を逆引きする配列 $\text{bc_idx}$ を作っています。

具体的な方法はコードで確認して頂きたいのですが、先ほど求めた $\text{bcv}$ と $\text{is_ap}$ を使うことで簡単に作れます。

計算量は $O(N+M)$

（ $\text{biconnected_component()}$ にて $\text{bce}$ を作らない、つまり、後退辺を無視するなら $O(N)$ ）

    # block-cut treeを構築
    def block_cut_tree(self):
        bce, bcv, is_ap = self.biconnected_component() # 二重頂点連結成分分解
        num_ap = sum(is_ap) # 関節点の個数
        bc = [[] for _ in range(num_ap+len(bcv))] 
        # bc[i] := block-cut tree上の頂点iに対応する頂点を格納したlist
        # [0:num_ap)は関節点に対応する頂点で、その関節点のみがlistに含まれる
        # [num_ap:len(bc))は連結成分に対応する頂点で、その連結成分から関節点を除いたものがlistに含まれる
        # block-cut tree上の頂点iが関節点に対応している ⇔ i < num_ap
        bc_idx = [None]*self.n
        # bc_idx[i] := (元グラフの)頂点iが属するblock-cut tree上の頂点の番号(bc, bc_treeのindexに対応)
        # 関節点でない頂点iについて、対応するbce, bcvのindexが知りたい場合、bc_idx[i]-num_apで取得可能。
        bc_tree = [[] for _ in range(num_ap+len(bcv))] # bc_tree[i] := block-cut tree上の頂点iの隣接頂点を格納したlist
        idx = 0 # 今見ているblock-cut tree上の頂点番号
        for v in range(self.n): # (元グラフの)各頂点vについて
            if is_ap[v]: # 関節点なら
                bc[idx].append(v) # block-cut tree上の頂点idxにvを対応させる
                bc_idx[v] = idx
                idx += 1
        for bcv_i in bcv: # 各連結成分の
            for v in bcv_i: # 各頂点vについて
                if is_ap[v]: # 関節点なら
                    bc_tree[idx].append(bc_idx[v]) # block-cut tree上の頂点idxと関節点vに対応した頂点を辺で結ぶ
                    bc_tree[bc_idx[v]].append(idx)
                else: # そうでないなら
                    bc[idx].append(v) # block-cut tree上の頂点idxに対応した頂点集合に頂点vを追加
                    bc_idx[v] = idx
            idx += 1
        return bc, bc_idx, bc_tree, num_ap, bce, bcv, is_ap

例題

atcoder.jp

解説

まず、以下のように $x$ 座標または $y$ 座標が等しい頂点を辺で結ぶことでグラフを構築します。

このグラフにおいてマッチングを考えるとき、頂点数が偶数の連結成分には完全マッチングが存在することが示せます。（証明は公式解説を参照してください。）

よって、この問題は各頂点を取り除いたときに全ての連結成分の頂点数が偶数になるかを判定する問題に帰着されます。

ここで、例えば全ての頂点の $x$ 座標が等しいようなケースで辺の本数が $O(N^2)$ となってしまい、扱うことができません。

そこで、「頂点を1つ取り除いたときの連結性を判定する」という問題の性質から三重以上の頂点連結成分は二重まで緩めても解に影響が出ないことを利用して、下図のように辺の本数を $O(N)$ に落とします。

また、全頂点数が奇数なので、頂点数が奇数の連結成分は少なくとも $1$ つ存在しますが、 $2$ つ以上存在する場合は明らかに $1$ つの頂点を削除するだけで全ての連結成分の頂点数を奇数にすることはできないので、頂点数が奇数の連結成分がただ $1$ つ存在する場合のみ考えます。

さらに、そのような場合において頂点数が偶数の連結成分から頂点を取り除くのも明らかに不適なので、ただ $1$ つの頂点数が奇数の連結成分にのみ着目します。

まず、「 $1$ 頂点を取り除いたときに連結でなくなるかどうか」が知りたいので、とりあえず二重頂点連結成分分解し、block-cut treeを作っておきましょう。

block-cut treeを構築。木の頂点 $i$ 内の数字は、 $\text{len}(\text{bc}[i])$ を表す

この連結成分において、関節点でない頂点を $1$ つ削除すると、連結性は崩れずに頂点数が $1$ 減るので、全ての連結成分の頂点数が偶数となります。では、関節点を取り除くとどうなるでしょうか？

これは実際に木から関節点を取り除いてみることですぐに結果がわかります。

すなわち、いくつかの部分木に分離するので、そのサイズの偶奇を確かめ、その中に $1$ つでも奇数のものがあれば不適、そうでないなら適切となります。

block-cut treeから関節点を $1$ つ削除すると、いくつかの部分木に分離する

あとは部分木のサイズが求まればよいので、根を適当に固定した木dpをすることで解くことができます。

以上より、全体 $O(N)$ で解けました。

ACコード

Submission #34866716 - AtCoder Regular Contest 045

（MLEとの戦いの結果、 $\text{bce}$ を求めないといったような実装例からの変更点が存在します。）

ソースコード全体

class LowLink():
    def __init__(self, adj):
        self.n = len(adj)
        self.ord = [None]*self.n
        self.low = [None]*self.n
        self.son = [[] for _ in range(self.n)] # son[i] := 頂点iの子を格納したlist
        self.back_edge = [[] for _ in range(N)] # back_edge[i] := 頂点iから出る後退辺の終点を格納したlist
        self.tps = [] # 頂点のトポロジカルソート

        # DFSでord, son, tpsを求め、lowを初期化
        t = 0 # 今までに訪れた頂点数
        stack = [(None, 0)] # 直前にいた頂点, 今いる頂点
        while stack: 
            pre, now = stack.pop()
            if self.ord[now] is not None: # 直前に通った辺が後退辺ならば
                if self.ord[pre] < self.ord[now]: continue # 後退辺を根側から進んでいた場合は無視
                self.low[pre] = min(self.low[pre], self.ord[now]) # low[pre]をord[now]でchmin
                self.back_edge[pre].append(now)
                continue
            if pre is not None:
                self.son[pre].append(now)
            self.tps.append(now)
            self.ord[now] = t # 行きがけ順を書き込む
            self.low[now] = self.ord[now] # low[now]をord[now]で初期化
            t += 1
            for next in adj[now]:
                if next == pre: continue
                stack.append((now, next))
        
        # ボトムアップ順にchminしてlowを求める
        for u in reversed(self.tps[1:]):
            for v in self.son[u]:
                self.low[u] = min(self.low[u], self.low[v])

    # 二重辺連結成分分解
    def two_edge_connected_component(self):
        tecc = [] # tecc[i] := 連結成分iに属する頂点の番号を格納したlist
        tecc_idx = [None]*self.n # tecc_idx[i] := 頂点iが属する連結成分の番号(上記teccにおけるindexに対応)
        tecc_tree = [] # 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト
        sub_roots = [(None, 0)] # 橋を見つけるごとに、その先は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            tecc.append([]) # 今いる頂点の連結成分を格納するlistを追加
            tecc_tree.append([]) # 今いる頂点の連結成分の隣接先を格納するlistを追加
            while stack:
                pre, now = stack.pop()
                tecc[idx].append(now) # 今いる頂点を連結成分idxに追加
                tecc_idx[now] = idx # 今いる頂点の連結成分の番号idxを記録
                if pre is not None and idx != tecc_idx[pre]: # 直前に橋を通ってきていたら
                    tecc_tree[idx].append(tecc_idx[pre]) # その橋で繋がれた2つの連結成分を辺で結ぶ
                    tecc_tree[tecc_idx[pre]].append(idx)
                for next in self.son[now]:
                    if self.low[next] > self.ord[now]: # 橋なら
                        sub_roots.append((now, next)) # その先は別の連結成分
                    else: # そうでないなら
                        stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
            idx += 1
        return tecc, tecc_idx, tecc_tree
    
    # 二重頂点連結成分分解
    def biconnected_component(self):
        bce = [] # bce[i] := 連結成分iに属する辺を格納したlist
        bcv = [] # bcv[i] := 連結成分iに属する頂点を格納したlist
        is_ap = [False]*self.n # is_ap[i] := 頂点iは関節点であるか(True/False)
        sub_roots = [(None, 0)] #「ある子に対する関節点」を見つけるごとに、その子以降は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            bce.append([]) # 今いる頂点の連結成分に含まれる辺を格納するlistを追加
            bcv.append([]) # 今いる頂点の連結成分に含まれる頂点を格納するlistを追加
            if stack[0][0] is not None: # 直前に通った頂点(関節点)が存在するなら
                bcv[idx].append(stack[0][0]) # それを連結成分idxに追加
            while stack:
                pre, now = stack.pop()
                if pre is not None: # 直前に通った辺が存在するなら
                    bce[idx].append((pre, now)) # 通ってきた辺を連結成分idxに追加 
                bcv[idx].append(now) # 今いる頂点を連結成分idxに追加
                if now == 0: # 今いる頂点nowが根で
                    if len(self.son[now]) >= 2: # 関節点であるなら
                        for next in self.son[now]:
                            is_ap[now] = True # 関節点であことを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        bce.pop() # 「根の関節点のみ」の連結成分は存在しないが追加してしまっているので、例外的に削除する
                        bcv.pop()
                        idx -= 1
                    else: # 関節点でないなら
                        for next in self.son[now]:
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                else: # 根でなく
                    for next in self.son[now]:
                        if self.low[next] >= self.ord[now]: # 子nextに対して関節点なら
                            is_ap[now] = True # 関節点であることを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        else: # 関節点でないなら
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                if now == 0 and len(self.son[now]) <= 1:
                    for back in self.back_edge[now]: # 今いる頂点から出る後退辺は同じ連結成分なので
                        bce[idx].append((now, back)) # 連結成分idxに追加
            idx += 1
        return bce, bcv, is_ap
    
    # block-cut treeを構築
    def block_cut_tree(self):
        bce, bcv, is_ap = self.biconnected_component() # 二重頂点連結成分分解
        num_ap = sum(is_ap) # 関節点の個数
        bc = [[] for _ in range(num_ap+len(bcv))] 
        # bc[i] := block-cut tree上の頂点iに対応する頂点を格納したlist
        # [0:num_ap)は関節点に対応する頂点で、その関節点のみがlistに含まれる
        # [num_ap:len(bc))は連結成分に対応する頂点で、その連結成分から関節点を除いたものがlistに含まれる
        # block-cut tree上の頂点iが関節点に対応している ⇔ i < num_ap
        bc_idx = [None]*self.n
        # bc_idx[i] := (元グラフの)頂点iが属するblock-cut tree上の頂点の番号(bc, bc_treeのindexに対応)
        # 関節点でない頂点iについて、対応するbce, bcvのindexが知りたい場合、bc_idx[i]-num_apで取得可能。
        bc_tree = [[] for _ in range(num_ap+len(bcv))] # bc_tree[i] := block-cut tree上の頂点iの隣接頂点を格納したlist
        idx = 0 # 今見ているblock-cut tree上の頂点番号
        for v in range(self.n): # (元グラフの)各頂点vについて
            if is_ap[v]: # 関節点なら
                bc[idx].append(v) # block-cut tree上の頂点idxにvを対応させる
                bc_idx[v] = idx
                idx += 1
        for bcv_i in bcv: # 各連結成分の
            for v in bcv_i: # 各頂点vについて
                if is_ap[v]: # 関節点なら
                    bc_tree[idx].append(bc_idx[v]) # block-cut tree上の頂点idxと関節点vに対応した頂点を辺で結ぶ
                    bc_tree[bc_idx[v]].append(idx)
                else: # そうでないなら
                    bc[idx].append(v) # block-cut tree上の頂点idxに対応した頂点集合に頂点vを追加
                    bc_idx[v] = idx
            idx += 1
        return bc, bc_idx, bc_tree, num_ap, bce, bcv, is_ap

類題

https://onlinejudge.u-aizu.ac.jp/problems/3022

H - Tourist on Graph

参考資料

lowlink

グラフにおける橋(bridge)を検出するアルゴリズム | アルゴリズムロジック

Biconnected component - Wikipedia

https://web.iitd.ac.in/~bspanda/biconnectedMTL776.pdf

オイラーツアー

オイラーツアーした木に対するクエリ - Qiita

Euler Tour のお勉強 | maspyのHP

*1: $xをyで\text{chmin} \underset{\text{def}}{\Leftrightarrow} x \leftarrow \text{min}\{x, y\}$

*2:オイラーツアーについて知りたい方は、参考資料に私が勉強する際に参考にさせて頂いた記事のリンクを掲載しておりますので、そちらを参照していただければと思います。

2022-07-24

【イベントソート】区間更新を遅延セグ木なしでやりたい話

この記事でやること
実現方法の説明
- イベントソートとは？
  - 平面走査による解法
  - 平面走査のための前準備
ソースコード
余談：どうせなら区間演算も遅延セグ木なしでやりたい
おわりに

この記事でやること

0埋めで初期化された配列に対する以下のようなクエリをオフライン（クエリ先読みができる状態）で処理する方法を考えます：

$L \quad R \quad X: \quad 配列の[L, R) をXに更新$
$T: \quad 配列のT番目の値を出力$

遅延セグ木を使えばオンラインで実現できますが、仕組みを理解し実装するのは結構難しいですし、機能的にはオーバーキルです。

（以下のサイトは私が遅延セグ木を勉強したときに参考にさせて頂いたものです。気になる方はこちらを参照して頂ければと思います。）

セグメント木を徹底解説！0から遅延評価やモノイドまで | アルゴリズムロジック

そこで、イベントソートというテクニックを使って、平衡二分探索木（wikipedia）を使えば解ける形に落とし込みます。

c++など平衡二分探索木が標準で用意されている言語であればこれで終わりなのですが、私が競プロで使っているPythonには残念ながら用意されていません。

自力で実装するには割と大変なデータ構造で、私もまだ実装したことないんですよね…。

載せてあるソースコードでは1行目でBBST(Balanced Binary Search Tree=平衡二分探索木)という名前のclassをimportしていますが、これは、比較的実装しやすいデータ構造であるBIT(Binary Indexed Tree)で同様の機能を再現したもので、本当の平衡二分探索木ではありません。その辺の話は気が向いたらそのうちまた記事を書くと思います。（多分）

（BITについて気になる方は下記のサイトを参照してみてください。）

Binary Indexed Tree (BIT) 総まとめ！区間加算や二次元BITまで | アルゴリズムロジック

実現方法の説明

イベントソートとは？

平面走査を行う上での前準備のことです。

平面走査って何ぞ？という方も、図を見れば雰囲気は掴めるかと思いますのでご安心ください。

平面走査による解法

各クエリを、横軸 $i$ が配列のindex、縦軸 $j$ がクエリの番号とした座標平面に図示してみます。

この座標平面を、 $i$ について昇順に走査します。

$i$ を時間軸、各クエリを「決まった時間に開始・終了するイベント」と捉え、「進行中の更新イベントの番号」を記録しながら時間を進めていきます。

$i = 2$ に到達すると、回答イベント $j = 4$ が発生します。このとき、元の配列の $i = 2$ 番目のデータは、進行中の更新イベントのうち $j = 4$ より小さい番号で最大のものを参照すればよいです。

ということは、「進行中のイベントの番号」を平衡二分探索木で記録しておけばよさそうです。正確に書くと、

更新イベント開始： $insert(-j)$
更新イベント終了： $erase(-j)$
回答イベント： $k = -upper\_bound(-j)$ として、 $X_k$ を出力*1

とすることで各イベントが $O(logQ)$ 処理できます。

平面走査のための前準備

実際に上記の平面走査を行うためには、 $(イベントの時刻i, イベントの番号j, イベントの種類q \in \{1, 2, 3\})$ という3つの情報を持ったデータを昇順にソートしておきます。（これをイベントソートと言います。）

あとは、尺取り法の要領でイベントを処理していけばよいです。

ソースコード

(Python3.8.3)

from BBST_like import BBST

if __name__ == "__main__":
    N, Q = map(int, input().split()) # 配列の長さ、クエリの数
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    # イベントソート
    events = []
    for j in range(Q):
        query = querys[j]
        if len(query) == 3:
            l, r, x = query
            events.append((l, j, 1))
            events.append((r, j, 2))
        else:
            t = query[0]
            events.append((t, j, 3))
    events.sort()

    bbst = BBST(list(range(Q)))
    # 平衡二分探索木のようなもの。引数は気にしなくいいです。
    #「bbst.lt(x): key < x を満たす最大のkeyを取得」という関数を用意してあるので、
    # 解説のように-1倍してupper_boundをする、という実装はしてません。
    
    # 平面走査
    ans = [None]*Q
    e = 0 # eventのindex
    for i in range(N): # iについて昇順に走査
        while e < len(events) and events[e][0] == i: # 発生したイベントを処理
            i, j, q = events[e]
            if q == 1:
                bbst.insert(j)
            elif q == 2:
                bbst.erase(j)
            else:
                k = bbst.lt(j)
                if k is None:
                    ans[j] = 0
                else:
                    ans[j] = querys[k][2]
            e += 1

    for a in ans:
        if a is not None: print(a)

"""
入力例
10 5
1 4 2
2 5 1
3
0 4 3
2

出力
1
3

"""

余談：どうせなら区間演算も遅延セグ木なしでやりたい

競プロ典型90問に、遅延セグ木が想定解の問題がありました。

atcoder.jp

区間演算の結果を利用して区間更新しろという無茶ぶり。これを遅延セグ木を使わずに解く方法ってあるのでしょうか？

私には思いつかないので、もしわかる方がいらっしゃれば教えていただけると幸いです。

追記

rsk0315さんに解説を書いていただきました。ありがとうございます！

atcoder.jp

おわりに

遅延セグ木を勉強した方が手っ取り早いのでは？と言われると、それはそう…

でもまあ、イベントソートないし平面走査はとても重要な典型知識だと思うので、頭の片隅にでもいれておきましょう。

逆張りオタクのような内容の記事でしたが、最後までお読みいただきありがとうございました。

*1:upper_bound(x)は「xより大きい最小の値」を求めるので、-1倍して大小関係を反転させています。

2022-07-23

最大・最小・指定キー削除をヒープで実現する話

この記事でやること
前提知識：（最小）ヒープとは
発想
- push(x), get_min(), get_max()
- erase(x)
ソースコード

この記事でやること

Python3のheapqを使い、以下の操作ができるデータ構造を実装します：

push(x): xを追加 $O(\text{log}N)$
erase(x): xを削除 $amortized\_O(\text{log}N)$
get_min(): 最小値を取得 $amortized\_O(1)$
get_max(): 最大値を取得 $amortized\_O(1)$

ソースコードはご自由にお使いください。

前提知識：（最小）ヒープとは

以下の操作ができるデータ構造です：

push(x): xを追加 $O(\text{log}N)$
pop(): 最小値を削除 $O(\text{log}N)$
get(): 最小値を取得 $O(1)$

仕組みが知りたい方はwikipediaを参照してください。

（このwikiによると、指定キー削除は二分ヒープのノードを指すポインタを別に管理することでできるようなので、ヒープを一から自作するなら参考にするとよいと思います。）

発想

push(x), get_min(), get_max()

最小ヒープと最大ヒープを両方持っておくだけで実現できます。heapqは最小ヒープなので、最大ヒープとして扱いたければデータを-1倍してpushすればいいでしょう。

erase(x)

遅延評価というテクニックを使って実現します。

実際にヒープから削除するのではなく、「xは削除済みである。」という情報だけ記憶しておきます。そして、後のget_min(), max_min()でもしxが取得されたなら、そのタイミングでヒープからpopします。

実装では、連想配列(defaultdict)で各要素の個数を管理しておき、個数が0のものがgetされたらヒープからpopするようにしています。

ソースコード

（Python3.8.3）

from collections import defaultdict
from heapq import heappush, heappop

class MinMaxHeap:
    
    def __init__(self, array=[]):
        self.hq_min = [] # 最小ヒープ
        self.hq_max = [] # 最大ヒープ
        self.cnt = defaultdict(int) # cnt[x] := xの個数
        self.size = 0 # 要素数
        for a in array:
            self.push(a)
    
    def push(self, x):
        # xを追加
        heappush(self.hq_min, x)
        heappush(self.hq_max, -x)
        self.cnt[x] += 1
        self.size += 1
    
    def erase(self, x):
        # xを削除（複数あれば1つだけ、無ければ何もしない）
        if self.cnt[x]:
            self.cnt[x] -= 1
            self.size -= 1
    
    def get_min(self):
        # 最小値を取得（空ならNone）
        while self.hq_min and self.cnt[self.hq_min[0]] == 0:
            heappop(self.hq_min)
        if self.hq_min:
            return self.hq_min[0]
        return None
    
    def get_max(self):
        # 最大値を取得（空ならNone）
        while self.hq_max and self.cnt[-self.hq_max[0]] == 0:
            heappop(self.hq_max)
        if self.hq_max:
            return -self.hq_max[0]
        return None
    
    def __len__(self):
        # len()で要素数を取得
        return self.size
    
    def __repr__(self):
        # {各要素: 個数} の形で表示される。
        return self.cnt

使用例：

ABC253-C問題

Submission #33418423 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

2022-07-09

ICPC 2022 国内予選参戦記

2022/07/08に開催された ICPC 2022 国内予選に、大学の先輩2人とチーム【thorny castle 】を組んで参加しました。

icpc.iisf.or.jp

そして、結果は4完で47位。

https://icpcsec.firebaseapp.com/standings/

公式の発表はないので手計算での集計ですが、おそらく国内予選を通過しました！

ICPC 2022 国内予選結果 | ICPC 2022 Asia Yokohama Regional

国内予選を通過したと正式に発表されました！（7/14更新）

私は今回先輩に誘われてのICPC初参加でしたが、こうした大舞台で結果を残せたのは本当に嬉しいです。

この記事では、その思い出の記録として、大会での大まかな進行や私が関与した問題での会話の内容等を書いていきます。（先輩2人の呼称は「先輩A」, 「先輩S」とします。）

大会の参加形態

本大会はオンライン開催と言うことで、まずチーム3人で集まるか各自自宅等で通話しながら参加するかを選ぶことができました。

最初は大学の理学部棟で一部屋借りようかという話でしたが、昨今の大学全体のwi-fiの不安定さを考慮して各自自宅から参加ということになりました。（こんな理由で集まるのを断念しているチームはうちだけなのでは？？）

作戦

初動でA,B,C問題を3人で並列して担当し、以降は流れで解けそうなやつを頑張ろう、という感じ。

AtCoderのレート順で、私はA問題を担当することになりました。ゴリッゴリの早解き勝負です。ﾑﾘ…

問題のページ↓ （問題の内容把握は記事内では省略します。）

icpc.iisf.or.jp

大会中の私がやったこと

A問題-全部
D問題-考察

A問題

やるだけ問題。一目見た瞬間から実装開始。しかし、往々にしてこういうやるだけ問題では実装の速度が顕著に表れるもの。お隣の46位、48位のチームはどちらも3分台でACしていますが、私は6分弱かかってしまいました。反省。

何はともあれ初動の並列パートを突破したので、とりあえずD, E問題を眺めることにしました。

D問題

しばらくして両先輩もB, C問題を突破。ここからは先輩SとD問題を考察し始めました。以下は会話形式で考察の過程を書きます。

私「tを後ろから見ていけば入場する列が構築できそうな気がします。」

先輩S「あー、行けそう。」

先輩S「なんかdpやりたくなるけど遷移ヤバそうじゃない？」

私「いや、縦に置けるのはsで連続で並んでるときだけなので、高々遷移は2通りです。」

先輩S「確かに。じゃあdpには『今何列置いたか』を持って…ああでも『それまでの各列の先頭にある値の最小値』を超えていると横には置けないから、それも処理しなくちゃいけないのか。」

私「あー…」

先輩S「dpの状態に『それまでの各列の先頭にある値の最小値』を持ったとしても、もしその最小値を隠すように大きい数字を縦に置いた場合、そのとき『各列の先頭にある値』がわからないから最小値の更新ができない。困った。」

私「うーん…」

私「『縦に並べるときに最小値が更新できない』のは、今置いた数が先に置かれてた数よりも大きいときですよね？」

先輩S「そうだね。」

私「その場合って、横にも置けないですよね。だったらなんか事前に処理しておくこととかってできませんかね？こう…ニコイチに纏めるとか…」

先輩S「つまり、tで単調減少の部分がsでも連続しているなら縮約しておく…？」

私「縮約…それって操作後はtが単調増加列になったりしません？」

先輩S「例えばt = [3, 1, 2] で考えると、3, 1を縮約してt = [3, 2]になる。これをまた縮約してt = [3]になる。確かに単調増加列にはなると思うけど、こんな操作していいのか？よさそう（自己解決）」

私「ええっと…確かによさそうですね。」

先輩S「単調増加列になると何が嬉しい？」

私「後ろから見れば単調減少列なので、最小値とか気にせずとも必ず横に並べることができます。」

先輩S「なるほど！じゃあ列の数だけ持ってdpできる！」

私「勝った！！」

というわけで、先輩Sが実装して無事ACしました。

ベンチ温めタイム

E問題で先輩Aと合流。

先輩S「これ無理くないです？」

私「なんですかねこれ…線形計画…？」

先輩S「いやー、こんなキモい牛ゲーやりたくない。」

私「カッコ列…」

先輩S「二次元カッコ列dpとか聞いたことない。」

先輩A「二次元カッコ列dpwww」

と言った雑談をしつつ、

先輩A「1の列または行は、最初は確定で+、最後は確定で-。」

私「0の行と列の交差点は-にしてよさそうです。」

先輩S「あとは『枝刈りdfs書いて実は間に合います』くらいしか思いつかないですね。」

と考察を進めつつもタイムアップ。

感想

個人的な出来栄えについては、そこそこ頑張れたんじゃないかと思っています。特にD問題の考察パートは全てを出し切った気がします。

ただ、実装についてはダメダメでしたね、A問題は早解きと言えるスピードではありませんでしたし、D問題は自分も実装してはいましたが、あまりにも遅すぎて結果的に先輩に任せてしまうような形になってしまいました。

先輩方には頭が上がりません。B問題は実装がかなり重そうで、C問題はなんだか難しそう（小並）。もし私が担当していたら通せた自信は正直ありません。

全体の感想としては、通話での思考の共有の難しさを実感しました。D問題の考察を会話形式で書きましたが、実際あれを口頭で実行していました。なんで意思疎通できたんでしょうね？

アジア地区大会への意気込み

アジア地区大会は、12月に横浜にて開催される予定です。

ここで、重大な問題が一つあります。アジア地区大会での問題文は全て英語なのですが、チーム全員が英弱と言うことが発覚しました。終わった…。

昨年度の問題をちらっと見た限り、正直僕レベルのなんちゃって競プロerでは手も足も出なさそうな雰囲気がありますが、まあ出るからには全力を尽くしたいです。頑張ります。

それではこの辺で〆ます。最後までお読みいただきありがとうございました。