JAG Contest 2016 Domestic

A - 阿吽の呼吸

Time Limit: 10 sec / Memory Limit: 512 MB

Problem Statement

時は進んで 2060 年，共に 70 歳を迎える前田さんと後藤さんは長い付き合いの友人であり，大学時代にACM-ICPCで共に戦った仲間でもある．

二人は今でもよく一緒にお茶を飲みつつ，競技プログラミングの話で盛り上がっている．

二人で一緒にお茶を飲む時，前田さんが 1 回Aと言うと，その発言の後に後藤さんがちょうど 1 回Unと返事をする習慣がいつのまにか出来た．

しかし最近後藤さんは物忘れや勘違いをすることが多く，前田さんがAと言っても，後藤さんはたまにUnの返事を忘れたり，余計に返事をしたりする．

ついこの間も前田さんと後藤さんはお茶を飲みながら，二人のお気に入りのデータ構造について話し込んでいたようだ．

この時の会話の中から，Aで表される前田さんの発言と，Unで表される後藤さんの返事のみからなる記録が時系列で与えられたとき，後藤さんが習慣通りに反応したとみなすことが出来るかチェックしてほしい．

注意点として，前田さんの発言に対し，後藤さんの返事が多少遅れても，後藤さんは習慣通りに反応したとみなせる場合がある，ということが挙げられる．例えば，前田さんが2回連続してAと言った後，後藤さんが 2 回連続してUnと返事をして会話が終了した場合は，後藤さんが習慣通りの返事をしたとみなされる (Sample Input 2 参照)．

また，会話が終了した時点で，前田さんがAと言った回数と，後藤さんがUnと返事した回数が一致しても，後藤さんが習慣通りに返事をしたとはみなされない場合もあるので注意すること．例えば，前田さんが1回Aと言った後，後藤さんが 2 回連続してUnと返事し，その後で前田さんが 1 回Aと言って会話が終了した場合は，後藤さんが習慣通りの返事をしたとはみなされない (Sample Input 3 参照)．

Input

入力は以下の形式で与えられる．

$N$
$S_1$
$S_2$
$…$
$S_N$

最初の行はひとつの整数からなる． $N$ は，記録に含まれる前田さんがAと発言した回数と後藤さんがUnと返事した回数の合計を表し，$1 \leq N \leq 100$ を満たす．その後 $N$ 行に，文字列 $S_i$ が続き，各 $S_i (1 \leq i \leq N)$ はAかUnのどちらかに一致する．ここでAは前田さんの発言，Unは後藤さんの返事を表す． $i$ の小さい順に $S_i$ が記録されたものとする．前田さんと後藤さんが同時に発言することは無かったとする．

Output

後藤さんが習慣通りに反応したとみなすことが出来ればYES，出来なければNOを1行で出力すること．

Sample Input 1

4
A
Un
A
Un

Output for the Sample Input 1

YES

Sample Input 2

4
A
A
Un
Un

Output for the Sample Input 2

YES

Sample Input 3

4
A
Un
Un
A

Output for the Sample Input 3

NO

Sample Input 4

1
Un

Output for the Sample Input 4

NO

B - 豪邸と宅配便

Time Limit: 10 sec / Memory Limit: 512 MB

Problem Statement

太郎君は豪邸で一人暮らしをしている．勉強好きの太郎君は，今日も邸内の書斎で勉強をするつもりである．太郎君は，書斎以外の場所では集中できないので，勉強は必ず書斎で行う．

ところがこの日，太郎君宛の宅配便が $N$ 件届く．$i$ ($1 \leq i \leq N$) 番目の宅配便の届く時刻は $a_i$ である．配達員を玄関先で待たせるのは心苦しいので，太郎君は宅配便の届く時刻には玄関にいることにした．豪邸は広いので，書斎と玄関間の移動には片道 $M$ の時間がかかる．

一方で，太郎君はできるだけ長い時間勉強したいと思っている．時刻 $0$ から時刻 $T$ までで，太郎君が書斎で勉強できる時間の最大値を求めよ．

なお，太郎君は時刻 $0$ には書斎にいて，時刻 $M$ より早く宅配便が届くことはなく，時刻 $T$ より遅く宅配便が届くこともない．また，太郎君が宅配便を受け取るのにかかる時間は無視できる．

Input

各データセットは 2 行からなる． 1 行目は空白で区切られた 3 つの整数 $N, M, T$ からなる．これらの整数は，$1 \leq N \leq 100$, $1 \leq M \leq 10{,}000$, $1 \leq T \leq 10{,}000$ を満たす． 2 行目は空白で区切られた $N$ 個の整数 $a_1, a_2, \dots, a_N$ からなる．各 $a_i$ は $M \leq a_i \leq T$ を満たし，また $a_i < a_{ i + 1 }$ ($1 \leq i < N$) である．

Output

太郎君が勉強できる時間の最大値を表す整数を 1 行に出力せよ．

Sample Input 1

1 1 5
3

Output for the Sample Input 1

Sample Input 2

2 1 10
2 7

Output for the Sample Input 2

Sample Input 3

2 4 10
6 8

Output for the Sample Input 3

C - みさわさんの根付き木

Time Limit: 10 sec / Memory Limit: 512 MB

Problem Statement

あなたは親友であるみさわさんの誕生日が近いことに気づき，根付きの二分木をプレゼントすることにした．ここで，根付きの二分木とは，以下のようなグラフ構造である．(図 1)

各頂点には，その頂点の親と呼ばれる頂点がちょうど 1 つだけ存在し，親と辺で結ばれている．ただし，根と呼ばれる 1 つの頂点のみ，例外的に親を持たない．
各頂点は，左の子と呼ばれる頂点をちょうど1つ持つか，あるいは持たない．左の子を持つ場合，左の子とは辺で結ばれており，左の子の親はその頂点である．
各頂点は，右の子と呼ばれる頂点をちょうど1つ持つか，あるいは持たない．右の子を持つ場合，右の子とは辺で結ばれており，右の子の親はその頂点である．

図 1. 2 つの根付きの二分木とその合成の例

あなたは手作りの品を贈りたいと考えたので，市販の根付きの二分木を 2 つ買ってきて重ね合わせて合成することで，さらによい根付きの二分木を 1 つ作ることにした．あなたが買ってきた 2 つの木の各頂点には非負の整数が書かれている．みさわさんは少ない頂点数で各数値が大きいような，コストパフォーマンスがよい木が好みなので，以下の手順に沿って新しい二分木を作ることにする．

2 つの二分木それぞれの根に書かれた整数の和を，新しい二分木の根に書く整数とする．
どちらの二分木の根も左の子を持っている場合，それらを根とする二分木それぞれを合成した二分木を作り，新しい二分木の根の左の子とする．そうでない場合，新しい二分木の根は左の子を持たない．
どちらの二分木の根も右の子を持っている場合，それらを根とする二分木それぞれを合成した二分木を作り，新しい二分木の根の右の子とする．そうでない場合，新しい二分木の根は右の子を持たない．

あなたは実際に合成する作業を行う前に，できあがる根付きの二分木がどのようになるのか確かめることにした．買ってきた 2 つの根付きの二分木の情報が与えられるので，上記の手順に従って合成される新しい根付きの二分木を求めるプログラムを作成せよ．

ここで，根付きの二分木の情報は以下のような形式で文字列として表現するものとする．

(左の子を表す文字列)[根に書かれた整数](右の子を表す文字列)

節点が存在しない木は空文字列とする．例えば図 1 の合成されてできた新しい根付きの二分木は (()[6]())[8](((()[4]())[7]())[9]()) のように書く．

Input

入力は次の形式で表される．

$A$
$B$

$A$，$B$ はそれぞれ買ってきた根付きの二分木の情報を表す文字列であり，長さは $7$ 以上 $1000$ 以下である．与えられる情報は前述の形式に従っており，余計な空白文字等を含まない．また，節点が存在しない根付き木が入力されることはない．各節点に書かれた整数は $0$ 以上 $1000$ 以下であると仮定してよい．ただし，出力の各節点に書かれる整数はこの範囲に収まらない場合もあることに注意せよ．

Output

2 つの根付きの二分木を合成してできあがる新しい根付きの二分木の情報を 1 行で出力せよ．特に，行末の改行を除く余計な空白文字等を含まないよう注意せよ．

Sample Input 1

((()[8]())[2]())[5](((()[2]())[6](()[3]()))[1]())
(()[4]())[3](((()[2]())[1]())[8](()[3]()))

Output for the Sample Input 1

(()[6]())[8](((()[4]())[7]())[9]())

Sample Input 2

(()[1]())[2](()[3]())
(()[1](()[2]()))[3]()

Output for the Sample Input 2

(()[2]())[5]()

Sample Input 3

(()[1]())[111]()
()[999](()[9]())

Output for the Sample Input 3

()[1110]()

Sample Input 4

(()[2](()[4]()))[8]((()[16]())[32](()[64]()))
((()[1]())[3]())[9](()[27](()[81]()))

Output for the Sample Input 4

(()[5]())[17](()[59](()[145]()))

Sample Input 5

()[0]()
()[1000]()

Output for the Sample Input 5

()[1000]()

D - インビジブル

Time Limit: 10 sec / Memory Limit: 512 MB

Problem Statement

あなたは友達と"インビジブル"というカードゲームを遊ぼうとしている．このカードゲームでは，"得点カード"と"妨害カード"という2種類のカードを使う．それぞれの得点カードには，正の値が書かれている．このカードゲームのルールは次の通りである．

ゲームはプレイヤー1とプレイヤー2の2人のプレイヤーで行われる．ゲームはプレイヤー1のターンから始まる．
場には，1つのスタックと2つのデッキがある．スタックは，2人のプレイヤーが置いたカードからなる．また，それぞれのプレイヤーが持つデッキはそのプレイヤーが持つ得点カードと妨害カードからなる．プレイヤーは自分，もしくは相手デッキのカードの順番をいつでも確認できる．ゲームの開始時点ではスタックには1枚もカードはない．
2人のプレイヤーは交互に次の2つの行動のどちらかをちょうど1回行う．
- 自分のデッキの一番上のカードをスタックの一番上に置く．ただし，この行動は自分のデッキにカードが1枚も存在しない時には行うことができない．
- 自分のターンをパスする．
プレイヤーがターンをパスした時，次の処理を行う．
- 各プレイヤーは次の2つの条件を満たすスタック中のすべての得点カードを得る．得た得点カードは場から取り除かれる．
  1. 自分がスタックにおいた得点カードである．
  2. 相手が置いたどの妨害カードよりも上にある (スタック中に相手の妨害カードが存在しないとき，プレイヤーは自分がスタックに置いたすべてのカードを得る)．
- スタックのカードをすべて取り除く．

もしスタックにカードがない状態で両プレイヤーが連続してパスした場合，ゲームを終了する．各プレイヤーの最終的なスコアは，各プレイヤーが得た得点カードに書かれた数の総和である．

各プレイヤーは，自分のスコアから相手のスコアを引いた値を最大化するために最適な行動をとる．あなたの仕事は，与えられた各プレイヤーのデッキに対し，各プレイヤーが最適に行動したときのプレイヤー1のスコアとプレイヤー2のスコアの差を計算することである．

Input

入力は次のような形式の単一テストケースからなる．

$n$ $m$
$a_1$ $a_2$ $\dots$ $a_n$
$b_1$ $b_2$ $\dots$ $b_m$

1行目は山札の枚数を表す正の整数 $n$, $m$ ($1 \le n, m \le 50$) からなる． 2行目は $n$ 個の整数からなり，$a_i$ はプレイヤー1のデッキの上から $i$ 番目のカードを表す ($1 \le i \le n$)．$a_i$ は $1$ 以上，$1{,}000{,}000$ 以下，または $-1$ である． 3行目は $m$ 個の整数からなり，$b_j$ はプレイヤー2のデッキの上から $j$ 番目のカードを表す ($1 \le j \le m$)．$b_j$ は $1$ 以上，$1{,}000{,}000$ 以下，または $-1$ である． $a_i$, $b_j$ が正の整数の時は得点カードを表し，$-1$ の時は妨害カードを表す．

Output

お互いのプレイヤーが最適に行動した時の (プレイヤー1のスコア) - (プレイヤー2のスコア) を出力せよ．

Sample Input 1

2 2
100 -1
200 300

Output for the Sample Input 1

-100

Sample Input 2

3 5
10 30 -1
-1 90 20 10 -1

Output for the Sample Input 2

Sample Input 3

4 5
15 20 10 30
50 30 10 20 25

Output for the Sample Input 3

-60

E - 選挙活動

Time Limit: 10 sec / Memory Limit: 512 MB

Problem Statement

あなたは次回の選挙の候補者であるX氏の支援者である． X氏は駅前での街頭演説を予定しており，できるだけ多くの有権者に見てもらえる場所で演説しようと考えている．

駅前は $N$ 個の障害物と $M$ 人の有権者が存在している二次元平面として与えられる．各障害物は多角形であらわされ，その多角形の内側の領域が障害物となる．多角形の辺上は障害物に含まれない．また，有権者は平面上の点としてあらわされる．ある有権者の位置とX氏の位置を結ぶ線分上に障害物が存在しないとき，その有権者はX氏を見ることができる．

あなたの仕事は，駅前の障害物と有権者の情報をもとに，もっとも多くの有権者に見てもらえる地点を探すことだ．最大で何人の有権者から見えるように演説することができるかを求めよ．

Input

入力は以下のフォーマットで与えられる．

$N$ $M$
$polygon_1$
$polygon_2$
$...$
$polygon_N$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_M$ $y_M$

データセットの最初の行は空白文字1つで区切られた2個の整数 $N$, $M$ からなる． $N$ $(1 \le N \le 5)$ は駅前にある障害物の個数であり，$M$ $(1 \le M \le 10)$ は駅前にいる有権者の数である．続く行から $N$ 個の障害物の情報が与えられる．1つの障害物を表す入力は以下の形式で与えられる．

$L$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_L$ $y_L$

各障害物情報の最初の行はその障害物をあらわす多角形に含まれる頂点の数 $L$ である．その後の $L$ 行には多角形の頂点の座標を表す整数の組が反時計回りに記されている．なお，障害物を構成する頂点数の合計は $15$ 個以下となる．

$N$ 個の障害物の情報の後に続く $M$ 行には有権者のいる座標を表す整数の組が与えられる．

また，各テストケースは以下の条件を満たす：

$ 0 \le |x_i|, |y_i| \le 20 $
多角形の頂点または有権者のいる場所の座標はすべて互いに異なる．
多角形の頂点または有権者のいる場所の座標のうち3点が同一直線状に存在することはない．
2つの異なる多角形同士は交差を持たない．
各多角形は自己交差を持たない．
多角形の内部に有権者が存在することはない．

Output

最大で何人の有権者が演説を見られるようになるかを1行に出力せよ．

Sample Input 1

Output for the Sample Input 1

Sample Input 2

Output for the Sample Input 2

Sample Input 3

Output for the Sample Input 3

Sample Input 4

Output for the Sample Input 4

Sample Input 5

Output for the Sample Input 5

Sample Input 6

Output for the Sample Input 6

各入力例の障害物および有権者の配置は，それぞれ以下の図のようになっている．

F - 土地相続

Time Limit: 10 sec / Memory Limit: 512 MB

Problem Statement

ある $N$ 人の兄弟は親の遺産相続の話し合いをしていた．彼らの親の残した莫大な遺産の中には広大な土地も含まれていた．その土地は南北に $H$ km, 東西に $W$ km に広がる長方形の形をしている．この土地は 1 km 四方の区画単位で管理されており，土地の北端から $i$ 〜 $i+1$ km かつ西端から $j$ 〜 $j+1$ km の範囲にある 1 km 四方の区画を区画 $(i, j)$ と呼ぶ．（$i$, $j$ は $0 \leq i < H$, $0 \leq j < W$ を満たす整数である．）土地の価格は区画ごとに決まっており，区画 $(i, j)$ の価格は $a_{i, j}$ で表される．

兄弟は次のように土地を分けて相続することにした．

$N$ 人の兄弟それぞれが区画をいくつか選び相続する．
各兄弟が相続する土地が 1 つの長方形を成すように区画を選ばなければならない．
$N$ 人の兄弟が相続する土地は重なってはならない．
誰も相続しない区画があってもよい．誰も相続しない区画は放棄される．

ある人が相続する土地の範囲に含まれる区画の価格の和をその土地の価格と呼ぶ．兄弟は，各々が相続する土地の価格がなるべく公平になるように土地を分けたい．あなたの仕事は， $N$ 人の中で相続する土地の価格が最も低い人の土地の価格を最大にするような土地の分け方を考えることである．そのように土地を分けた時の，相続する土地の価格が最も低い人の土地の価格を答えるプログラムを作成せよ．

Input

入力は以下のような形式で与えられる．

$H$ $W$ $N$
$a_{0,0}$ $a_{0,1}$ ... $a_{0,W-1}$
...
$a_{H-1,0}$ $a_{H-1,1}$ ... $a_{H-1,W-1}$

$H$, $W$ $(2 \leq H,W \leq 200)$ は遺産の土地の南北の長さと東西の長さをそれぞれ表す． $N$ $(2 \leq N \leq 4)$ は土地を相続する兄弟の人数を表す． $a_{i, j}$ $(0 \leq a_{i,j} \leq 10^4)$ は区画 $(i, j)$ の価格を表す．

Output

相続する土地の価格が最も低い人の土地の価格を最大にするように分けた時の，最も低い土地の価格を 1 行で出力せよ．

Sample Input 1

Output for the Sample Input 1

図のように分けるのが最適である．

Sample Input 2

Output for the Sample Input 2

Sample Input 3

2 5 3
8 3 0 5 6
2 5 2 5 2

Output for the Sample Input 3

Sample Input 4

Output for the Sample Input 4

Sample Input 5

Output for the Sample Input 5

G - リングと紐

Time Limit: 10 sec / Memory Limit: 1024 MB

Problem Statement

芸術家のみさわさんは新しい作品を作ろうとしている．新しい作品の材料として，みさわさんは金属の輪と白黒2色の紐を大量に用意した．みさわさんは，異なる 2 つの輪をいずれかの色の紐で結ぶことを繰り返すことによって作品を作ることが出来る． 1 つの輪を複数の輪と繋ぐことも可能であるが，それぞれの輪のペアを結ぶ紐は高々 1 本である．みさわさんは，せっかく作品を作るからにはよい作品を作りたいと考えた．みさわさんの考える「よい作品」とは，以下のように定義されるものである．

1 つの輪は 1 つのよい作品である．
2 つのよい作品を用意したとき，それらに含まれている紐で繋がれていない輪のペア全てを白い紐で繋いだものは， 1 つのよい作品である．(図1. 操作1)
よい作品の白い紐を黒い紐に，黒い紐を白い紐にすべて入れ替えたものはよい作品である．(図1. 操作2)
以上で定義されたもののみがよい作品である．

図 1 はよい作品の一例である．

図 1. よい作品の例

以上の条件を満たすような渾身の「よい作品」を作り上げたみさわさんは，この作品に含まれる 0 個以上の輪を選び，それらを天井から吊るして展示することにした．このとき，なるべく黒い紐が映えるように展示したい．すなわち，天井から吊るされている輪とそれ以外の輪の間を繋ぐ黒い紐の本数が最大になるようにしたい．

そのように展示した時の，天井から吊るされている輪とそれ以外の輪の間を繋ぐ黒い紐の本数を求めよ．

Input

入力は以下の形式で与えられる．

$N$ $M$
$u_1$ $v_1$
...
$u_M$ $v_M$

$N$ $(1 \leq N \leq 5000)$ は作品に含まれる輪の数である． $M$ $(1 \leq M \leq 100000)$ は作品に含まれる黒い紐の本数である．

$u_i$, $v_i$ ($1 \leq u_i, v_i \leq N$)は $i$ 番目の黒い紐が $u_i$ 番目の輪と $v_i$ 番目の輪を繋いでいることを表す．入力で指定されなかった輪のペアに関しては白い紐で繋がれている．入力で与えられる作品は「よい作品」であることが保証されている．

Output

天井から吊るされている輪とそれ以外の輪の間を繋ぐ黒い紐の本数の最大値を求めよ．

Sample Input 1

Output for the Sample Input 1

Sample Input 2

Output for the Sample Input 2

Sample Input 3