CODE FESTIVAL 2017 Qual B
A - XXFESTIVAL
B - Problem Set
B: Problem Set - CODE FESTIVAL 2017 qual B | AtCoder
1 2 3 4 5 6 7 8 |
from collections import Counterinput()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 cntn, 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) // 2print(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回しか置換できない。順番が大事。
- '1010011011'みたいに2つ以上の'0'で隔てられたグループは、グループを隔てた'1'同士が'101'を形成することは無い
- なので、グループ単位で考えて後で合計すればOK
- 各グループは「11101011111101111」のように、1個以上の'1'と、1個の'0'が交互に並ぶことになる
- '10111'みたいに'101'に'1'がくっついた形は、1回置換で'01011'、2回目で'00101'、3回目で'00010'と、連鎖的に1の連続数分だけ置換を繰り返せる
- ただ、'1110111'のように両端に1がくっついていても、どちらか一方向にしか連鎖できない
- 要は、「10111…1」「111…101」という2パターンのカタマリを、連続する'1'の数が全体で最大になるように取り出せばよい
- 連続する1の数を、“カタマリの値”と呼ぶことにする
10111011101は、1011 101 1101とすれば値は2,1,2で合計5だが、10111 0 11101とすれば、3,3で6になり、後者が選ばれる
で、このグループ単位での最大値の求め方が分からなくて時間切れ。
動的計画法で解ける。
- たとえば「
111011011111101111」というグループを考える - 0で分割し、1の連続数の配列lsを得る。
ls = [3,2,6,4]
11…11011..11という、0を挟んで1が並んだ箇所ごとに、そこから取るカタマリを考える- 候補が4つある
- 左から最大限、右から1個だけ取り、「11…1101」というカタマリを作る。右の残りは次の箇所のために繰り越す
- 左から1個だけ、右から最大限取り、「1011…11」というカタマリを作る。左のあまりは捨てられ、繰り越しは無し
- 左から1個だけ、右から1だけ残して取り、「1011…1」というカタマリを作る。繰り越し数は1個
- 左を全て捨て、右を丸ごと次に繰り越す。カタマリは作られない
- 繰り越し数が、次の箇所での左の個数になる
- 繰り越し数によって、明らかに損になる候補、不可能な候補があるため、場合分けで微調整
- dpc[pc]= 「左からc番目の箇所に着目している時、繰り越しの長さがpcであるときの、これまで作ってきたカタマリの累計の最大値」
- pcの取る値は限られている（0, 1, ls[c]-1, ls[c]）が、上限は揺れ動くため、辞書型で持つ
- dp1={ls[0]:0} として、ls[1]から順番に更新
- dpk+1 は dpk のみから作成できるため、生成後は1つ前の状態は残しておく必要は無い（無駄な節約志向）
- 場合分け
- pc = 繰り越し数, cc = ls[c]とする
- 以下、[a]は、1がa個並んだ文字列を示す
- pc == 0のとき
- 1.～3.は不可能
- 4. 次へ → pc = cc, 新規カタマリなし
- pc > 0, cc == 1のとき
- 1. [pc]01を作る → pc = 0, 値pcのカタマリが出来る
- 4. [pc]を無視して次へ → pc = cc, 新規カタマリなし
- 3.は不可能、2.にするなら1.にした方が常に良い
- pc > 0, cc > 1のとき
- 1. [pc]01を作る → pc = cc-1, 値pcのカタマリが出来る
- 2. 10[cc]を作る → pc = 0, 値ccのカタマリが出来る
- 3. 10[cc-1]を作る → pc = 1, 値cc-1のカタマリが出来る
- 4. [pc]を無視して次へ → pc = cc, 新規カタマリなし
- この条件で、pcの値ごとに最大値を保持するようにDPを更新する
- c, pcが同じなら、カタマリ累計が大きい方が常に良い
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 redef update(d, k, v): if k not in d or d[k] < v: d[k] = vn = input()s = input().strip('0')ans = 0for 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) |
