Loading [MathJax]/jax/output/CommonHTML/jax.js

−目次

CODE FESTIVAL 2017 Qual B

A - XXFESTIVAL

A: XXFESTIVAL - CODE FESTIVAL 2017 qual B | AtCoder

今までコンテストで提出した中で一番短いかも知れない

1
print(input()[:-8])

B - Problem Set

B: Problem Set - CODE FESTIVAL 2017 qual B | AtCoder

1
2
3
4
5
6
7
8
from collections import Counter
 
input()
d = Counter(map(int, input().split()))
input()
t = Counter(map(int, input().split()))
 
print('YES' if all(ti in d and d[ti] >= tc for ti, tc in t.items()) else 'NO')

C - 3 Steps

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

グラフ問題。あるノードと、リンクを3本渡った先のノードの間にリンクが無ければ追加、ということを繰り返して、追加できるリンクの最大本数を答える。

追加できなくなるまで繰り返すってことは、全ノードから2リンク以内に全ノードまで到達できるようになるわけで、完全グラフになるんじゃ無かろうか、と考えながらサンプルを見ると、1番目のサンプルでは本数が合わない。1-3-5、2-4-6の間が互いに結ばれていないので、二部グラフが関係しているっぽい。たしかに、二部グラフでは同じグループの頂点間に辺は無いし、奇数回の移動では同じグループの頂点にはたどり着けないので辺が追加されることも無い。

グラフが二部グラフなら完全二部グラフ、違うなら完全グラフが最終形になり、その辺数から、最初からある数を引けばよい。

二部グラフの判定は、どっかの適当な頂点に“0”をマークして、隣り合う頂点には“1”、さらに隣の頂点には“0”、と2色に塗っていく。最後まで矛盾しなければ二部グラフ。途中で矛盾する塗り方が発生したら二部グラフでない。

is_bipartite()は、二部グラフ判定。二部グラフなら一方のグループの頂点数を、二部グラフでないならFalseを返す。

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
def is_bipartite(links):
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]
    visited = set()
    cnt = 0
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c:
                return False
            continue
        visited.add(v)
        colors[v] = c
        cnt += c
        for u in links[v]:
            q.append((u, c ^ 1))
    return cnt
 
 
n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
 
bp1 = is_bipartite(links)
if bp1:
    max_m = bp1 * (n - bp1)
else:
    max_m = n * (n - 1) // 2
print(max_m - m)

D - 101 to 010

D: 101 to 010 - CODE FESTIVAL 2017 qual B | AtCoder

'0'と'1'からなる文字列がある。'101'を'010'に再帰的に置換していく。最大で何回できますか、という問題。

たとえば1010101は、両端の101を置換すれば2回できるが、真ん中を最初に置換してしまうと1001001となり、1回しか置換できない。順番が大事。

で、このグループ単位での最大値の求め方が分からなくて時間切れ。

動的計画法で解ける。

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
import re
 
 
def update(d, k, v):
    if k not in d or d[k] < v:
        d[k] = v
 
 
n = input()
s = input().strip('0')
ans = 0
 
for ps in re.split('0{2,}', s):
    fs = ps.split('0')
    if len(fs) == 1:
        continue
    ls = list(map(len, fs))
    pl = {ls[0]: 0}
    for cc in ls[1:]:
        nl = {}
        for pc, a in pl.items():
            update(nl, cc, a)
            if pc == 0:
                continue
            if cc == 1:
                update(nl, 0, a + pc)
            else:
                update(nl, cc - 1, a + pc)
                update(nl, 0, a + cc)
                update(nl, 1, a + cc - 1)
        pl = nl
    ans += max(pl.values())
 
print(ans)