の場合
ポイントは、 という条件です。一般には、もっとたくさんの順列が選べるはずなのですが、なぜか、10 個だけ選べばOKです。
この条件をどう使うかを考えるのがミソですが・・・、たとえば、小課題 2 にある の場合、つまり、特定の 1 つだけ見つければ良い場合はどうなるか考えてみましょう。
この場合は、Greedy search でいけます。
はじめに、A -> B （B は A の後に選ばないといけない）という条件を有向グラフとして構成して、各ノードに入ってくるリンクの数を記録しておきます。入ってくるリンク数が 1 以上のノードは、まだ利用することができません。つまり、リンク数が 0 のノード
のどれか 1 つを選んで、選んだノードからのリンクは削除する、という処理を N 回繰り返せばOKです。N回繰り返す前に、リンク数が 0 のノードがなくなった場合は、条件を満たす順列は存在しないことになります。
さっくり実装するとこんな感じですね。
このコードでは、リスト candidates に、リンク数が 0 のノードを記録しておき、candidates.pop() で 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」をコピーする処理（最悪ケースで ）が何度も行われるので、間違いなく TLE します。これらのコピー処理の回数を減らす方策が必要です。
で、ここで利用できるのが、 という条件です。上記のコードは、すべての可能なパターンを網羅するロジックになっていますが、実際には、
種類だけ発見すればよいので、すべての「並行世界」をたどる必要はありません。キューの中に溜まっている検索中の「世界」は、「
発見済みの順列の本数」に絞ることができます。
さらに、len(candidates) == 1 の世界（つまり、次の１手ではブランチしない場合）、あるいは、必要な数のブランチ処理が終わって、十分な数の「世界」がキューに詰まってしまえば、上記の情報をコピーする必要はありません。キューから受け取った情報をそのまま使い回すことができます。
これらの制限を入れると無事に通ります。
ちなみに、この解法に気がつくポイントは、 という組み合わせにあります。先ほどのコピー処理は、
ですが、
という条件があるので、10 回程度の繰り返しは大丈夫そうだと気が付きます。この 10 回が、ちょうど、
に一致しています。なので、
種類の答えを見つけるために、
回のブランチならば大丈夫とわかります。
