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に対応した頂点」部分でブロックされることになります。

はい。

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

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

043 - Maze Challenge with Lack of Sleep（★4）の解説

何の話かと言うと

atcoder.jp

この問題をネタに「重み0のリンクで結合されたノードを同一視する」という話をします。

一般的な解法

まず、この問題の一般的な解法は、01-BFS になります。

方向転換を考慮する必要があるので、座標 (x, y) + 方向（上下方向 or 左右方向）をノードとします。たとえば、

・(1, 1, '|') : 座標 (1, 1) を上下方向に移動中
・(1, 1, '-') : 座標 (1, 1) を左右方向に移動中

という感じです。そして、これらのノードをリンクで結合します。

座標を変えずに方向だけ変えるリンクを重み 1 とします。

・(1, 1, '|') <----> (1, 1, '-') : 重み 1

ただし、スタートとゴール地点での方向転換は重み 0 にします。（スタート地点での方向転換は自由なので。）

今向いている方向への移動を表すリンクを重み 0 とします。

・(1, 1, '|') <----> (1, 2, '|') : 重み 0
・(1, 1, '-') <----> (2, 1, '-') : 重み 0

あとは、これらで構成される無向グラフについて、スタートからゴールの最小距離を検索します。（スタートとゴールでの方向は任意の方向を1つ決めればOK。スタートとゴール地点の方向転換は重み 0 に注意してください。）

一般には、ダイクストラを使えばOKですが、Python だとギリギリ TLE になります。

そこで、ダイクストラより効率的な 01-BFS を利用します。（これは、リンクの重みが 0 / 1 だけの場合に使えます。）

※ 01-BFS の解説はこちらがお勧め。
betrue12.hateblo.jp

で、実際の結果はこうなります。

atcoder.jp

いちおうパスしていますが、1838 ms で、けっこうギリギリ感はあります。

重み 0 でつながるノードを同一視

上記のコードでは、conv() 関数で、「座標 + 方向（0 / 1 で表現）」で表した状態を単一の数値のノード番号に変換しています。

仮に、(1, 1, 0) と (2, 1, 0) が重み 0 のリンクで繋がっていた場合、これらを区別せずに同一のノード番号にマッピングしてしまっても構いません。

ただし・・・・

それぞれのノードがリンクを持っている場合、それぞれのリンクを融合するという、ちょっと面倒な処理が必要になります。

なのですが・・・

上記のコードでは、リンク情報を構築する際に、

  for y in range(1, H+1):
    for x in range(1, W+1):

という方向にマス目をスキャンしながら、

・(x, y) から見て、右と下にあるマス目 (x+1, y)、および、(x, y+1) とのリンクを追加する

という処理をしています。（この順番であれば、左と上のマス目は、ダブルカウントになるので、考えなくてよいですよね・・）

そうすると・・・

・(x, y) から見て、右と下にあるマス目 (x+1, y)、および、(x, y+1) は、スキャン前なので、まだリンク情報を持っていません。

したがって、「(x+1, y)、もしくは、(x, y+1) を (x, y) と同一視する」という処理、つまり、「(x+1, y)、もしくは、(x, y+1) を (x, y) と同一のノード番号にマッピングする」という処理は、リンクの引き継ぎを気にせずに行うことができます。

ノードの同一視については、（Union-Find の発想を借りて）次のように実装します。

まず、conv() では、ノード番号を取得した後、さらにその親のノード番号を返すようにします。

def conv(x, y, d):
  global H, W, parent
  i = x + (y-1) * W + d * (H*W)
  if parent[i] == None:
    parent[i] = i
  return parent[i]

で、ノードを同一視させたくなったところで、親の情報を書き換えます。

      if exists(x+1, y):
        p0 = conv(x, y, 0)
        p1 = conv(x+1, y, 0)
        parent[p1] = p0

一般には、親の親を再帰的に検索する必要がありますが、今回の場合は、スキャンの順序を（落ち着いて）考えると、再帰的な検索は不要とわかります。

実際にこれを実装したのがこちらになります。

atcoder.jp

801 ms で、確かに高速化されました。（ちなみに、この処理をしておけば、ダイクストラでもギリギリ間に合いました。）

とことんやってみる

上記のコードでは、隣り合うマス目を（連鎖的に）同一視していますが、よく考えると、スタート地点とゴール地点の方向転換についても、同一視ができます。（スタートとゴールでは方向転換のリンクは重み 0 なので。）

ただし、この部分では、先に触れたノードの引き継ぎが必要になります。さらに、同一視の連鎖が一方向にならない可能性があるので、（本物の Union-Find と同様に）親の検索を再帰的に実装する必要があります。

def conv(x, y, d):
  global H, W, parent
  i = x + (y-1) * W + d * (H*W)
  if parent[i] == None:
    parent[i] = i
  while i != parent[i]:
    i = parent[i]
  return i

ここまでやる必要があるかは疑問ですが、仮に、ここまでやると、重み 0 のリンクが完全になくなり、重み 1 のリンクのみになります。なので、01-BFS ではなく、普通の BFS での探索が可能になります。

というわけで、ものは試しでやってみました。

atcoder.jp

965 ms とちょっと遅くなりました。親の再帰的な検索の時間がオーバーヘッドになっているような気がします。（たぶん。）