差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2021/02/17] – ikatakos
@@ 行 1: / 行 1: @@
-======第6回 ドワンゴからの挑戦状 予選 B問題メモ======
+======第6回 ドワンゴからの挑戦状 予選 B,D問題メモ======
 [[https://atcoder.jp/contests/dwacon6th-prelims|Dwango Programming Contest 6th]]
@@ 行 146: / 行 146: @@
 </sxh>
+/*
+===== C - Cookie Distribution =====
+[[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_c|C - Cookie Distribution]]
+==== 問題 ====
+==== 例 ====
+==== 解法 ====
+++++ Python3 |
+<sxh python>
+</sxh>
+++++
+*/
+===== D - Arrangement =====
+[[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d|D - Arrangement]]
+==== 問題 ====
+  * $1～N$ の順列 $p_1,p_2,...,p_N$ であって、以下の条件を満たすもののうち辞書順最小のものを求めよ
+  * 条件
+    * $i$ の右側に $a_i$ が来てはいけない
+  * 存在しない場合は ''-1'' を答えよ
+  * $2 \le N \le 10^5$
+  * $i \neq a_i$
+==== 解法 ====
+まず、サンプルにあるが、$N=2$ の場合は $(a_1,a_2)=(2,1)$ の1通りしか無く、これは破綻する。以下、$N \ge 3$ とする。
+辞書順最小でよくある解法は、先頭から「この後が破綻しない限り、貪欲に現在置ける最小のものを置く」というもの。
+破綻するかどうかを手早く判定できることがポイントとなる。
+で、置ける条件、破綻する条件を探していく。これは実際にいろいろ試す。\\
+直前に置いた値を $p$、残っている最小の値を $q$、その次に小さい値を $r$ とする。
+  * $a_p \neq q$ の場合、ある1ケースを除いて、$q$ を置いてよい
+  * $a_p = q$ の場合、ある1ケースを除いて、$r$ を置いてよい
+そして、ある1ケースとは「残っている全ての数字に対して $a_i=x$ となっている」場合。\\
+これは、今 $x$ を置いておかないと今後置ける機会が無くなってしまうので、大小にかかわらず $x$ を置く。
+逆に、このようなケースが1度見つかったら、あとは「$x$ のすぐ右に置く数字は $a_x$ 以外」という他に制約は無くなるので、そこだけ注意して昇順に並べてよい。
+  N = 9
+  a : 2 3 5 5 4 5 5 5 5
+3 2                ・ここまで決めた後、5自身を除き全ての数字の ai = 5
+3 2 5              ・5を置いておかないと、置ける機会が無くなる
+3 2 5 6            ・次に小さい値は4だが、a5 = 4なので置けず、次善の6を置く
+3 2 5 6 4 7 8 9    ・あとは昇順でよい
+また、残りが2個になったら破綻する条件がもう1つ加わり、$q,r$ が $a_q=r, a_r=q$ のような状態で残ると破綻してしまう。\\
+しかし実際は残り3個の状態で $q$ または $r$ を前に持ってくることで、破綻を防げる。
+従って、以下のアルゴリズムで残り3個になるまで構築し、
+  * 各数が「右隣においてはいけない数」として指定されている個数を管理（確定した数字の分はその都度減らす）する
+  * 「置くべき残り個数 - 1（自身の分）」と「自身が右隣においてはいけない数として指定されている個数」が等しい数があれば、その数を置く
+    * 残りはほぼ昇順に並べられる
+  * そうで無ければ、直前に置いた値を $p$、残っている最小の値を $q$、その次に小さい値を $r$ として、
+    * $a_p \neq q$ の場合、$q$ を置く
+    * $a_p = q$ の場合、$r$ を置く
+残り3個になったら、総当たりしても高々6通りなので、破綻しない最小のものを探して後ろにくっつければよい。
+++++ Python3 |
+<sxh python>
+import sys
+from collections import Counter
+from heapq import heappop, heapreplace
+from itertools import permutations
+from operator import itemgetter
+def fill_remaining(ans, aaa, x, remaining):
+    """
+    xを先頭にして残りを昇順に追加
+    ただしxの次の要素のみ、aaa[x]で禁止されていた場合はその次と入れ替える
+    remainingにはxを含め3要素以上残っていることが前提
+    """
+    ans.append(x)
+    i = len(ans)
+    while remaining:
+        k = heappop(remainings)
+        if k != x:
+            ans.append(k)
+    if aaa[x] == ans[i]:
+        ans[i], ans[i + 1] = ans[i + 1], ans[i]
+def solve(n, aaa):
+    if n == 2:
+        return [-1]
+    in_degrees = Counter(aaa)
+    # 少なくとも残り個数がこれ+1になるまでは「ある条件」には当てはまらない
+    # ただし減少することはあるため、直前に再チェック必要
+    curr_max = max(in_degrees.values())
+    remainings = list(range(1, n + 1))
+    aaa.insert(0, 0)
+    ans = []
+    banned = -1
+    for i in range(n - 3):
+        if curr_max == n - i - 1:
+            curr_x, curr_max = max(in_degrees.items(), key=itemgetter(1))
+            if curr_max == n - i - 1:
+                fill_remaining(ans, aaa, curr_x, remainings)
+                return ans
+        top = heappop(remainings)
+        if top == banned:
+            ans.append(heapreplace(remainings, top))
+        else:
+            ans.append(top)
+        banned = aaa[ans[-1]]
+        # 確定した数字の入り次数を削減
+        if banned in in_degrees:
+            if in_degrees[banned] == 1:
+                del in_degrees[banned]
+            else:
+                in_degrees[banned] -= 1
+        in_degrees.pop(ans[-1], 0)
+    remainings.sort()
+    for i, j, k in permutations(remainings):
+        if i != banned and j != aaa[i] and k != aaa[j]:
+            ans += [i, j, k]
+            break
+    return ans
+n, *aaa = map(int, sys.stdin.buffer.read().split())
+print(*solve(n, aaa))
+</sxh>
+++++
+===== E - Span Covering =====
+[[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_e|E - Span Covering]]
+==== 問題 ====
+==== 例 ====
+==== 解法 ====
+++++ Python3 |
+<sxh python>
+</sxh>
+++++