差分
このページの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:// | [[https:// | ||
行 146: | 行 146: | ||
</ | </ | ||
+ | /* | ||
+ | |||
+ | ===== C - Cookie Distribution ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | |||
+ | ==== 例 ==== | ||
+ | |||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | |||
+ | ++++ Python3 | | ||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | |||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | */ | ||
+ | |||
+ | ===== D - Arrangement ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * $1~N$ の順列 $p_1, | ||
+ | * 条件 | ||
+ | * $i=1~N$ について、$i$ の右側に $a_i$ が来てはいけない | ||
+ | * 存在しない場合は '' | ||
+ | * $2 \le N \le 10^5$ | ||
+ | * $i \neq a_i$ | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | まず、サンプルにあるが、$N=2$ の場合は $(a_1, | ||
+ | |||
+ | 辞書順最小でよくある解法は、先頭から「この後が破綻しない限り、貪欲に現在置ける最小のものを置く」というもの。 | ||
+ | |||
+ | 破綻するかどうかを手早く判定できることがポイントとなる。 | ||
+ | |||
+ | で、置ける条件、破綻する条件を探していく。これは実際にいろいろ試す。\\ | ||
+ | 直前に置いた値を $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 | ||
+ | | ||
+ | 1 3 2 ・ここまで決めた後、5自身を除き全ての数字の ai = 5 | ||
+ | 1 3 2 5 ・5を置いておかないと、置ける機会が無くなる | ||
+ | 1 3 2 5 6 ・次に小さい値は4だが、a5 = 4なので置けず、次善の6を置く | ||
+ | 1 3 2 5 6 4 7 8 9 ・あとは昇順でよい | ||
+ | |||
+ | また、残りが2個になったら破綻する条件がもう1つ加わり、$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, | ||
+ | """ | ||
+ | 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, | ||
+ | |||
+ | aaa.insert(0, | ||
+ | |||
+ | ans = [] | ||
+ | banned = -1 | ||
+ | for i in range(n - 3): | ||
+ | if curr_max == n - i - 1: | ||
+ | curr_x, curr_max = max(in_degrees.items(), | ||
+ | if curr_max == n - i - 1: | ||
+ | fill_remaining(ans, | ||
+ | return ans | ||
+ | top = heappop(remainings) | ||
+ | if top == banned: | ||
+ | ans.append(heapreplace(remainings, | ||
+ | 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], | ||
+ | |||
+ | 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, | ||
+ | |||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | ===== E - Span Covering ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 長さがそれぞれ $L_1, | ||
+ | * この区間を、左端座標が整数になるよう $[0,X)$ からはみ出さないように置いていく | ||
+ | * $[0,X)$ が全て少なくとも1つの区間に覆われるような置き方の個数を求めよ | ||
+ | * $1 \le N \le 100$ | ||
+ | * $1 \le L_i \le X \le 500$ | ||
+ | ==== 解法 ==== | ||
+ | |||
+ | |||
+ | ++++ Python3 | | ||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | |||
+ | </ | ||
+ | ++++ | ||