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文字以下

ARC 097 F Monochrome Cat

問題 N頂点からなり、各頂点が黒または白である木が与えられる。 好きな頂点から出発して、 今いる頂点の色を反転させる 隣接する頂点に移動して、移動先の色を反転させる の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の…

ARC 097

ボケ防止にまったり勢でプロコン復帰します。 C sの異なる連続する部分文字列のうち辞書順でK番目に小さいものを出力せよ。 最初から結構難しそう。制約がないと結構面倒な問題じゃなかったっけか。 substringを全部列挙してsetに入れる → O(N^3logN)とかに…

ICPC2017 Asia Regional Tsukuba K Counting Cycles

問題 n頂点m辺からなる連結な無向グラフが与えられる。そのグラフに含まれる単純閉路(同じ頂点を二度通らないような閉路)の個数を求めよ。 制約条件 n≦10万 m≦n+15

ICPC2017 Asia Regional Tsukuba J String Puzzle

問題 長さnの文字列がありその一部の情報が以下のどれかの形式で与えられる。 x文字目がcである l文字目からr文字目がh文字目からと等しい このときq個のクエリ、x文字目が何の文字であるか、あるいは与えられた情報からではわからないかを答えよ。 制約条件…

ICPC2017 Asia Regional Tsukuba I Starting a Scenic Railroad Service

Hは解説みて通しはしたけど解法の意味がわからない。 問題 n人の乗客がいてそれぞれ駅s[i]からt[i]まで電車に乗る。 全員が座るためには各人が席を指定できないとき、最小でいくつの座席が必要であるか、 また各人が自由に席を指定できるとき最小でいくつの…

ICPC2017 Asia Regional Tsukuba G Rendezvous on a Tetrahedron

問題 全ての辺の長さが1の正四面体ABCDの頂点Aから二つの点p, qが与えられた向きに与えられた長さだけ進む。 点は正四面体の辺を通過するとき、辺と進む向きの角度が変化しないように進む。 移動後に二つの点が同じ面の中にいるかを判定せよ。 制約条件 移動…

ICPC2017 Asia Regional Tsukuba F Pizza Delivery

問題 重み付きの有向グラフが与えられる。i番目の辺の向きを反転させたとき、1番から2番の頂点への最短路が 短くなる 変化しない 長くなる のいずれであるかをそれぞれ出力せよ。 制約条件 グラフの辺と頂点≦10万 辺の重みは正整数で10万以下

ICPC2017 Asia Regional Tsukuba E Black or White

Dむずくて通せてないですごめんなさい。 問題 n個のセルが黒または白で塗られている。 セルの初期状態およびゴールの状態が与えられる。 セルは一度の操作で連続する1〜k個を好きな色に塗ることができる。 最小で何回の操作で全てのセルをゴールの状態にでき…

ICPC2017 Asia Regional Tsukuba C Medical Checkup

問題 とても読みにくい問題文。 n人の人がt秒以内に機械(m1, m2, m3, ...)を使う。 同時に一人一個の機械しか使えず、一つの機械は同時に一人でしか使えない 各人はm1から順にとばさずに機械を使う必要がある 各機械は、1番目の人から順に使用する。i番目の…

ICPC2017 Asia Regional Tsukuba B Parallel Lines

問題 平面上にm個の点が与えられる。その中から相違なる2n点を選び、n本の線分を作る。(nは自由) n本の線分のうち、平行であるペアの個数を最大化したい。 そのようなペアの個数の最大値はいくつか。 制約条件 m≦16 座標は絶対値1000以下の整数

ICPC2017 Asia Regional Tsukuba A Secret of Chocolate Poles

問題 黒と白の円盤を積み上げてタワーを作る。タワーは以下の条件を満たす必要がある 一枚以上の円盤がある 円盤の厚さの合計はl以下 最も外側の円盤は黒 同じ色同士の円盤が隣り合ってはいけない 黒の円盤は厚さ1またはkのどちらかを選ぶことができて、白の…

ICPC2017 国内予選 H 等積変形

問題 面積の等しい三角形A, Bが与えられる。 三角形Aに対し等積変形(二頂点を固定し、残り一頂点を三角形の面積が変わらないように動かす操作)を繰り返し三角形Aを三角形Bに重ねたい。 必要な操作の最低回数(あるいは4回以内にはできない)を求めよ。

ICPC2017 国内予選 G 迷宮を一周

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622&lang=jp

ICPC2017 国内予選 F リボンたたみ

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1621&lang=jp

ICPC2017 国内予選 E 論理式圧縮機

問題 与えられた論理式と常に同じ出力を返すような論理式のうち長さが最小のものを求めよ。 論理式の変数は4つまで、長さは16まで。

ICPC2017 国内予選 D 弁当作り

問題 各成分が0, 1であらわされる行列Aが与えられる。 Aの行の部分集合A[i]で、任意の列jに対してΣi_s[i][j]が偶数になるものを考える。 このようなA[i]のうち最大のサイズはいくつか。 例)Aが 010 011 110 101 だったら、2, 3, 4行目を選ぶと全ての列の和…

ICPC2017 国内予選 C 池のある庭園

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1618&lang=jp

ICPC2017 国内予選 B ほとんど同じプログラム

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1617&lang=jp

ICPC2017 国内予選 A 太郎君の買物

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1616&lang=jp

TopCoder SRM 622 Div1 Hard

問題 aまたはbからなる文字列が与えられる。 このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。 文字列が同じときは一つと数える。 制約条件 文字列は乱数により生成される。 n≦10^5

Codeforces 480(#274 Div1) D. Parcels

問題 n個の箱があり、i番目の箱は 時刻in[i]に倉庫に入り、out[i]に倉庫から出る。 この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。 この荷物を倉庫に出し入れするとv[i]円もらえる。 倉庫には、同時に全体でSの重さの荷物しか入れら…

Codeforces 478(#273 Div2only) E. Wavy numbers

問題 wavy numberとは、数字を10進法で書いたときの数字をx1,x2,x3,...,xnとすると x1<x2>x3<x4…が成り立つまたは、x1>x2<x3>x4…が成り立つ数のことを言う。Nの倍数のwavy numberでK番目に小さいものを求めよ。 答えが存在しない場合や10^14より大きく…

Codeforces 484(#276 Div1) E. Sign on Fence

問題 長方形の板がN枚並んで出来ているフェンスがある。 i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。 このフェンスに看板を貼る候補がQ通りある。 各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方…