AtCoder Regular Contest 024

A - くつがくっつく

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ARCマートは土曜日だけに営業する靴屋さんです。扱う靴は1種類だけで、サイズ以外の見分けはつきません。残念なことに、 1 週間ぶりに店を開けると空き巣に入られてしまったらしく、靴がめちゃくちゃに散乱していました。

残っている靴を全部かき集めると、左足の靴が L 足、右足の靴が R 足みつかりました。ただ、靴を売るには同じサイズを両足分そろえてペアにしなければなりません。靴の種類はすべて同じなので、ペアを作るときはサイズだけを気にすれば良さそうです。

もう開店まで時間がないので、店長のために、最大で何組のペアを作ることができるか求めてください。

入力

入力は以下の形式で標準入力から与えられる

L R
l_1 l_2 … l_L
r_1 r_2 … r_R

1 行目にみつかった左足の靴の数 L (1 ≦ L ≦ 100) 、右足の靴の数 R (1 ≦ R ≦ 100) が空白区切りで与えられる。
2 行目にはL個の整数が空白区切りで与えられる。 i 番目には i 番目の左足の靴のサイズ l_i (10 ≦ l_i ≦ 40) が与えられる。
3 行目にはR個の整数が空白区切りで与えられる。 i 番目には i 番目の右足の靴のサイズ r_i (10 ≦ r_i ≦ 40) が与えられる。

出力

作成可能な靴のペア数の最大値を 1 行で出力せよ。

入力例1

3 3
20 21 22
30 22 15

出力例1

サイズ 22 のペアが 1 つだけ作れます。

入力例2

3 4
10 11 10
12 10 11 25

出力例2

サイズ 10 、サイズ 11 のペアがそれぞれ 1 つずつ作れます。

入力例3

5 5
10 10 10 10 10
10 10 10 10 10

出力例3

入力例4

5 5
10 11 12 13 14
30 31 32 33 34

出力例4

B - 赤と黒の木

Time Limit: 2 sec / Memory Limit: 256 MB

問題文にミスがあったため、正しいものに差し替えました。「何日後に全ての木の色が…」→「何日目に全ての木の色が…」（22:00）

問題文

レッドブラックアイランドには特殊な性質を持った木が生えています。この木は赤色になったり黒色になったりする変わった木です。この木には複数の個体が 1 箇所に集まって、ある円の円周上に 1 列に並ぶように生えるという特徴があります。

また、この木は同じ色が 1 箇所に集中しないように1日ごとに「バランスをとる」という性質があります。具体的には、自分とその両隣の木の色がすべて同じ色だったら、その木は次の日は異なる色に変わるという性質です。より形式的に言うと、ある3つの木 A, B,C がこの順に並んでいて、それぞれの色が C_A, C_B, C_C であるとします。このとき C_A = C_B = C_C = 赤だったならば次の日 C_B は黒になります。黒と赤が反対の場合も同様です。

しかし、この木は隣の木が次の日どうなるかに関わらず、その日の自分の状況だけを見て「バランスをとる」ことをします。そのため 1 日たっても同じ色の木が 3 つ連続で並ぶという事もあり得ます(下の入力例を参照してください)。そのときは次の日も同様に「バランスをとる」ことをします。

研究者であるあなたは N 個の木からなるある群れの 1 日目の色の状況を観測しました。何日目に全ての木の色が変わらなくなるか求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N
color_1
color_2
:
color_N

1 行目には木の本数 N (3 ≦ N ≦ 10^5) が与えられる。
2 行目からの N 行のうち i 行目には i 番目の木の色の情報 color_i (color_i = 0, 1) が与えられる。
color_i = 0 の場合、その木の色は黒である。 color_i = 1 の場合、その木の色は赤である。
木は円形状に並んでいるので i(1 ≦ i ≦ N - 1) 番目の木は i + 1 番目の木と隣り合っており、 N 番目の木は 1 番目の木と隣り合っている。

出力

すべての木の色が変わらなくなる日が何日目かを 1 行で出力せよ。もし、そのような日が来ないのならば -1 を出力せよ。

入力例1

出力例1

下図のように変化する。2日目以降は変化しない。

1 日目、 3 番目の木が、両隣と自分の色が同じなので次の日、色が変わる。
2 日目以降は変化しない。

入力例2の画像にミスがあったため、正しいものに差し替えました（21:13）

入力例2

出力例2

下図のように変化する。 6 番目の木と 1 番目の木が隣り合っていることに注意せよ。

1 日目、 1, 5, 6 番目の木が、両隣と自分の色が同じなので次の日、色が変わる。
2 日目、 6 番目の木が、両隣と自分の色が同じなので次の日、色が変わる。
3 日目以降は変化しない。

入力例3

出力例3

-1

全部黒という状態と全部赤という状況を交互に繰り返す。

C - だれじゃ

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

Takahashi 市の住人はダジャレが大好きであり、Takahashi 市で上手に渡り歩くためには高度なダジャレ能力が要求される。

Takahashi 市の住人の間では、引っ越してきた相手に様々なダジャレを浴びせることが習慣となっている。最近の Takahashi 市では「アナグラムダジャレ」というものが流行っている。「アナグラムダジャレ」とは、文章の中に、互いに共通部分を持たない、2 つの同じ長さの文字列に関して、一方に出てくる文字列を並べ替えると他方の文字列になるというものである。その文字列の長さが m であるとき、この文章は長さ m の「アナグラムダジャレ」を含むと呼ぶことにする。

例えば、「だじゃれをいったのはだれじゃ」という文章を考えると、先頭 4 文字からなる文字列「だじゃれ」と末尾 4 文字からなる文字列「だれじゃ」は互いに共通部分を持たず、かつ「だじゃれ」を並べ替えると「だれじゃ」になるため、この文章は長さ 4 の「アナグラムダジャレ」を含むということになる。

Takahashi 市に引っ越したばかりの青木君は、Takahashi 市で上手に渡り歩くために、「アナグラムダジャレ」検知能力を身につけたいと考えている。青木君は長さ K の「アナグラムダジャレ」を発見するのが苦手なので、文章生成ソフトを用いて特訓することにした。

ところが文章生成ソフトには長さ K の「アナグラムダジャレ」が含まれているか判定する機能がついていない。

あなたは青木君のために長さ K の「アナグラムダジャレ」が含まれているかを判定するプログラムを作らなければならない。

入力

入力は以下の形式で標準入力から与えられる。

N K
S

1 行目には、与えられる文章の長さ N (1 ≦ N ≦ 10^5) および求めたい「アナグラムダジャレ」の長さ K (1 ≦ K ≦ N) が空白区切りで与えられる。
2 行目には、判定したい文章が与えられる。この文章は長さ N で、半角の小文字英字のみからなる。

部分点

この問題には部分点が設定されている。

N ≦ 8 を満たすデータセット 1 に正解した場合は、15 点が与えられる。
N ≦ 300 を満たすデータセット 2 に正解した場合は、上記とは別に 15 点が与えられる。
N ≦ 5,000 を満たすデータセット 3 に正解した場合は、上記とは別に 15 点が与えられる。
追加制約のないデータセット 4 に正解した場合は、上記とは別に 55 点が与えられる。

出力

長さ K の「アナグラムダジャレ」が含まれるなら YES を、含まれないなら NO を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

8 3
abcdbcae

出力例1

YES

先頭から 1 文字目を起点とした 3 文字からなる文字列 abc と、先頭から 5 文字目を起点とした 3 文字からなる文字列 bca は、一方を並べ替えると他方になるので、長さ 3 の「アナグラムダジャレ」を含むといえる。

入力例2

7 4
abcdcba

出力例2

NO

先頭から 1 文字目を起点とした 4 文字からなる文字列 abcd と、先頭から 4 文字目を起点とした 4 文字からなる文字列 dcba は、一方を並べ替えると他方になるが、先頭から 4 を共通して使用しているため条件を満たさない。他の取り出し方をしても条件をみたすことはない。

入力例3

8 1
issample

出力例3

YES

D - バス停

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋国の高橋王は国内の交通の便を良くするためにいくつかバス停を設置することにしました。高橋国には東西に走る道路と、南北に走る道路の 2 種類しかありません。ある基準点から東に i キロメートルの地点に i 番目の南北の道路が敷かれており、北に j キロメートルの地点に j 番目の東西の道路が敷かれています。 i 番目の南北の道路と j 番目の東西の道路の交差点を (i, j) と表すことにします。道路は無限に長いのでどの 2 つの直交する道をとってもどこかで交差します。バス停は交差点にのみ設置し、同じ交差点にはたかだか 1 個までしかバス停を設置しません。

いまちょうど N 個のバス停を設置し終わりました。しかし、ここで高橋王は重大なミスに気づきます。道路が狭すぎてバスが道を曲がれないのです。つまり、どの路線も東西もしくは南北のどちらか一方にしか移動できないということになります。これでは、バスのみで行き来ができないバス停ができてしまいます。これでは不便なので、新たにいくつかのバス停を設置してどの 2 つのバス停間もバスの乗り換えを繰り返すことで移動できるようにします。なお、バスの乗り換えはバス停でしかできません。また、その乗り換えが遠回りになっても不便なので、どの 2 つのバス停間も総移動距離がバス停間のマンハッタン距離と等しくなるようなバスの乗り換えが可能になるように設置します。つまりどの 2 つのバス停 (a, b), (c, d) にも、総移動距離が |a - c|+|b - d| キロメートルとなるような乗り換え経路があるようにするということです。

予算の関係で合計で 10,000 個のバス停しか設置できません。つまり、残り 10,000 - N 個しか設置できません。その範囲で上記の条件をみたすようにバス停を追加するとき、新たに置くバス停の場所を求めてください。解が複数通り存在する場合はどれを求めても構いません。

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 y_1
x_2 y_2
:
x_N y_N

1 行目には、既に設置されているバス停の個数を表す整数 N (2 ≦ N ≦ 1,000) が与えられる。
2 行目からの N 行のうち i 行目には i 番目のバス停の設置されている位置を表す整数 x_i (1 ≦ x_i ≦ 1,000) と y_i (1 ≦ y_i ≦ 1,000) が空白区切りで与えられる。これは i 番目のバス停が交差点 (x_i, y_i) に設置されているということである。
i \neq j ならば (x_i, y_i) \neq (x_j, y_j) が成り立つ
解は少なくとも 1 つ存在する。

部分点

この問題には部分点が設定されている。

2 ≦ N ≦ 100 を満たすテストケース全てに正解した場合 10 点が得られる。
2 ≦ N ≦ 1,000 を満たすテストケース全てに正解した場合さらに 90 点が得られる。合計で 100 点となる。

出力

以下の形式で追加するバス停の位置を出力せよ

M
x_1 y_1
x_2 y_2
:
x_M y_M

1 行目には、新たに設置するバス停の個数を表す整数 M (0 ≦ M ≦ 10,000 - N) を出力せよ。
2 行目からの M 行のうち i 行目には i 番目のバス停の設置する位置を表す整数 x_i (1 ≦ x_i ≦ 1,000) と y_i (1 ≦ y_i ≦ 1,000) を空白区切りで出力せよ。これは i 番目のバス停を交差点 (x_i, y_i) に設置するということである。
i \neq j ならば (x_i, y_i) \neq (x_j, y_j) が成り立たたなければならない。
新たに設置するバス停の位置が、既に設置されているバス停の位置と重複してはいけない。
既に設置されているバス停と新たに追加したバス停を合わせた N+M 個のバス停について、どの 2 つについても最短距離がマンハッタン距離と等しくならなければならない。

入力例1

2
1 1
2 2

出力例1

1
1 2

バス停 (1, 1) を通るバスは (i, 1) もしくは (1, j) にしか訪れることができない( i, j は任意の整数)。同様にバス停 (2, 2) を通るバスは (i, 2) もしくは (2, j) にしか訪れることができない( i, j は任意の整数)。 (1, 2) というバス停を追加すればどの 2 つも行き来することができるようになる。なお、 (2, 1) でも構わないし、両方を追加しても構わない。

入力例2

出力例2

新たに追加したバス停どうしについても最短経路がマンハッタン距離と等しくならなければならないことに注意せよ。

入力例3

出力例3