AtCoder Regular Contest 005

A - 大好き高橋君

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

問題文

　高橋君は自分が大好きなので、自分の評判を調べるために自分の名前が入っているツイートを調べたいと考えました。しかし彼のフォロー数は多いので、タイムラインを 1 つずつ確認して自分に関係あるつぶやきを探すのは面倒です。

　そこで高橋くんを手伝うために、与えられる文から高橋君を表す単語が現れる回数を数えてください。
　ただし、単語の一部に高橋君を表す単語を含んでいた場合も、高橋君を表す単語と完全に一致しない限り、その単語を高橋君を表す単語として数えないでください。

　以下の3単語が高橋君を表す単語です。

TAKAHASHIKUN（高橋君をヘボン式ローマ字にして、全て大文字にしたもの）
Takahashikun（高橋君をヘボン式ローマ字にして、先頭の 1 文字のみ大文字、残りは小文字にしたもの）
takahashikun（高橋君をヘボン式ローマ字にして、全て小文字にしたもの）

入力

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

N
w_{0} w_{1} … w_{N-1}.

入力は 2 行ある。
1 行目には、2 行目に与えられる文に含まれる単語数を表す整数 N(1≦N≦50) が与えられる。
2 行目には 2 文字以上 100 文字以下の 1 文が与えられる。
- 文は単語 w_i(0≦i≦N-1)から成り、各単語は空白で区切られている。
- 最後の単語 w_{N-1} の後には空白を挟まず . がある。
- 単語 w_{i}(0≦i≦N-1) は英字(A-Z, a-z)で成り立っている。

出力

与えられた文の中で高橋君を表す単語が現れる回数を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

5
Takahashikun is not an eel.

出力例 1

Takahashikun が 1 回現れます。

入力例 2

5
TAKAHASHIKUN loves TAKAHASHIKUN and takahashikun.

出力例 2

TAKAHASHIKUN が 2 回、takahashikun が 1 回現れるので 2+1=3 が答えです。

入力例 3

6
He is not takahasikun but Takahashikun.

出力例 3

Takahashikun が 1 回現れます。
takahasikun は takahashikunではないので、高橋君を表す単語ではありません。

入力例 4

1
takahashikunTAKAHASHIKUNtakahashikun.

出力例 4

単語の一部に高橋君を表す単語が含まれていても、高橋くんを表す単語そのものでなければ当てはまりません。

入力例 5

18
You should give Kabayaki to Takahashikun on July twenty seventh if you suspect that he is an eel.

出力例 5

Takahashikun が 1 回現れます。

出典

ARC 005

B - P-CASカードと高橋君

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

問題文

　高橋君は来る 7 月 27 日の土用の丑の日に備えて、高級なうなぎを通販で買うことにしました。支払いはネット銀行を通して行います。
　高橋君が利用しているネット銀行のカードの裏には、下図のような縦 9 文字 ×横 9 文字の数字から成る乱数表がついています。支払う時は、この乱数表の指定された位置から縦横斜めの中で指定された向きに 4 文字連続で抜き出して入力し、それが正しいかによって本人確認を行います。
　下図は「上から 1 文字目、左から 1 文字目」の位置から「右下斜め」の方向が指定された時の 4 文字を抜き出した例です。この場合は 7930 が入力する数字になります。

図：1 行目 1 文字目から右下方向に 4 文字抜き出す例

　乱数表の一番端の文字を抜き出した後もさらに文字を抜き出す必要がある場合は、向きを変更して残りの文字を抜き出します。向きの変更は以下のように行います。

読み込み時に進んでいた方向が上下左右の場合
- 向きを 180 度変える
読み込み時に進んでいた方向が斜めの場合
- 角で向きを変更する場合
  - 向きを 180 度変える
- 左右の端で向きを変更する場合
  - 左右への向きのみ逆にし、上下への向きはそのままにする
- 上下の端で向きを変更する場合
  - 上下への向きのみ逆にし、左右への向きはそのままにする

　これらの向きの変更を図で示すと下図のようになる。

図：変更する向きの一覧

　乱数表、抜き出す最初の数字の位置、抜き出す向きが与えられる時、本人確認のため入力する 4 文字を答えてください。

入力

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

x y W
c_{11}c_{12}…c_{19}
c_{21}c_{22}…c_{29}
:
:
c_{91}c_{92}…c_{99}

入力は 10 行ある。
1 行目には、抜き出す最初の数字が左から何文字目かを表す整数 x(1≦x≦9)、抜き出す最初の数字が上から何文字目かを表す整数 y(1≦y≦9)、抜き出す方向を表す W が空白で区切られて与えられる。

抜き出す方向 W は R、L、U、D、RU、RD、LU、LD のいずれかで与えられ、抜き出す方向が以下であることを表す。

R : 右方向
L : 左方向
U : 上方向
D : 下方向
RU : 右上に斜め方向
RD : 右下に斜め方向
LU : 左上に斜め方向
LD : 左下に斜め方向

2 行目からの 9 行は、乱数表の数字を表す整数 c_{ij}(1≦i,j≦9) が与えられる。

i 行目 j 番目の数字は、乱数表の上から i 番目、左から j 番目の数字が c_{ij} であることを表す。
c_{ij} は 0-9のいずれかである。

出力

指定された位置から指定された方向に数字を 4 文字抜き出し、それらの数字を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

出力例 1

乱数表から抜き出す 4 文字は下図のように右方向に抜き出します。

入力例 2

出力例 2

乱数表から抜き出す 4 文字は下図のように左上方向に抜き出します。

入力例 3

出力例 3

下図のように下方向へ 3 文字抜き出した後、向きを上方向に変えて残りの 1 文字を抜き出します。

入力例 4

出力例 4

下図のように左上方向へ 2 文字抜き出した後、向きを右下方向に変えて残りの 2 文字を抜き出します。

入力例 5

出力例 5

下図のように右下方向へ 1 文字抜き出した後、向きを左下方向に変えて残りの文字を抜き出します。
3 文字目まで抜き出した後、さらに向きを左上方向に変えて残りの 1 文字を抜き出します。

出典

ARC 005

C - 器物損壊！高橋君

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

問題文

　良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
　彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
　しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。

　高橋君が魚屋に辿り着くことができるかどうか答えてください。

入力

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

H W
c_{(0,0)}c_{(0,1)} … c_{(0,W-1)}
c_{(1,0)}c_{(1,1)} … c_{(1,W-1)}
:
:
c_{(H-1,0)}c_{(H-1,1)} … c_{(H-1,W-1)}

入力は H+1 行ある。
1 行目は、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
2 行目からの H 行には、格子状の街の各区画における状態 c_{(i,j)}(0≦i≦H-1, 0≦j≦W-1) が与えられる。

i 行目 j 文字目の文字 c_{(i,j)} はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。

s : その区画が家であることを表す。
g : その区画が魚屋であることを表す。
. : その区画が道であることを表す。
# : その区画が塀であることを表す。

高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
与えられた街の外を通ることはできない。
s と g はそれぞれ 1 つずつ与えられる。

出力

塀を 2 回まで越えることで、家から魚屋まで辿り着くことができる場合は YES、辿りつけない場合は NO を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

4 5
s####
....#
#####
#...g

出力例 1

YES

(1,2),

(2,2),

(3,2)

入力例 2

4 4
...s
....
....
.g..

出力例 2

YES

塀が無いので到達することができます。

入力例 3

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...

出力例 3

YES

(1,6), (2,6) の 2 つの塀を壊すことで到達することができます。

入力例 4

6 6
.....s
###...
###...
######
...###
g.####

出力例 4

YES

一例として (3,3), (2,3), の 2 つの塀を壊すと、到達することができます。

入力例 5

1 10
s..####..g

出力例 5

NO

塀を 2 つ壊しても魚屋に到達することができません。

出典

ARC 005

D - 連射王高橋君

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

問題文

　ようやく魚屋に到着した高橋君は、あまりお金を持ってきていなかったことに気づきました。これでは定価でうなぎを買うことができません。そこで、店主に値引きしてくれないか交渉することにしました。ところが、魚屋の店主はお年寄りで耳が遠く、値段を言う高橋君の声がうまく聞こえていないようです。仕方がないので高橋君は近くにあった電卓を使って、値段を伝えることにしました。
　しかし困ったことに、高橋君はうっかり電卓を落としていくつかのボタンを壊してしまいました。電卓には数字(0-9), 加算記号(+), イコール(=) の 12 個のボタンがあります。0、1、+、= が壊れていないことは確かですが、それ以外のボタンは壊れている可能性があります。
　例えば 0、1、2、+、=が壊れていない場合は、店主に 11 を伝える方法の例の一部としては以下のようなものがあります。

1+1+1+1+1+1+1+1+1+1+1=
2+2+2+2+2+1=
11
1+2+1+2+1+1+1+2=
10+1=

　この時、+ と = は以下のように用いる。

+ : 数字と数字の間でのみ押すことができます。
= : + を使用する場合は一番最後に必要です。+ を使っていない場合に押しても何も起きません。

　さて、この魚屋の店主は気難しいので、早く伝えないと怒ってしまいます。そこでボタンを押す回数はなるべく少なくしたいです。先ほどの例の場合は 11 と押すと、2 回ボタンを押すだけで 11 を表すことができ、この場合が押す回数は最小になります。

　電卓に表示させたい数字が与えられた時、壊れていないボタンのみを用いて数字を表示させるために、押したボタンの回数が最小となる場合に押したボタンを順に答えなさい。なお、加算の形で表す場合は、項の順番は問いません（1+2=が正解ならば、2+1=も正解です）。

入力

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

b_1b_2...b_N
price

入力は 2 行のみである。
1 行目には N(2≦N≦10) 文字の整数の文字列が与えられる。
- b_i(1≦i≦N)は、0-9のいずれかであり、壊れていないボタンを表す。
- b_1からb_Nまでに、0、1の 2 つは必ず含まれる。
- 1 行目の中で、b_i は小さい順に並んでおり、重複はしない。
- この行に表示された数字のボタンと+と=を用いることができる。
2 行目には表示させたい整数 price(1≦price＜10^{18}) が与えられる。
- 注：64bit型整数型を使うことを推奨します。

出力

壊れていないボタンのみを用いて指定された数字を表示させるために、押したボタンの回数が最小値となる場合に押したボタンを順に答えなさい。
なお、最後には改行を出力せよ。

入力例 1

01257
2380

出力例 1

2270+110=

使用できるボタンは0, 1, 2, 5, 7, +, = の 7 つです。
3 と 8 が壊れてしまっているので、加算の形で表す必要があります。

入力例 2

0123456789
17564523527628452

出力例 2

17564523527628452

全てのボタンが使えるので、入力したい数字を直接入力できます。

入力例 3

01
9

出力例 3

1+1+1+1+1+1+1+1+1=

0 と 1 しか使えないので、1 つずつ足すしかありません。

入力例 4

019
2727

出力例 4

909+909+909=

入力例 5

01457
245723852196245230

出力例 5

175711751155145110+70011701041100110+400000000010=

出典

ARC 005