068 - Paired Information（★5）の解説

何の話かというと

atcoder.jp

上記の問題をネタに、Union-find の解説と、Union-find の特徴を利用した別解を紹介します。

Union-find

Union-find の基本的な実装はこちらになります。

group_parent = defaultdict(lambda:None)
 
def create_group(x):
  global group_parent
  group_parent[x] = x
  return x

def get_group(x):
  global group_parent
  p = group_parent[x]
  if p == None:
    return None
  while group_parent[p] != p:
    p = group_parent[p]

  # 最適化
  p = group_parent[x]
  group_parent[x] = real_p
  while group_parent[p] != p:
    p = group_parent[p]
    group_parent[p] = real_p

  return p
 
def merge_group(x, y):
  global group_parent
  group_parent[get_group(y)] = get_group(x)

グループ分けしたい（Hashable な）オブジェクトに対して、グループ ID を割り当てて、必要に応じてグループをマージしていくことができます。

・create_group(x) : グループ ID を持たないオブジェクト x に新しいグループ ID を割り当てて、グループ ID を返す。

・get_group(x) : オブジェクト x のグループ ID を返す。（グループ ID を持たない場合は None が返る。）

・merge_group(x, y) : オブジェクト x の属するグループとオブジェクト y の属するグループをマージする。（オブジェクト y の属するグループのグループ ID をオブジェクト x の属するグループのグループ IDに変更する。）

実装の中身に注目すると、各オブジェクト x に対して、グループ ID を示す p = group_parent[x] を割り当てるのですが、グループ ID p 自身もさらに group_parent[p] を持っています。仮に、p == group_parent[p] （自己参照）の場合は、p が正しいグループ ID になりますが、p != group_parent[p] の場合は、group_parent のチェインをたどっていって、px == group_parent[px] となった時点で、px が正しいグループ ID になります。

このチェイニングは、グループをマージする際に発生するもので、x と y のグループ ID を px, py とする時、元々は、

・group_parent[px] = px

・group_parent[py] = py

となっているわけですが、これを

・group_parent[py] = px

と書き換えることで、グループをマージすることができます。

ただし、グループのマージが連続すると、group_parent のチェインが長くなり、get_group(x) の処理時間が伸びます。そこで、get_group(x) を実行した際は、最終的に発見されたグループ ID real_p を用いて、チェインに含まれる group_parent が指す先を real_p に置き換えてショートカットします。（先ほどの実装の「# 最適化」とコメントした部分。）

問題の解説

数列の隣り合う2項の関係が与えられていくので、Union-find を用いて、与えられた関係でつながった項をグループ化していきます。その後、x と y の関係についての Query が与えられた際に、x と y が同じグループであれば、Query に答えることができます。

そして、公式解説 では、すべての Query を読み込んだ後に、Query の答えを計算する順序を工夫することで、計算量を減らすという手法（バッチ方式）が説明されていますが、ここでは、別解として、Query を読み込みながら答えていく方法（オンライン方式）を考えてみます。

まず、この問題では「隣り合う2項の和」が与えられますが、ちょっと工夫すると、「隣り合う2項の差」が与えられる問題に置き換えることができます。具体的には次の置き換えをします。

・ と の和 を に置き換える

・ の値 を に置き換える

「隣り合う2項の差」になると何が嬉しいかというと、部分和のテクニックが使えることです。たとえば、すべての隣り合う項の差がわかっている場合であれば、これらを加えることで、 を事前に計算することができます。これにより、任意の x, y について、 と の関係を と で計算することができます。

今回の問題では、互いにつながった項のグループが分かれるので、グループごとに同様の計算をすることが考えられます。グループの先頭の項を として、グループごとに を計算するのです。先ほどの Union-find の実装を思い出すと、（「# 最適化」の処理を削除すれば）要素 x に対して、get_group(x) で得られるグループ ID が、ちょうど、グループの先頭の要素になることに気がつきます。

グループをマージする際は、マージする各グループの先頭の要素間の差を記録しておきます。これにより、複数のグループがマージされた後でも、group_parent[x] のチェーンをたどりながら差分を加えることで、 を（ とまではいきませんが）効率的に計算することができます。

実装結果はこちらになります。

atcoder.jp

※ この解法、最悪計算時間は になるので、最悪計算時間になるように意図的に組まれたデータに対しては TLE になります。

060 - Chimera（★5）の解説

何の話かと言うと

atcoder.jp

上記の問題の簡単な解説です。（特に捻りはありません・・・。）

単調増加部分列の長さ

基本は、与えられた数列を順番にスキャンしながら、

・dp[k] = v # 長さ k の部分列を取り出した際の最後の値（の最小値）が v

を更新していくという方法です。dp は、

・dp = [-Inf, Inf, Inf,..., Inf]

で初期化しておきます。

dp は単調増加になるので、n 番目の要素 A[n] を考えた際に、A[n] よりギリギリ小さい v の位置は、二分探索で高速に検索できます。

・index = (A[n] よりギリギリ小さい v の位置) + 1

として、

・dp[index] = min(dp[index], A[n])

で、dp が更新できます。次のように、非常にシンプルに実装が可能です。

  dp = [10**30] * (N+1) # dp[長さ] = 最後の値（の最小値）
  dp[0] = -10**30
  for i in range(N):
    index = bisect.bisect_left(dp, A[i])
    dp[index] = min(dp[index], A[i])

最後に dp[k] < Inf である最大の k が単調増加部分列の最大の長さを与えます。

A[n] を採用した場合の部分列の長さ

冒頭の問題は、前半が単調増加、後半が単調減少という組み合わせになっているので、

・単調増加列の末尾が A[n] だった場合の単調増加列の長さ ---- (1)
・単調減少列の頭が A[n] だった場合の単調減少列の長さ ---- (2)

という情報が必要になります。

(1) については、上記の dp とは別に、

・dp2[i] = k # A[i] を末尾とした場合の単調増加列の長さは k

という情報を記録していきます。さきほどの実装を次のように修正すればOKです。

  dp1 = [10**30] * (N+1) # dp1[長さ] = 最後の値（の最小値）
  dp1[0] = -10**30
  dp2 = [-1] * N # dp2[i] = A[i] を末尾とした場合の長さ
  for i in range(N):
    index = bisect.bisect_left(dp1, A[i])
    dp1[index] = min(dp1[index], A[i])
    dp2[i] = index

(2) については、A を反転させて (1) を求めて得られたものをもう一回反転すればOKですね。

  A.reverse()
  dp3 = [10**30] * (N+1)
  dp3[0] = -10**30
  dp4 = [-1] * N
  for i in range(N):
    index = bisect.bisect_left(dp3, A[i])
    dp3[index] = min(dp3[index], A[i])
    dp4[i] = index
  dp4.reverse()

(1)(2) の情報があれば、折り返し点を A[0], A[1], ... とした場合、それぞれでの最長部分列（の合計）を個別に計算することができます。

atcoder.jp

054 - Takahashi Number（★6）の解説

何の話かと言うと

atcoder.jp

この問題、公式解説では、「新たな頂点を追加してリンク数を削減する」というテクニックが紹介されています。実は、これを知らなくても、もう少し自然な発想で「本質的に同じ解法」にたどり着けるという話をします。

基本的な考え方

論文の共著者を（重さ1）のリンクで接続したグラフを作成して、「研究者1」からの最短距離をBFS（幅優先探索）で計算します。この際、共著者のリストからリンクの情報を愚直に構成すると、次のような処理になるでしょう。

  link = [[] for _ in range(N+1)]
  for _ in range(M):
    K = int(f.readline())
    R = list(map(int, f.readline().split()))
    for i in range(K):
      for j in range(i, K):
        link[i] = j
        link[j] = i

しかしながら、 であることから、この2重ループは で TLE になります。

2重ループを用いずにリンク情報を構成する方法としては、次のように、研究者ごとに共著者リストを（重複を気にせずに）積み上げる方法があります。

  link = [[] for _ in range(N+1)]
  for _ in range(M):
    K = int(f.readline())
    R = list(map(int, f.readline().split()))
    for i in range(K):
        link[i].append(R)

この場合、研究者 i からリンクされた研究者 j を取得する際は、次のような2重ループを使用します。

  for r in link[i]:
    for j in r:
      # j は i からリンクされたノード
      # 重複処理のチェックが必要

しかしながら、この方法の場合、重複が多すぎて、BFS の探索で TLE します。困りましたね。。。

論文単位で重複排除

上記の（2つ目の）アイデアにおいて、重複がどのように生じるかを考察してみましょう。ある論文 X に [i, j, k, l] の4人の研究者が入っていた場合、i, j, k, l のそれぞれに対して、[i, j, k, l] というリンク情報が追加されます。

そして、BFS による探索中に、はじめに、研究者 i の高橋数が決まったとします。すると、次のステップで、論文 X を通じて、j, k, l の高橋数が決まります。この時点で、論文 X の役割は終わります。つまり、j, k, l が持つ [i, j, k, l] というリンク情報は不要になります。

つまり、リンク情報は、論文単位で処理されていき、1つの論文は1回だけ処理すれば十分なのです。

そこで、研究者 i のリンク情報を

link[i] = [r1, r2, r3,...] # r1, r2, r3 は研究者 i が参加した論文のインデックス

という形で保存して、明示的に論文単位で処理を進めます。そして、論文ごとに「処理済みフラグ」を用意しておき、処理済みフラグが立った論文は、まるごとスキップします。実装を示すと次の通りです。

  N, M = map(int, f.readline().split())
  paper = [[] for _ in range(N+1)] # paper[i] 研究者 i が参加した論文
  authors = [[] for _ in range(M)] # authors[p] 論文 p の著者
  tkn = [10**30] * (N+1)
  tkn[1] = 0
  flag = [False] * M # 論文ごとの処理済みフラグ
 
  for p in range(M):
    K = int(f.readline())
    R = list(map(int, f.readline().split()))
    authors[p] = R
    for i in range(K):
      paper[R[i]].append(p)
 
  q = deque()
  q.append(1)
  while q:
    i = q.popleft()
    n = tkn[i]
    for p in paper[i]: # 論文単位でリンクを処理
      if flag[p]: # 処理済みの論文はスキップ
        continue
      flag[p] = True
      for j in authors[p]:
        if n + 1 < tkn[j]:
          tkn[j] = n + 1
          q.append(j)

これで、無事に通ります。

atcoder.jp

「新たな頂点」と「論文」の対応関係

と、ここまでを理解した上で、再度、公式解説 の図を見てください。

ここでは、論文ごとに「新たな頂点」を用意して、これを経由して、論文の共著者をリンクしています。この場合、論文 X の共著者の1人、i の高橋数が（他のリンク経由で）決定すると、論文 X に対応した頂点を通じて、他の共著者の高橋数が決まります。この時点で、論文 X に対応した頂点が処理済みになるので、これ以降は、論文 X を介したつながりはすべて「論文Xに対応した頂点」部分でブロックされることになります。

はい。

これは、先ほどの「論文単位でリンクを処理する」という実装と本質的に同じことですね。

公式解説をいきなりみると、「新たな頂点を追加する」という発想がどこから生まれたか不思議に感じるかもしれませんが、グラフのリンク構造が「論文」という固まりで構成されているからこそ、このようなテクニックが利用できるわけなのです。