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)