めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

071 - Fuzzy Priority（★7）の解説

何の話かというと

atcoder.jp

上記の問題をネタに、「極端に小さな制約条件に注目する」という話をします。

まぁ、下記のネタと似たような話です。

enakai00.hatenablog.com

K=1 の場合

ポイントは、1\le K\le 10 という条件です。一般には、もっとたくさんの順列が選べるはずなのですが、なぜか、10 個だけ選べばOKです。

この条件をどう使うかを考えるのがミソですが・・・、たとえば、小課題 2 にある K=1 の場合、つまり、特定の 1 つだけ見つければ良い場合はどうなるか考えてみましょう。

この場合は、Greedy search でいけます。

はじめに、A -> B （B は A の後に選ばないといけない）という条件を有向グラフとして構成して、各ノードに入ってくるリンクの数を記録しておきます。入ってくるリンク数が 1 以上のノードは、まだ利用することができません。つまり、リンク数が 0 のノード
のどれか 1 つを選んで、選んだノードからのリンクは削除する、という処理を N 回繰り返せばOKです。N回繰り返す前に、リンク数が 0 のノードがなくなった場合は、条件を満たす順列は存在しないことになります。

さっくり実装するとこんな感じですね。

atcoder.jp

このコードでは、リスト candidates に、リンク数が 0 のノードを記録しておき、candidates.pop() で 1 つ取り出すということを繰り返しています。

K>1 の場合

candidates に保存されたノードの中から、複数のノードを選んで、それぞれについて処理をブランチさせれば、条件を満たす複数の順列が構成できます。ブランチした「世界」ごとに、「これまでに選んだノードの列」「リンク数のカウント」「次に選べる候補のリスト candidates」のそれぞれが異なるので、ブランチするごとにこれらをコピーする必要があります。キューを用いた再帰処理で実装すると、次のようになります。

def get_list():
  global N, M, K, link_from, link_to_count

  candidates = []
  for i in range(1, N+1):
    if link_to_count[i] == 0:
      candidates.append(i)
  result = []

  q = deque()
  q.append(([], candidates, link_to_count))
  while len(result) < K:
    line, candidates, link_to_count = q.pop()
    if len(candidates) == 0:
      if len(line) == N:
        result.append(line)
        continue
      return None

    for index, i in enumerate(candidates):
      line2 = copy.copy(line)
      line2.append(str(i))

      candidates2 = copy.copy(candidates)
      del candidates2[index]

      link_to_count2 = copy.copy(link_to_count)
      for j in link_from[i]:
        link_to_count2[j] -= 1
        if link_to_count2[j] == 0:
          candidates2.append(j)
      q.append((line2, candidates2, link_to_count2))
  return result

理屈上はこれでOKですが、「これまでに選んだノードの列」「リンク数のカウント」「次に選べる候補のリスト candidates」をコピーする処理（最悪ケースで O(N)）が何度も行われるので、間違いなく TLE します。これらのコピー処理の回数を減らす方策が必要です。

で、ここで利用できるのが、K\le 10 という条件です。上記のコードは、すべての可能なパターンを網羅するロジックになっていますが、実際には、K 種類だけ発見すればよいので、すべての「並行世界」をたどる必要はありません。キューの中に溜まっている検索中の「世界」は、「K - 発見済みの順列の本数」に絞ることができます。

さらに、len(candidates) == 1 の世界（つまり、次の１手ではブランチしない場合）、あるいは、必要な数のブランチ処理が終わって、十分な数の「世界」がキューに詰まってしまえば、上記の情報をコピーする必要はありません。キューから受け取った情報をそのまま使い回すことができます。

これらの制限を入れると無事に通ります。

atcoder.jp

ちなみに、この解法に気がつくポイントは、N\le 10^5,\ K\le 10 という組み合わせにあります。先ほどのコピー処理は、O(N) ですが、N\le 10^5 という条件があるので、10 回程度の繰り返しは大丈夫そうだと気が付きます。この 10 回が、ちょうど、K に一致しています。なので、K 種類の答えを見つけるために、K 回のブランチならば大丈夫とわかります。

070 - Plant Planning（★4）の解説

何の話かというと

atcoder.jp

この問題をネタに L1 ノルムの最小化の話をします。

L2 ノルムの最小化

平面上の点の集合 (x_i,\,y_i)\ (i=1,2,\cdots,N) に対して、各点との「ユークリッド距離の2乗の話」

　\displaystyle E = \sum_{i=1}^N\left\{(x-x_i)^2+(y-y_i)^2\right\}

を最小にする点 (x,\,y) は、

　\displaystyle\frac{\partial E}{\partial x} = 0,\ \frac{\partial E}{\partial y} = 0

の条件から、与えられた点の集合の重心に一致することがわかります。

　\displaystyle x = \frac{1}{N}\sum_{i=1}^Nx_i,\ y = \frac{1}{N}\sum_{i=1}^Ny_i

L1 ノルムの最小化

平面上の点の集合 (x_i,\,y_i)\ (i=1,2,\cdots,N) に対して、各点との「マンハッタン距離の話」

　\displaystyle E = \sum_{i=1}^N\left\{\sqrt{(x-x_i)^2}+\sqrt{(y-y_i)^2}\right\}

を最小にする点 (x,\,y) は、

　\displaystyle\frac{\partial E}{\partial x} = 0,\ \frac{\partial E}{\partial y} = 0

の条件から決まります。上記の偏微分を実行すると、次の条件が得られます。

　\displaystyle \sum_{i=1}^N\frac{x-x_i}{|x-x_i|} = 0,\ \sum_{i=1}^N\frac{y-y_i}{|y-y_i|} = 0

これは、次のように言い換えることができます。

　\displaystyle\sum_{i=1}^N{\rm sign}(x-x_i) = 0,\ \sum_{i=1}^N{\rm sign}(y-y_i) = 0

つまり、x と x_i の差の符号、つまり、x が x_i の右にいるか、左にいるかの合計が 0 になればよく、x として、\{x_i\}_{i=1}^N の中央値を選択すればよいことになります。y についても同様です。

というわけで、非常にシンプルに問題の答えが得られます。

atcoder.jp

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項の差」が与えられる問題に置き換えることができます。具体的には次の置き換えをします。

・A_x と A_{x+1} の和 V を -(-1)^xV に置き換える

・A_x の値 V を (-1)^x V に置き換える

「隣り合う2項の差」になると何が嬉しいかというと、部分和のテクニックが使えることです。たとえば、すべての隣り合う項の差がわかっている場合であれば、これらを加えることで、 D_x = A_x - A_1\ (x=2,3,...,N) を事前に計算することができます。これにより、任意の x, y について、A_x と A_y の関係を A_y = A_x + (D_y-D_x) と O(1) で計算することができます。

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

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

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

atcoder.jp

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