目次
文書の過去の版を表示しています。
AtCoder Grand Contest 032 A,B,C 問題メモ
A - Limited Insertion
問題
- 数列 $b_1,b_2,...,b_N$ がある
- 空の配列 $a$ に以下の操作を $N$ 回繰り返して $b$ と同じにできるか判定し、可能なら操作手順を示せ
- $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する
- $1 \le N \le 100$
解法
- $i$ 番目より左に整数 $i$ を挿入することは出来ない。
- 各要素は、自分より前に挿入されると1つずつ右に動くことはあるが、左に動くことは無い。
以上の2つより、$i$ 番目より左に整数 $i$ が存在してると、つまり $i \lt b_i$ となる $i$ が存在していると構築不可能。 それ以外の場合を考える。
最後に挿入した数字は、$a_i=i$ となっているはずである。
そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作しないと困ったことになる。
i 1 2 3 4 5 a 1 1 3 2 5 → 1,3,5 が i = ai となっている i=3を最後に操作したことにすると、1つ前の状態は i 1 2 3 4 a 1 1 2 5 ^ ここで i < ai となり構築不可能な形になる i=5を最後に操作したことにすると、構築可能な状態を保てる i 1 2 3 4 a 1 1 3 2
$i=b_i$ となっている一番最後の $i$ を特定し、$i$ を $b$ から消す。 これを $N$ 回繰り返し、最後にひっくり返せばそれが操作手順となる。
$N \le 100$ なので、上記を毎回ループして間に合う。
n = int(input()) bbb = list(map(int, input().split())) for i, b in enumerate(bbb, start=1): if i < b: print(-1) exit() ans = [] for _ in range(n): for i, b in reversed(list(enumerate(bbb, start=1))): if i == b: ans.append(i) bbb.pop(i - 1) break ans.reverse() print('\n'.join(map(str, ans)))
B - Balanced Neighbors
問題
- 単純で連結な無向グラフを考える
- 単純: 自己ループや多重辺を持たない
- 自己ループ: 自分から出て自分へ入る辺
- 多重辺: 同じ頂点同士を結ぶ複数の辺
- 連結: 分割されていない。どの2頂点間も、辺を通じて行き来できる
- 以下の条件を満たすグラフを1つ構築せよ
- $N$ 頂点で、頂点に $1 ... N$ まで番号が付いている
- 「自身に隣接する全ての頂点の番号の和」は、全ての頂点で等しい
- $2 \le N \le 100$
解法
なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。
1 2 3 ↕ ↕ ↕ 6 5 4
$N$ が偶数の場合
$S=1+2+...+N$ とする。また、$T=1+N$ とする。$T$ はペアの和となる。
ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。
自身に対する辺のみが無いので、頂点 $v$ に隣接する頂点の和は $S-v$ となる。
ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。
$N$ が奇数の場合
$T=N$ (頂点 $N$ だけぼっち)となるので、上記と同様に構築すると、完全グラフの時点で頂点 $N$ は $S-v=S-T$ となり、他の頂点と等しくなっている。
n = int(input()) ans = [] if n % 2 == 0: m = n + 1 else: m = n for i in range(1, n + 1): for j in range(i + 1, n + 1): if i + j == m: continue ans.append('{} {}'.format(i, j)) print(len(ans)) print('\n'.join(ans))
C - Three Circuits
問題
- $N$ 頂点 $M$ 辺の単純連結無向グラフが与えられる
- グラフを、3つの閉路に分割できるか判定せよ
- 閉路は、同じ頂点を2回以上通過してもよい
解法
以下で全網羅できるという証明はよく分かっていないが、実験して「何となく出来そう」で通った。
まず、閉路を作るには、入る辺と出る辺で必ずペアが必要。これは閉路が重なり合っても変わらないので、全ての頂点の次数は偶数である。奇数の頂点があればNo。
その上で、
- 次数が6以上の頂点が1つでも存在すると、Yes
- 次数が4の頂点が3つ以上存在すると、Yes
- 次数が4の頂点が1つ以下だと、No
次数が4の頂点が2つの場合、2パターンに分かれる。
,--, ,--, ,--, ( ○ ○ ) →OK `--' `--' `--' ,--, |,--,| ○ ○ →NG |`--'| `--'
次数4の2頂点を $S,T$ として、$S$ から出発して $T$ を経由せず $S$ に戻ってくる辺があるかを調べればよい。
import sys def solve(n, m, links): v4 = set() v6 = 0 for v, link in enumerate(links): l = len(link) if l % 2 == 1: return False if l == 4: v4.add(v) elif l >= 6: v6 += 1 if v6 > 0: return True if len(v4) > 2: return True if len(v4) < 2: return False s = v4.pop() t = v4.pop() for c in links[s]: visited = {s, t} q = [c] while q: v = q.pop() if v in visited: continue visited.add(v) for u in links[v]: if v != c and u == s: return True if u not in visited: q.append(u) return False n, m = map(int, input().split()) links = [set() for _ in [0] * n] for line in sys.stdin: a, b = map(int, line.split()) a -= 1 b -= 1 links[a].add(b) links[b].add(a) print('Yes' if solve(n, m, links) else 'No')
D - Rotation Sort
問題
- ${1,...,N}$ の順列 $p=(p1,...,pN)$
- 以下の操作を好きな順序で繰り返して、$p$ を昇順にソートする
- コスト $A$ を支払い、任意の数 $p_i$ を取り出し、取り出した位置より右の任意の位置に挿入する
- コスト $B$ を支払い、任意の数 $p_i$ を取り出し、取り出した位置より左の任意の位置に挿入する
- 必要な総コストの最小値を求めよ
- $1 \le N \le 5000$
解法
最小カットで解く方法は分かったけど、辺数が多くなりすぎるためTLE。