文書の過去の版を表示しています。


AtCoder Grand Contest 032 A,B,C 問題メモ

A - Limited Insertion

問題

  • 数列 b1,b2,...,bN がある
  • 空の配列 a に以下の操作を N 回繰り返して b と同じにできるか判定し、可能なら操作手順を示せ
    • i 番目の操作では、1ji なる j を1つ選び、aj 番目に整数 j を挿入する
  • 1N100

解法

  • i 番目より左に整数 i を挿入することは出来ない。
  • 各要素は、自分より前に挿入されると1つずつ右に動くことはあるが、左に動くことは無い。

以上の2つより、i 番目より左に整数 i が存在してると、つまり i<bi となる i が存在していると構築不可能。 それ以外の場合を考える。

最後に挿入した数字は、ai=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=bi となっている一番最後の i を特定し、ib から消す。 これを N 回繰り返し、最後にひっくり返せばそれが操作手順となる。

N100 なので、上記を毎回ループして間に合う。

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つ構築せよ
    • N 頂点で、頂点に 1...N まで番号が付いている
    • 「自身に隣接する全ての頂点の番号の和」は、全ての頂点で等しい
  • 2N100

解法

なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。

1  2  3
↕  ↕  ↕
6  5  4
N が偶数の場合

S=1+2+...+N とする。また、T=1+N とする。T はペアの和となる。

ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。

自身に対する辺のみが無いので、頂点 v に隣接する頂点の和は Sv となる。

ここで、ペアへの辺を1本だけ無くすと、ST となり、これは全ての頂点で同じとなる。

N が奇数の場合

T=N (頂点 N だけぼっち)となるので、上記と同様に構築すると、完全グラフの時点で頂点 NSv=ST となり、他の頂点と等しくなっている。

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

問題

  • 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 に戻ってくる辺があるかを調べればよい。

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

問題

  • 1,...,N の順列 p=(p1,...,pN)
  • 以下の操作を好きな順序で繰り返して、p を昇順にソートする
    • コスト A を支払い、任意の数 pi を取り出し、取り出した位置より右の任意の位置に挿入する
    • コスト B を支払い、任意の数 pi を取り出し、取り出した位置より左の任意の位置に挿入する
  • 必要な総コストの最小値を求めよ
  • 1N5000

解法

最小カットで解く方法は分かったけど、辺数が多くなりすぎるためTLE。

FIXME

programming_algorithm/contest_history/atcoder/2019/0323_agc032.1553363337.txt.gz · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0