AtCoder Regular Contest 014

A - 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

高橋君は無駄な能力を数多く所持している。

そのうちのひとつの能力として彼は一列に並べたたこ焼きを、高速に赤と青の交互に染め上げることができる。
ちなみに味はつかない。

先頭1番目のたこ焼きを赤色としたとき、N 番目のたこ焼きは何色か答えよ。

入力

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

1 行目にはたこ焼きの番号を表す整数 N(1≦N≦1000) が与えられる。

出力

N 番目のたこ焼きが赤ければ Red、青ければBlue と 1 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

出力例 1

Blue

赤、青、赤、青と並ぶので、４番目は青である。

入力例 2

出力例 2

Red

入力例 3

出力例 3

Red

B - あの日したしりとりの結果を僕達はまだ知らない。

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

高橋君は分身できる。
今日はしりとりをしたい気分だったが、あいにく近くにお友達がいないので、分身した自分とすることにした。

便宜上元々いた高橋君を高橋くん、分身して新しく生まれた高橋君を高橋クンと呼ぶことにする。

さて、しりとりを十分に楽しんだ高橋くんと高橋クンであったが、悲しいことに彼らはしりとりのルールを知らなかったため勝敗をつけることが出来なかった。
しかしこんな事もあろうかと、自分の発言を全て録音することにしていた高橋君は無事にしりとりで使われた単語のリストを得ることが出来たのだ。

しりとりのルールは極めて単純である。以下の条件を守って単語を言っていくだけだ。

前の単語の、最後のアルファベットから始まる単語を言う。
一度使われた単語をもう一度使わない。

この条件を先に破った方が負けとなる。英語のしりとりなので、「ん」を言ったら負け、というルールは存在しない。

高橋くんに代わって、あなたは高橋くんの勝敗を判定しなければならない。

入力

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

N
W_{1}
W_{2}
:
W_{N}

1 行目には録音データから得られた単語の数を表す整数 N(1≦N≦100) が与えられる。
2 行目から N+1 行までの N 行では、高橋くんと高橋クンの発した単語 W_{i}が時系列順に高橋くんを先攻として交互に与えられる。
W_{i} の長さ L_{i} は 1≦L_{i}≦20 を満たす。また、 W_{i} は、小文字のアルファベットのみで構成される。

出力

高橋くんが勝利していればWIN、負けていればLOSE、勝敗が決まっていなければDRAW と 1 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

4
ab
ba
ab
cb

出力例 1

LOSE

高橋くんが ab を2回言ってしまっているので負けとなる。
高橋クンの cb もルールに反しているが、高橋くんのほうが先にルールに反している。

入力例 2

3
atcoder
redcoder
recorder

出力例 2

DRAW

どちらもルール違反をしていないので、引き分けとなる。

C - 魂の還る場所

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

高橋君が大好きなプラスチック製の円筒と不思議な赤青緑3色のボールがある。
このボールはぎりぎり円筒に入れることができる大きさである。
円筒の両端を便宜上、右と左と呼ぶことにすると、左右好きな方からボールを入れることができる。
このボールは同じ色のボールと接触すると消える性質を持っている。
さらに、これら 3 色の複数個のボールを入れる順番のみが決まっている時、それぞれのボールを左右のどちらから入れるかによって全てのボールを入れ終わった後に残るボールの数が変化する。

3 色の複数個のボールを入れる順番のみが与えられ、最後に円筒に残るボールの数が最小になるよう計画したとき、円筒に残るボール数の最小値を答えよ。

入力

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

N
S

1 行目にはボールの数を表す整数 N(1≦N≦50) が与えられる。
2 行目には入れるボールの順番 S が与えられ、 R は赤、 G は緑、 B は青色のボールを表す。 S は R, G, B の 3 種類の文字のみが N 文字で構成される。

部分点

1≦N≦15 を満たす入力にのみ正解した場合、部分点として 30 点が与えられる。

出力

最後に残るボールの数が最小になるように計画を行った時、その残る最小の数を 1 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

9
RGBGGBGBR

出力例 1

まず R を入れる。 R
次に G を左から入れる。 GR
B を右から入れる。 GRB
G を右から入れる。 GRBG
G を右から入れる。 GRBGG

この時 G が揃うので消える。 GRB

B を右から入れる。 GRBB

この時 B が揃うので消える。 GR

G を左から入れる。 GGR

この時 G が揃うので消える。 R

B を左から入れる。 BR
R を右から入れる。 BRR

この時 R が揃うので消える。 B

よって B が1つ残るので、答えは1である。

入力例 2

6
RGBRGB

出力例 2

D - grepマスター

実行時間制限: 4 sec / メモリ制限: 256 MB

問題文

高橋君は目grepが得意である。しかしこの世には目grepが得意な人が大勢いて特技にならないため、高橋君は新たな技を習得すべくgrepコマンドのマニュアルを目grepしていた。

検索コマンド grep には -B と -A というオプションがある。これは、

grep -B x -A y "needle" kakikomi.txt

とするとファイルkakikomi.txt でパターン "needle" にヒットした行だけでなく、その行の直前 x 行, 直後 y 行をあわせて表示するというものである。直前直後にある行数がx,yに満たない場合、あるだけ表示する。

同じ行番号の行が複数回表示されることになった場合、これらはマージされ、全体で1回ずつしか現れないようになる。この挙動については出力例の説明が詳しい。

今、ファイルkakikomi.txt に対してあるパターンでgrepを実行し、ヒットする行番号のリスト L_1,L_2,...,L_n がわかっているものとする。ここに m 個のクエリが与えられ、それぞれx,yが指定される。各クエリについて、-B x -A yのオプションをつけて同様にgrepを実行した場合、表示される行数を答えよ。

入力

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

all N M
L_{1}
L_{2}
:
L_{N}
x_{1} y_{1}
x_{2} y_{2}
:
x_{M} y_{M}

1 行目には kakikomi.txt の行数を表す整数 all(1≦all≦10^9)、ヒットした行数を表す整数 N(1≦N≦min(all,10^5)) 、クエリx, y の個数を表す整数 M(1≦M≦10^5) が与えられる。
2 行目から N+1 行までの N 行では、i 番目にヒットした行の行番号を表す整数 L_{i}(1≦L_{i}≦all) が与えられる。

L_i は L_i < L_{i+1}を満たす。

N+2 行目から N+M+1 行までの M 行では、L_i に対する各クエリを表す整数 x_i, y_i(0≦x_i, y_i≦10^9) が与えられる。

出力

各クエリx, y に対して表示される行数をそれぞれ1 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

出力例 1

5
4
7

ヒットした行は、 2 行目と 4 行目である。
x = 1, y = 1 のとき、それぞれのヒット範囲は、 1 ～ 3 行目、3 ～ 5 行目なので、合わせて 5行が答えとなる。
x = 3, y = 0 のとき、それぞれのヒット範囲は、 1 ～ 2 行目、1 ～ 4 行目なので、合わせて 4行が答えとなる。
x = 3, y = 4 のとき、それぞれのヒット範囲は、 1 ～ 6 行目、1 ～ 7 行目なので、合わせて 7行が答えとなる。

入力例 2

出力例 2