2018-09-29から1日間の記事一覧

AUPC 2018 day3: G Palindromic Subsequences

問題 英小文字からなる文字列が与えられる。 文字列の必ずしも連続しない部分文字列のうち、回文であるものは何種類あるか。 同じ回文は一つと数える。 制約 文字列の長さ2000以下。

AUPC 2018 day3 F: Binary String with Slit

問題 01からなる文字列が与えられる。 文字列に対して次の操作を好きなだけ行える。 文字列の一番右の'1'を含む連続する二文字の部分文字列を 11は10に 10は11か01に 01は10に することができる。 文字列S, Tが与えられたとき、SをTに最低何回の操作で変えら…

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))を最小化するよう…

AUPC 2018 day3 D: Shiritori Compression

問題 しりとりになっている英単語の列wiが与えられる。この列には次のような操作を好きなだけ行うことができる。 i<jなるi, jについてwiとwjの先頭の文字が等しいとき、列からwi, wi+1, ..., wj-1を取り除く。 最小でいくつまで要素を減らせるか。 制約 単…

AUPC 2018 day3 C: Namo.. Cut

問題 無向木に一本だけ無向辺を足したグラフが与えられる。 次のQ個のクエリに答えよ。 aからbへのパスをなくすために最小で何本の辺を消せばいいか。 制約 グラフのサイズとクエリの数が両方10万以下。

AUPC 2018 day3 B: Pivots

AOJ

問題 数列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

AOJ

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