AtCoder Regular Contest 211 (Div. 2) A,B,C,D問題メモ

AtCoder Regular Contest 211 (Div. 2)

A - Banned X 2

問題文

長さ $9$ の非負整数列 $A=(A_1,A_2,\dots,A_9)$ が与えられます。
あなたは、$A$ の要素を $1$ つ選び $1$ 加算する操作を $0$ 回以上好きな回数行うことができます。
以下の条件をすべて満たす正整数列 $S$ が存在するようにするために、最小で何回の操作が必要ですか。
- $S$ の要素はすべて $1$ 以上 $9$ 以下である。
- $1\leq i\leq 9$ なる整数 $i$ について、$S$ に $i$ がちょうど $A_i$ 個含まれる。（したがって、$S$ の長さは $\sum_{i=1}^{9}A_i$ である。）
- どの隣接する $2$ 要素の和も $10$ にならない。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\leq T\leq 10^3$
$0\leq A_i\leq 10^9$ $(1\leq i\leq 9)$
$2\leq \sum_{i=1}^{9}A_i$
入力はすべて整数

解法

ARCの1問目にありがちな、注意力勝負の問題。（2敗）

$S$ の構築条件を満たすために $A$ に求められる条件は意外と緩く、だいたいの $A$ でそのまま構築可能である。

隣り合ってはいけない（和が $10$）のは $(1,9),(2,8),(3,7),(4,6),(5,5)$ のペアに限られる。
$(5,5)$ だけ同じものとのペアで特殊なので、分けて考える。

$5$ が過半数ある場合

$T=\sum_{i=1}^{9}A_i-A_5$（$A_5$ 以外の $A_i$ の和）として、$A_5 \gt T+1$ の時は、$5$ がどうしても隣り合ってしまう。

この場合、挟み込む文字は $5$ 以外なら何でもいいが、$A_5-T-1$ だけ、追加の文字が必要となる。

それ以外のペアが隣り合う場合

$5$ の時とは違い、たとえば $(1,9)$ がいっぱいあっても、$111...1999...9$ のようにすると隣り合う箇所は1箇所で済む。 $1$ と $9$ の間に $1,9$ 以外の文字が1つでもあればよい。

2種類のペア、たとえば $(1,9)$ と $(2,8)$ がいっぱいあっても、 $111222888999$ のように互い違いに挟み込めば何とでもできる。

よって、$5$ 以外のの4ペアについては、ペアを $(p,q)$ とし、

$A_p$ が $1$ 以上、$A_q$ が $1$ 以上、かつそれ以外の $A_i$ が $0$

という場合に限り操作が $1$ 必要となる。

以上の2条件に当てはまらない場合、答えは $0$ となる。

Python3

def solve(aaa):
    aaa = [0] + aaa
    total = sum(aaa)
    for p, q in ((1, 9), (2, 8), (3, 7), (4, 6)):
        if aaa[p] == 0 or aaa[q] == 0:
            continue
        if aaa[p] + aaa[q] == total:
            return 1

    other5 = total - aaa[5]
    ans = max(0, aaa[5] - other5 - 1)
    return ans


t = int(input())
for _ in range(t):
    aaa = list(map(int, input().split()))
    ans = solve(aaa)
    print(ans)

B - Three Sequences

問題文

$X\leq Y\leq Z$ なる正整数の組 $(X,Y,Z)$ が与えられます。
非負整数列の組 $(S_1,S_2,S_3)$ であって、以下の条件をすべて満たすものを $1$ つ出力してください。
- $S_1,S_2,S_3$ の長さはそれぞれ $1$ 以上 $1000$ 以下
- $S_1$ の連続部分列であり、かつ $S_2$ の連続部分列であるもののうち、最長のものの長さが $X$
- $S_1$ の連続部分列であり、かつ $S_3$ の連続部分列であるもののうち、最長のものの長さが $Y$
- $S_2$ の連続部分列であり、かつ $S_3$ の連続部分列であるもののうち、最長のものの長さが $Z$
- 上 $4$ つの条件をすべて満たすもののうち、$\max(\max(S_1),\max(S_2),\max(S_3))$ が最小

本問題の制約下で、条件を満たす $(S_1,S_2,S_3)$ は必ず存在することが証明できます。そのようなものが複数ある場合、どれを出力してもかまいません。

制約

$1\leq X\leq Y\leq Z\leq 100$
入力はすべて整数

解法

制約を読み飛ばして、$X,Y,Z$ の大小関係が定まっていないと思い込み、$6$ 通りに対応した実装をして時間かけてしまった。。。

最大が $0$

文字数だけしか調整できるものがない。

仮に最も短いのを $S_1$ として、$X$ と $Y$ は必ず同じ長さ $|S_1|$ にならざるを得ない。

この時、$|S_2|=|S_3|=Z$ とすることで条件を満たせる。

つまり、$X = Y$ なら可能である。

最大が $1$

いろいろ試行錯誤すると、

S1  |00X00|111Y111|         |00X00| : 長さXの0
S2  |0000Z0000|
S3  |111Y111|0000Z0000|

このように必ず構築できる。最大を $2$ 以上にする必要は無いことが分かる。

Python3

def solve(x, y, z):
    def add_length(ans):
        for i in range(3):
            ans[i].insert(0, len(ans[i]))

    ans = [[], [], []]
    xyz = [(x, 0b011), (y, 0b101), (z, 0b110)]
    xyz.sort()
    p, a = xyz[0]
    q, b = xyz[1]
    r, c = xyz[2]
    if p == q:
        for i in range(3):
            if c & (1 << i):
                ans[i] = [r] + [0] * r
            else:
                ans[i] = [p] + [0] * p
        return ans

    i = (a & b).bit_length() - 1
    j = (b & c).bit_length() - 1
    k = (c & a).bit_length() - 1
    ans[i] = [p + q] + [0] * q + [1] * p
    ans[j] = [q + r] + [1] * r + [0] * q
    ans[k] = [r] + [1] * r
    return ans


x, y, z = list(map(int, input().split()))
ans = solve(x, y, z)
for row in ans:
    print(*row)

C - Forest

問題文

$N$ 個の区画が横 $1$ 列に並んだ森林があります。
文字列 $S$ の $i$ 文字目が # であるとき区画 $i$ には木が生えていて、. のとき生えていません。
あなたは、以下の操作を好きなだけ繰り返すことができます。
- 木が生えていない区画を $2$ つ選ぶ。
- 選んだ区画を左から区画 $i,j$ とすると、区画 $i$ と区画 $j$ の間にある木がすべてなくなり、$R_i+R_j$ の報酬を得る。
ただし、木が $1$ 本もなくならないような操作を行うことはできません。

最終的に獲得できる報酬の総和の最大値を達成するために、最初に行うことのできる操作の数を求めてください。ただし、$2$ つの操作は、どちらか一方のみで選んでいる区画が存在するとき、またそのときに限り区別します。

制約

$3\leq N\leq 2\times 10^5$
$S$ の長さは $N$ で、各文字は # または .
$1\leq R_i\leq 10^9$ $(1\leq i\leq N)$
操作を $1$ 回以上行うことができる
$N,R_i$ は整数

解法

「初手」の場合の数を求めるという、少し変わった問題。

#### のように # が連続した区間1つ分を、「森」と呼ぶことにする。
…. のように . が連続した区間1つ分を、「平地」と呼ぶことにする。

前準備として、左右端にある森は伐採できないのでトリミングして、両端を平地の状態とする。

最適な操作において、伐採する区間には必ず森が1つだけ存在するとしてよい。

i   j   k    (i,k) 間で森2つを一気に伐採する意味は無い。
..##..##..   たとえば(i,j)→(i,k)のように操作した方が、必ず報酬は高くなる。

$S$ をランレングス圧縮し、以下を求める。森の個数を $n$ 個とし、左から森 $1,2,...,n$、平地 $1,2,...,n+1$ とする。

各森における $R_i$ の最大値を $f_1,...,f_n$
各平地における $R_i$ の最大値を $p_1,...,p_{n+1}$
各平地で、$R_i$ が区間内の最大値をとる $i$ の個数を $c_1,...,c_{n+1}$

S  . . . # # . . . # # # . .
R  3 1 3 5 2 1 2 2 4 1 1 2 5

f       |-5-|     |--4--|
p |--3--|   |--2--|     |-5-|
c |--2--|   |--2--|     |-1-|

初手では、隣接する2つの平地 $(i,i+1)$ を選ぶことになる。
その結果、$i$ と $i+1$ はマージされ、$p_i ← \max(p_i,f_i,p_{i+1})$ に更新される。（後続の要素は1つずつ前に移動する）

なるべく大きい $p_i,f_i$ を多く使うのが良さそうではあるが、最適であることを証明するには？

1回につき森1つ分を伐採するので、操作は $n$ 回おこなわれ、報酬として加算される $R_i$ の個数はのべ $2n$ 個となる。

このうち、$p_1,...,p_{n+1}$ は少なくとも1回ずつ使われる。
各平地につき、左右いずれかの森が切り開かれる際に必ずその平地に対して操作する必要がある。

もし、残り $n-1$ 個を全て $M=\max(R)$ にできれば、それが文句なく最大である。
そしてそれは、以下のように実現できる。

$\max(f) = M$ の場合、 $M$ を含む森を初手で伐採して $M$ を使用可能にし、以降の $n-1$ 回の操作で $M$ を使い続ければ実現できる。

$\max(p) = M$ の場合、 $n$ 回の操作で $M$ を使い続ければ（最初に $p_1,...,p_{n+1}$ が1回ずつ使われるとした分を除いて）残り $n-1$ 個を全て $M$ にできる。

言い換えると、「$p_i,f_i,p_{i+1}$ がいずれも $M$ でない $i$ を選んで操作する」時のみ、最大を達成できなくなる。

したがって、$\max(p_i,f_i,p_{i+1})=M$ となるような $i$ につき、$c_i \times c_{i+1}$ を合計すれば、答えとなる。

Python3

from itertools import groupby


def solve(n, s, rrr):
    i = 0
    while s[i] == '#':
        i += 1
    j = n - 1
    while s[j] == '#':
        j -= 1
    s = s[i:j + 1]
    rrr = rrr[i:j + 1]
    n = j + 1 - i

    max_plane_value = []
    max_plane_count = []
    max_forest_value = []
    offset = 0
    for c, itr in groupby(s):
        l = len(list(itr))
        if c == '.':
            tmp_max = 0
            tmp_count = 0
            for i in range(offset, offset + l):
                r = rrr[i]
                if r > tmp_max:
                    tmp_max = r
                    tmp_count = 1
                elif r == tmp_max:
                    tmp_count += 1
            max_plane_value.append(tmp_max)
            max_plane_count.append(tmp_count)
        else:
            max_forest_value.append(max(rrr[offset:offset + l]))
        offset += l

    lp = len(max_plane_value)
    mp = max(max_plane_value)
    mf = max(max_forest_value)
    ans = 0
    checked = set()
    if mp >= mf:
        for i in range(lp):
            if max_plane_value[i] == mp:
                if i > 0 and (i - 1) not in checked:
                    ans += max_plane_count[i - 1] * max_plane_count[i]
                    checked.add(i - 1)
                if i < lp - 1 and i not in checked:
                    ans += max_plane_count[i] * max_plane_count[i + 1]
                    checked.add(i)

    if mf >= mp:
        for i in range(lp - 1):
            if max_forest_value[i] == mf:
                if i not in checked:
                    ans += max_plane_count[i] * max_plane_count[i + 1]
                    checked.add(i)

    return ans


n = int(input())
s = input()
rrr = list(map(int, input().split()))
ans = solve(n, s, rrr)
print(ans)

D - Michishirube

問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。
- $i$ 番目 $(1\leq i\leq M)$ の辺は頂点 $U_i$ と頂点 $V_i$ を結ぶ無向辺です。
すべての頂点に、以下のように道標を立てます。
- 頂点 $1$ 以外のすべての頂点に、隣接している頂点のうちどれか $1$ つを指す青色の道標を立てる。
- 頂点 $2$ 以外のすべての頂点に、隣接している頂点のうちどれか $1$ つを指す黄色の道標を立てる。
ただし、同じ頂点にある $2$ つの道標が同じ頂点を指してはいけません。

以下の条件を満たすように道標を立てることは可能か判定し、可能なら道標の立て方を $1$ つ出力してください。
- 頂点 $1$ 以外のどの頂点からも、青色の道標の指す頂点に動くことを有限回繰り返すことで頂点 $1$ に到達することができる。
- 頂点 $2$ 以外のどの頂点からも、黄色の道標の指す頂点に動くことを有限回繰り返すことで頂点 $2$ に到達することができる。

条件を満たす道標の立て方が複数ある場合、どれを出力してもかまいません。

制約

$2\leq N\leq 2\times 10^5$
$1\leq M\leq 3\times 10^5$
$1\leq U_i\lt V_i\leq N$ $(1\leq i\leq M)$
与えられるグラフは単純かつ連結
入力はすべて整数

解法

構築可能かの判定

問題は以下のように言い換えられる。

$N$ 頂点 $2M$ 辺の有向グラフがある
入力 $(U_i,V_i)$ に対し、$U_i→V_i,V_i→U_i$ の有向辺が両方ある。
このグラフから、頂点 $1,2$ をそれぞれ根とした $N$ 頂点の根付き有向木を抽出せよ。
- ただし、2つの木で同じ辺を使ってはいけない。

（※問題文のイメージとは逆だが、根付き有向木の辺は根から葉に向かうとする。DFSなどの探索ではその方が自然なので。答えを出力する上では、各頂点にとっての「親頂点」を出力すると、問題文の設定と合致する）

①の根付き有向木を適当に1つ取る。

○      ○      ○→○
↑      ↑      ↑
①→○→○→○→②
        ↓
        ○→○→○
             `→○

この木を、（元の無向グラフとしての）使用する辺はそのまま、②を根としたものに変えると以下のようになる。
①と②を結ぶパス（“本流”とする）にある辺だけは向きが変わりOKとなるが、その他の“傍流”の辺の向きは変わらず、このままでは①を根としたときと使用辺が被ってしまう。

○      ○      ○→○    ┐傍流
↑      ↑      ↑        ┘
①←○←○←○←②        ] 本流
        ↓                ┐
        ○→○→○        │傍流
             `→○        ┘

傍流については、別の辺を使う必要がある。この時、一番困るのは傍流の中でも「葉」頂点である。中間の頂点をいくら解決（②からたどれるように）しても、葉頂点を解決しない限り、葉への辺は①と②の根付き木で同じ方向となってしまう。逆に、全ての葉さえ②からたどれるようにできれば、後は傍流の辺の向きを逆にすれば（枝分かれがある場合は一部の辺が不要になるが）全ての頂点についてたどれるようにできる。

○      ○      ○←○←,
  ↖  ↗     ,----------'
①←○←○←○←②----,
         `----------, |
        ○←○←○←' |
                ○←--'

この葉についての考察から、以下のことが連想される。

傍流に含まれる各辺は、元の無向グラフ上で「橋」であってはいけない?

もし橋ならその辺は、①の根付き木でも②の根付き木でも必ず本流から遠ざかる向きで使わざるを得ない。

逆に橋でないなら、本流からその頂点へ必ず2通り以上のパスで辿り着けるため、構築可能である。

①↔○↔○↔○↔○↔○↔②
  橋↓      ↕      ↕ not 橋
○--○--○  ○↔○↔○
 `○--○'

よって、構築可不可の条件は「傍流に橋があるか」で判定できる。

本流上の辺は、橋であってもよい。（ある①②パス上で橋である辺は、どのような他の①②パスを取っても、必ず含まれる）

構築

本来構築可能なグラフでも、うまく①の根付き木を構築しないと不可能になってしまうことがある。

×
①→○→○→○→②    →: ①の根付き木に含まれる辺
    ↓      ↓        …: 含まれないが元のグラフにはある辺
    ○………○
OK
①→○→○→○→②    ①←○←○←○←②
    ↓      ：            ：      ↓
    ○──→○            ○←──○

適当に本流（①②パス）を1つ選んだとき、元の無向グラフ上で「本流上の頂点を経由することなく互いに行き来できる本流外の頂点集合」を1つのまとまりと考え、傍流の「連結成分」と呼ぶことにする。連結成分1つにつき、本流から分岐するための辺は複数ある（構築可能な前提なら、傍流に橋はないので）。この分岐する辺を全て①の根付き木の方で使ってしまうと、②の本流から分岐する辺が無くなってしまい、不可能となる（上例・上図）。

これは「一旦傍流に入ると、連結成分内の頂点全てをたどるまで、本流に戻らない」とすることで、傍流と本流の接続辺を1本に抑え、②の本流から傍流に入る辺を残すことができ、回避できる（上例・下図）。

ただし「傍流内の全ての頂点をたどる」のも、上手くしないと、②の根付き木において別の辺で傍流に入れはしても、その後全ての傍流内の頂点をたどれなくなってしまう可能性がある。
が、これは再帰構造となっているので、元の問題を回避できるようなアルゴリズムを見つければ、この問題も回避できる。（①から傍流に入った最初の頂点を①'、②から傍流に入った最小の頂点を②'と考えると、構造は同じ）

①→○→○→○→○→②
    ↓          ￤
   ①'→○→○→②'
        ↓  ↓        ←こうするとダメ
        ○…○

で、このような根付き木の構築方法だが、未探索頂点があったら残さず行き尽くす性質と言えば、「DFSの訪問順」で根付き木を構築すれば良さそうとわかる。

（①からの根付き木構築時にはどれが“本流”でどれが“傍流”になるかもまだ決まっていないが、どのような木にしろ） DFSで構築された適当な根付き木においては、「全ての傍流の連結成分について、本流から分岐するために使用している辺は1本のみ」であることが保証される。
条件を満たすグラフであれば、残りの辺を使って②の根付き木を構築できる。

判定問題（橋の有無）はおこなわなくても、実際にDFSで①の根付き木を構築してみて、使用した辺を除き、②の根付き木を構築できたらYes、できなければNoとしてよい。

Python3

def dfs(n, links, s):
    parents = [-1] * n
    parents[s] = -2
    progress = [0] * n
    path = [s]
    while path:
        u = path[-1]
        li = progress[u]
        if li == len(links[u]):
            path.pop()
            continue
        progress[u] += 1
        v = links[u][li]
        if parents[v] != -1:
            continue
        parents[v] = u
        path.append(v)
    return parents


def solve(n, m, edges):
    links = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].add(v)
        links[v].add(u)

    links2 = [list(lk) for lk in links]
    result1 = dfs(n, links2, 0)

    for v, u in enumerate(result1):
        if u == -2:
            continue
        links[u].remove(v)

    links3 = [list(lk) for lk in links]
    result2 = dfs(n, links3, 1)

    if any(p == -1 for p in result2):
        return None

    ans = [f'{result2[0] + 1}', f'{result1[1] + 1}']
    for i in range(2, n):
        ans.append(f'{result1[i] + 1} {result2[i] + 1}')
    return ans


n, m = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
if ans is None:
    print('No')
else:
    print('Yes')
    print('\n'.join(ans))

目次

AtCoder Regular Contest 211 (Div. 2) A,B,C,D問題メモ

A - Banned X 2

問題文

制約

解法

$5$ が過半数ある場合

それ以外のペアが隣り合う場合

B - Three Sequences

問題文

制約

解法

最大が $0$

最大が $1$

C - Forest

問題文

制約

解法

D - Michishirube

問題文

制約

解法

構築可能かの判定

構築