−目次
文書の過去の版を表示しています。
AtCoder Grand Contest 032 A,B,C 問題メモ
A - Limited Insertion
問題
- 数列 がある
- 空の配列 に以下の操作を 回繰り返して と同じにできるか判定し、可能なら操作手順を示せ
- 番目の操作では、 なる を1つ選び、 の 番目に整数 を挿入する
解法
- 番目より左に整数 を挿入することは出来ない。
- 各要素は、自分より前に挿入されると1つずつ右に動くことはあるが、左に動くことは無い。
以上の2つより、 番目より左に整数 が存在してると、つまり となる が存在していると構築不可能。 それ以外の場合を考える。
最後に挿入した数字は、 となっているはずである。
そのような箇所が複数ある場合は、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
となっている一番最後の を特定し、 を から消す。 これを 回繰り返し、最後にひっくり返せばそれが操作手順となる。
なので、上記を毎回ループして間に合う。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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つ構築せよ
- 頂点で、頂点に まで番号が付いている
- 「自身に隣接する全ての頂点の番号の和」は、全ての頂点で等しい
解法
なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。
1 2 3 ↕ ↕ ↕ 6 5 4
が偶数の場合
とする。また、 とする。 はペアの和となる。
ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。
自身に対する辺のみが無いので、頂点 に隣接する頂点の和は となる。
ここで、ペアへの辺を1本だけ無くすと、 となり、これは全ての頂点で同じとなる。
が奇数の場合
(頂点 だけぼっち)となるので、上記と同様に構築すると、完全グラフの時点で頂点 は となり、他の頂点と等しくなっている。
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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
問題
- 頂点 辺の単純連結無向グラフが与えられる
- グラフを、3つの閉路に分割できるか判定せよ
- 閉路は、同じ頂点を2回以上通過してもよい
解法
以下で全網羅できるという証明はよく分かっていないが、実験して「何となく出来そう」で通った。
まず、閉路を作るには、入る辺と出る辺で必ずペアが必要。これは閉路が重なり合っても変わらないので、全ての頂点の次数は偶数である。奇数の頂点があればNo。
その上で、
- 次数が6以上の頂点が1つでも存在すると、Yes
- 次数が4の頂点が3つ以上存在すると、Yes
- 次数が4の頂点が1つ以下だと、No
次数が4の頂点が2つの場合、2パターンに分かれる。
,--, ,--, ,--, ( ○ ○ ) →OK `--' `--' `--' ,--, |,--,| ○ ○ →NG |`--'| `--'
次数4の2頂点を として、 から出発して を経由せず に戻ってくる辺があるかを調べればよい。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
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
問題
- の順列
- 以下の操作を好きな順序で繰り返して、 を昇順にソートする
- コスト を支払い、任意の数 を取り出し、取り出した位置より右の任意の位置に挿入する
- コスト を支払い、任意の数 を取り出し、取り出した位置より左の任意の位置に挿入する
- 必要な総コストの最小値を求めよ
解法
最小カットで解く方法は分かったけど、辺数が多くなりすぎるためTLE。