実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 150000 点
問題文
命令列を読み込んでボードの上を歩くロボットがあります。この問題では、命令 とは S
, L
, R
の 3 種類の文字であり、命令列 とはこれらの文字からなる文字列です。
長さ L (= 300) の命令列が N (= 500) 個与えられます。あなたのタスクは、M \times M (M = 29) マスのボードを構築して、N 個の命令列に対してロボットをできるだけバラバラな位置で停止させることです。
ロボットはボードの中央のマス (上から 15 マス、左から 15 マス目) から上を向いて動作を開始し、命令列に含まれる命令を左から順に実行していきます。それぞれの命令の効果は次の通りです。
S
: 現在向いている方向に 1 マス進みます。L
: 90 度左に回転します。R
: 90 度右に回転します。
ただし、あなたはこれらの命令の効果に影響を及ぼすマスを使ってボードを構築することができます。使うことのできるマスは以下の通りです。
.
: 通常マスです。このマスの上で実行された命令は本来の効果を発揮します。#
: 壁マスです。ロボットがこのマスに進入しようとしたとき、その移動は失敗し、ロボットは手前のマスから動きません。なお、ボードの最も外側のマスはすべて壁マスでなければいけません。D
: 2 倍マスです。このマスの上で実行された命令の効果が 2 回連続で発揮されます (途中で通過したマスの効果は無視されます)。T
: 3 倍マスです。このマスの上で実行された命令の効果が 3 回連続で発揮されます (途中で通過したマスの効果は無視されます)。L
:L
マスです。このマスの上で命令R
が実行されると、通常マスの上でL
が実行されたときと同じ効果が発揮されます。R
:R
マスです。このマスの上で命令L
が実行されると、通常マスの上でR
が実行されたときと同じ効果が発揮されます。
これらのマスはそれぞれ何個でも使うことができます。
あなたのタスクを再度述べると、N 個の命令列に対してロボットができるだけバラバラな位置で停止するようなボードを構築することです。 より具体的には、あなたが構築したボードには以下のように点数が与えられます。
- 各マスの 停止カウント を 0 とする。
- 各命令列に対し、中央のマスからロボットにその命令列を実行させ、実行終了時にロボットが立っているマスの停止カウントを 1 増やす。
- 各マスに対する点数を以下のように定める。
- 停止カウントが 1 のとき、そのマスの点数は 10 点である。
- 停止カウントが 2 のとき、そのマスの点数は 3 点である。
- 停止カウントが 3 のとき、そのマスの点数は 1 点である。
- 上記以外のとき、そのマスの点数は 0 点である。
- すべてのマスに対する点数の和がそのボードの点数となる。
できるだけ高い点数を得るボードを構築してください。
制約
- N = 500
- M = 29
- L = 300
- S_i は長さ L の文字列である。
- S_i の文字は 1 文字ずつ独立に選ばれ、50% の確率で
S
、25% の確率でL
、25% の確率でR
となる。
入力
入力は以下の形式で与えられる。
N M L S_1 S_2 : S_N
出力
できるだけ高い点数を得るボードを以下の形式で出力せよ。
T_1 T_2 : T_M
ここで T_i はそれぞれ長さ M の文字列であり、.
, #
, D
, T
, L
, R
以外の文字を含んではならない。
また、ボードの最も外側の文字 (すなわち、T_1, T_M のすべての文字と各 T_i の最初と最後の文字) はすべて #
でなければならず、T_{15} の 15 文字目は #
であってはならない。
採点
単一のテストケースにおける点数は、問題文で述べた方法で算出される。
テストケースは 30 ケース与えられ、全てのテストケースの点数の和がその提出の得点となる。
なお、example_01 以外のケースで 1 ケースでも出力が不正であった場合、example_01 以外のケースの点数はすべて 0 点となる。
入力例0
6 7 7 RSLSSRS RSSLSSS SRSLLLL RSLSLLL LSLSLLL RRSRSRR
この入力は例示用の小さいサイズのものであり、制約を満たしません。
出力例0
####### #....## #..L..# #.T...# #..D..# #R....# #######
各命令列に対し、ロボットが停止するマスは以下のようになり、60 点を獲得できます。
####### #.5.1## #.3642# #.....# #.....# #.....# #######
入力例1
採点結果の「example_01」はこちらのデータとなります。このデータも採点対象です。
実行時間制限: 0 msec / メモリ制限: 0 KB
配点 : 0 点
A問題「ばらばらロボット」のビジュアライザ用のページです。問題ページではないので回答不要です。
テストケース生成
乱数シードを指定し、ローカル実行用にテストケースを生成する機能を用意しました。
- 本機能はchrome上での動作を想定しています。他の環境で正常に動作する保証はなく、特にIEでは動作しないことを確認しています。
- 本機能は当コンテスト上でのテストケースとの同一性を保証するものではありません。特に乱数生成の仕様に差異があることが考えられますので、予めご了承ください。
ビジュアライザー
入力ファイルと出力ファイルから、点数の計算および結果を可視化するビジュアライザを用意しました。
- 本ビジュアライザはchrome上での動作を想定しています。他の環境で正常に動作する保証はなく、特にIEでは動作しないことを確認しています。
- 本ビジュアライザから解答の提出はできません。 AtCoder A問題「ばらばらロボット」上より解答を提出して下さい。
- 本ビジュアライザ上で計算された点数は、当コンテスト上での点数を保証するものではありません。本ビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
- テキストファイルの改行コードはCRLFを想定しています。特にUnix系のOSをご使用の方はご注意下さい。
Score
0
※ロボットの数に応じて色が濃くなる