目次
文書の過去の版を表示しています。
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になるように、和が同じになるペアに着目するとうまくいきそう。
１ ２ ３ ↕ ↕ ↕ ６ ５ ４
$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。
