B: Problem Set - CODE FESTIVAL 2017 qual B | AtCoder
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 - CODE FESTIVAL 2017 qual B | AtCoder
グラフ問題。あるノードと、リンクを3本渡った先のノードの間にリンクが無ければ追加、ということを繰り返して、追加できるリンクの最大本数を答える。
追加できなくなるまで繰り返すってことは、全ノードから2リンク以内に全ノードまで到達できるようになるわけで、完全グラフになるんじゃ無かろうか、と考えながらサンプルを見ると、1番目のサンプルでは本数が合わない。1-3-5、2-4-6の間が互いに結ばれていないので、二部グラフが関係しているっぽい。たしかに、二部グラフでは同じグループの頂点間に辺は無いし、奇数回の移動では同じグループの頂点にはたどり着けないので辺が追加されることも無い。
グラフが二部グラフなら完全二部グラフ、違うなら完全グラフが最終形になり、その辺数から、最初からある数を引けばよい。
二部グラフの判定は、どっかの適当な頂点に“0”をマークして、隣り合う頂点には“1”、さらに隣の頂点には“0”、と2色に塗っていく。最後まで矛盾しなければ二部グラフ。途中で矛盾する塗り方が発生したら二部グラフでない。
is_bipartite()は、二部グラフ判定。二部グラフなら一方のグループの頂点数を、二部グラフでないならFalseを返す。
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 - CODE FESTIVAL 2017 qual B | AtCoder
'0'と'1'からなる文字列がある。'101'を'010'に再帰的に置換していく。最大で何回できますか、という問題。
たとえば1010101は、両端の101を置換すれば2回できるが、真ん中を最初に置換してしまうと1001001となり、1回しか置換できない。順番が大事。
10111011101は、1011 101 1101とすれば値は2,1,2で合計5だが、10111 0 11101とすれば、3,3で6になり、後者が選ばれるで、このグループ単位での最大値の求め方が分からなくて時間切れ。
動的計画法で解ける。
111011011111101111」というグループを考えるls = [3,2,6,4]11…11011..11という、0を挟んで1が並んだ箇所ごとに、そこから取るカタマリを考える
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)