CODE FESTIVAL 2017 Qual B

A: XXFESTIVAL - CODE FESTIVAL 2017 qual B | AtCoder

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

print(input()[:-8])

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回しか置換できない。順番が大事。

• '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. 左から最大限、右から1個だけ取り、「11…1101」というカタマリを作る。右の残りは次の箇所のために繰り越す
    2. 左から1個だけ、右から最大限取り、「1011…11」というカタマリを作る。左のあまりは捨てられ、繰り越しは無し
    3. 左から1個だけ、右から1だけ残して取り、「1011…1」というカタマリを作る。繰り越し数は1個
    4. 左を全て捨て、右を丸ごと次に繰り越す。カタマリは作られない
  • 繰り越し数が、次の箇所での左の個数になる
  • 繰り越し数によって、明らかに損になる候補、不可能な候補があるため、場合分けで微調整
• ${\rm dp}_c[{\rm pc}] = $ 「左からc番目の箇所に着目している時、繰り越しの長さがpcであるときの、これまで作ってきたカタマリの累計の最大値」
  • pcの取る値は限られている（0, 1, ls[c]-1, ls[c]）が、上限は揺れ動くため、辞書型で持つ
  • ${\rm dp}_1 = \{ls[0]: 0\}$ として、ls[1]から順番に更新
  • ${\rm dp}_{k+1}$ は ${\rm dp}_k$ のみから作成できるため、生成後は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が同じなら、カタマリ累計が大きい方が常に良い

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)