AUPC 2018 day3 F: Binary String with Slit
問題
01からなる文字列が与えられる。
文字列に対して次の操作を好きなだけ行える。
文字列の一番右の'1'を含む連続する二文字の部分文字列を
- 11は10に
- 10は11か01に
- 01は10に
することができる。
文字列S, Tが与えられたとき、SをTに最低何回の操作で変えられるか。
制約
S, Tの長さは50以下で、それが10^5個以下与えられる。
S, Tは0,1からなり、ともに少なくとも一つの1を含む。
AUPC 2018 day3 E: Balanced Edge Deletion
問題
無向グラフが与えられる。ここから辺を一本取り除き、できた連結成分をA, Bとする。（A, Bの片方またはどちらも空かもしれない）
グラフGに対してsum(G) = Σ{w(e)|e∈Gの辺}とする。ただしw(e)は辺eの重みである。
abs(sum(A) - sum(B))を最小化するような取り除くべき辺を求めよ。
複数ある場合は辞書順最小のもの。
制約
グラフの頂点、辺はともに10万以下。
重みは10^9以下の正の整数。
AUPC 2018 day3 D: Shiritori Compression
問題
しりとりになっている英単語の列wiが与えられる。この列には次のような操作を好きなだけ行うことができる。
i＜jなるi, jについてwiとwjの先頭の文字が等しいとき、列からwi, wi+1, ..., wj-1を取り除く。
最小でいくつまで要素を減らせるか。
制約
単語の個数≦10^5
AUPC 2018 day3 C: Namo.. Cut
問題
無向木に一本だけ無向辺を足したグラフが与えられる。
次のQ個のクエリに答えよ。
aからbへのパスをなくすために最小で何本の辺を消せばいいか。
制約
グラフのサイズとクエリの数が両方10万以下。
AUPC 2018 day3 B: Pivots
問題
数列a0, ..., an-1が与えられる。要素は互いにことなる。
この数列に対してQ個のクエリを処理した後の数列を出力せよ。
クエリ： 値vが与えられる。ai = vとしたとき、
数列を ai+1, ..., an-1, ai, a0, ..., ai-1のように並び替える。
制約
n, q≦10^5
