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

続きを読む

AUPC 2018 day3 A: Internet Protocol Address

問題

数字からなる文字列が与えられる。適当にピリオドを打ってvalidなIPアドレスにできるか。
IPアドレスは4つの0〜255の数の列。leading zeroはだめ。

制約

与えられる文字列は4文字以上12文字以下

続きを読む