めもめも

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

072 - Loop Railway Plan(★4)の解説

何の話かというと

atcoder.jp

上記の問題をネタに「キューを用いた全件探索」の話をします。

キューを用いた全件探索

enakai00.hatenablog.com

上記の記事では、キューを用いて木構造データを探索するという話をしています。木構造データに限らず、複数の選択肢を網羅的に探索する際には、同様の手法が利用できます。

大雑把な考え方は、次の通りです。

(1) 処理中のデータについて、「次にやるべき処理」に複数の選択肢があり、選択によって処理後のデータが変わり、その先の処理がブランチしていく、というような状況を考えます。

(2) 処理後のそれぞれのデータを個別に用意して、それらをキューに詰め込んでおきます。

(3) キューからデータを取り出して、次の処理を行います。処理結果を再びキューに詰め込みます。

これを繰り返すことにより、複数の選択肢の組み合わせパターンをすべて網羅することができます。ただし、処理対象のデータが多い場合、(2) でデータの複製が発生するので、この部分の処理時間が長くなります。そのため、探索範囲が広い場合は、データの複製量を減らすなどの工夫が必要です。(Python のリストは参照渡しの Mutable オブジェクトなので、明示的に copy.copy / copy.deepcopy する必要がある点に注意してください。)

下記の問題は、探索範囲を制限する、データの複製を必要な場合に限定する、という両方の工夫を詰め込んだ例になります。

enakai00.hatenablog.com

そもそも探索量が少ない場合

冒頭の問題は、フィールドのサイズが 16 x 16 と小さいので、すべてのデータをコピーしながら全件探索しても十分に間に合うと予想できます。公式解説 では、バックトラックが紹介されていますが、愚直にすべてのパターンを検索しても大丈夫です。つまり、次に進めるすべての方向に処理をブランチして、キューに詰め込んでいきます。

また、出発地点についてもすべてのパターンを検索する必要がありますが、すでに発見された経路に含まれる位置は、出発地点にする必要はありません。これらを実装すると下記になります。

atcoder.jp

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 の世界(つまり、次の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

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

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

atcoder.jp