mtsmfm blog - オフラインリアルタイムどう書く E04 の問題

オフラインリアルタイムどう書く E04 の問題 - ドキドキ登山

2016-06-04

オフラインリアルタイムどう書く E04 の問題です。

問題

次の図は山を上から見たところである。

A ~ H が登山者、1 ~ 8 は方角、実線が登山道である。

A ~ H のうち登頂できた人を求めたい。

ルール

登山には次のルールがある:

登山道を麓から頂上に向かって登る
登る際に、横方向の登山道があればそちらを通る

ただし、一部の登山道は頂上からの落石によって通行止めになっており、通行止めに行きあたると登頂失敗になる。

落石は、頂上から登山者と同じルールで麓まで転がってくる。

先述した例 (2512:C) だと、通行止めの道は次の図の赤破線のようになる。

よって、頂上に辿りつけた人は次の図の赤丸のようになる。

入力

2512:C のような形式。コロンの前は頂上と並行に伸びる登山道の情報。頂上から順に並んでいる。コロンの後は落石の開始位置。

出力

DEFGH のような形式。登頂に成功した人をアルファベット順で並べる。

補足

実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

#	入力	期待	状況へのリンク
0	2512:C	DEFGH	状況
1	1:A	CDEFGH	状況
2	:C	ABDEFGH	状況
3	2345:B	AGH	状況
4	1256:E	ABCDH	状況
5	1228:A	ADEFG	状況
6	5623:B	AEFGH	状況
7	8157:C	ABDEFGH	状況
8	74767:E	ABCFGH	状況
9	88717:D	ABCEFGH	状況
10	148647:A	ACDEFH	状況
11	374258:H	BCDEFH	状況
12	6647768:F	ABCDEH	状況
13	4786317:E	ABFGH	状況
14	3456781:C		状況
15	225721686547123:C	CEF	状況
16	2765356148824666:F	ABCDEH	状況
17	42318287535641783:F	BDE	状況
18	584423584751745261:D	FGH	状況
19	8811873415472513884:D	CFG	状況
20	74817442725737422451:H	BCDEF	状況
21	223188865746766511566:C	ABGH	状況
22	2763666483242552567747:F	ABCG	状況
23	76724442325377753577138:E	EG	状況
24	327328486656448784712618:B		状況
25	4884637666662548114774288:D	DGH	状況
26	84226765313786654637511248:H	DEF	状況
27	486142154163288126476238756:A	CDF	状況
28	1836275732415226326155464567:F	BCD	状況
29	62544434452376661746517374245:G	G	状況
30	381352782758218463842725673473:B	A	状況

テストデータ

/*0*/ test("2512:C", "DEFGH")
/*1*/ test("1:A", "CDEFGH")
/*2*/ test(":C", "ABDEFGH")
/*3*/ test("2345:B", "AGH")
/*4*/ test("1256:E", "ABCDH")
/*5*/ test("1228:A", "ADEFG")
/*6*/ test("5623:B", "AEFGH")
/*7*/ test("8157:C", "ABDEFGH")
/*8*/ test("74767:E", "ABCFGH")
/*9*/ test("88717:D", "ABCEFGH")
/*10*/ test("148647:A", "ACDEFH")
/*11*/ test("374258:H", "BCDEFH")
/*12*/ test("6647768:F", "ABCDEH")
/*13*/ test("4786317:E", "ABFGH")
/*14*/ test("3456781:C", "")
/*15*/ test("225721686547123:C", "CEF")
/*16*/ test("2765356148824666:F", "ABCDEH")
/*17*/ test("42318287535641783:F", "BDE")
/*18*/ test("584423584751745261:D", "FGH")
/*19*/ test("8811873415472513884:D", "CFG")
/*20*/ test("74817442725737422451:H", "BCDEF")
/*21*/ test("223188865746766511566:C", "ABGH")
/*22*/ test("2763666483242552567747:F", "ABCG")
/*23*/ test("76724442325377753577138:E", "EG")
/*24*/ test("327328486656448784712618:B", "")
/*25*/ test("4884637666662548114774288:D", "DGH")
/*26*/ test("84226765313786654637511248:H", "DEF")
/*27*/ test("486142154163288126476238756:A", "CDF")
/*28*/ test("1836275732415226326155464567:F", "BCD")
/*29*/ test("62544434452376661746517374245:G", "G")
/*30*/ test("381352782758218463842725673473:B", "A")

状況一覧

2512:C

1:A

:C