A - Multiple Pieces
Time Limit: 10 sec / Memory Limit: 1024 MB
背景
※この「背景」の項に書かれている文章は問題とあまり関係がありません。問題文は「問題文」の項から始まります。
20XX 年、RCO 量子サーバールーム ━━━ ここには RCO の持つ大量の量子コンピュータが所狭しと並んでいる。
2016 年に量子コンピューティングに参入した RCO アドテク部は、2017 年には実際の量子コンピュータ上で機械学習プログラムを走らせたり、量子アニーリングの国際学会のホストを務めるなどして勢いを増し、この時代では量子コンピュータ専門の企業になっていた。
競技プログラミングの経験を買われて入社した社員 X は、広告マッチングシステムの高速化に携わっていたが、今やその仕事も量子コンピュータに取って代わられ、プログラミングの仕事を失った彼は量子コンピュータを接続する仕事をしている。
RCO の長年の研究によって、量子コンピュータには以下の性質があることが明らかになった。
- 量子コンピュータは K 台連結することによって、その力を発揮する。 K 台より多くても少なくても機能しない。この連結した K 台を「ピース」と呼ぶ。
- あるピースに含まれる量子コンピュータは、別のピースに含むことができない。
- ピースのもつ力は、ピース内の各量子コンピュータの能力の積に等しい。
このサーバールームには H 行 W 列のグリッド状に H \times W 台の量子コンピュータが並んでいて、社員 X の仕事は、どの量子コンピュータを接続するか決めることである。量子コンピュータは、辺で接している隣の量子コンピュータとしか接続できない。接続された量子コンピュータを辿って到達できる時、それらの量子コンピュータは連結であるといえる。
社員 X は適切にピースを作ることで、全てのピースの力の合計を最大化したいが、プログラミングの仕事を失った彼はプログラミング能力も失ってしまった！そこで、彼の親しい友人であるあなたが、そのプログラムを書いてあげることにした。
問題文
同じ大きさの正方形のマスが H 行 W 列並んだ長方形のグリッドがあります。1 \leq i \leq H, 1 \leq j \leq W を満たす整数 i と j について、 i 行 j 列に位置するマスの座標を (i,\ j) と表します。各マスには 0 以上 9 以下の整数が 1 つ書かれています。
このグリッド上で、いくつかのピースを作ります。ピースとは、ちょうど K 個のマスからなる、グリッド上の領域です。 ピース内のマス同士は互いに連結でなければいけません。マス同士が連結しているというのは、ピース内の全てのマスの組について、ピース内で縦橫に接続したマスを辿って互いに到達可能であることをいいます。
ピースは可能な限りいくつでも作ることができますが、あるピースを作るために使用したマスは、別のピースを作るために使用することはできません。
各ピースはスコアを持ちます。ピースが含むマスに書かれた K 個の整数の積が、そのピースのスコアになります。全てのピースのスコアの合計値を最大化してください。
制約
- H = 50
- W = 50
- K = 8
- 各テストケースは、各マスに書かれる整数が一様乱数によってマスごとに独立に 0 以上 9 以下の整数が入るように生成されます。
入力
入力は以下の形式で標準入力から与えられます。
H W K s_1 s_2 : s_H
- H はグリッドの行数を表す整数であり、H = 50 を満たします。
- W はグリッドの列数を表す整数であり、W = 50 を満たします。
- K は 1 つのピースを作るマスの数を表す整数であり、K = 8 を満たします。
- s_i (1 \leq i \leq H) はグリッドの i 行目を表す長さ W の文字列であり、
s_i を構成する文字はいずれも
0から9までの整数です。 s_i の j (1 \leq j \leq W) 文字目は、グリッドにおける (i,\ j) のマスの整数を表します。
出力
出力は以下の形式で標準出力に出力してください。
C
y_{1,1} x_{1,1}
y_{1,2} x_{1,2}
:
y_{1,K} x_{1,K}
y_{2,1} x_{2,1}
y_{2,2} x_{2,2}
:
y_{C,K} x_{C,K}
- 1 行目にピースの数 C を出力してください。
- 続く C \times K 行には、各行にスペース区切りで、マスの位置を表す 2 つの整数を出力してください。
- (c - 1) \times K + k \ (1 \leq c \leq C ,\ 1 \leq k \leq K) 番目には、c 個目のピースで使われている k 個目のマスの位置 (y_{c,k}, \ x_{c,k}) の行と列を、スペース区切りで順番に出力してください。
- 同じピースで使われているマスは連続して出力してください。
- 同じピースで使われているマスは、どのような順番で出力しても構いません。
- 同じピースで使われているマスは、ちょうど K 個を出力してください。
- 同じピースで使われているマスは、連結している必要があります。
- 各ピースはどのような順番で出力しても構いません。
採点について
各テストケースについて、出力されたピースのスコアの合計値を 10,000 で割り、小数点以下を切り上げた整数が、そのテストケースの得点になります。
テストケースは全部で 10 個あります。各テストケースの得点の合計値が、この問題の得点になります。
入力例1
50 50 8 53201047392344411470438731252072209638476606576022 13242641632370617792332244270350675420864470404947 76372756316250650550563212732102937351075767336672 43391440260272522122049404306241926052045602433410 52720091423022222223344046324704721322132522334463 61693424425167321660472564434627234092497347246494 74134790436364436322363453027722019104342653173246 06407501031023661315440613726761261950342364317750 32434003036734297520344434846325625906542524345344 05729429300314444521730193634776225440322622762751 86170432967422452264329256425612350934624120326541 26260636676449250472787131576465747405632235055443 40432921056447267224144437767405026230355213327648 24472704922530039761140156512267320526045880236176 07436062226225795544236739634472433612487916576911 55028479331202644253542466261627757154341742036422 44736123293411696555237251437134202024002321292635 81006264110473511002519270476632234036184209203337 34270476462376904464776536713540006776077721473323 32686034469090324371414045247233600414023574431213 04080796152524541314625733207636637252102345120474 36904177763204264504704640313204912205748211284652 57646677253297155293792204031260531495473582235447 61433022620013614311260112334301203542233443703533 26244220666366257106223555253272744437143551534343 72304587152225442705443405915460720321040950035230 47266334792647716333950266050273713405293544063606 42436560231720147179723145056172462274137306344833 67443441401341276340150714410757027270244643654052 40404753669203250556387534301404004772563702525335 33666140790372604312034023231462405523170203279455 28102241646055944326071031547720270757259214611268 87746061343006140377547262199332060353244672704332 41225292920224383122136357428437525343572422270572 92160034046626479600394426924399953726374944127112 34214633560182413271544514253244940522222796462242 90062659764619121220592222437422113522730203122504 62132594362434364325233673235334175411672571335787 73620117121304602302723930343349513021441324772513 17763541417154976777536460213763760329204066378655 63263664266374779346744404484544692004111522323332 44632343821194331534223464082067723522091642446477 19604176094424473236373041633400242226774002570136 26233643026251007443132567680196513234006280452006 56654403268971142737776260023025532206663443245553 03675233864254722764052295365207973334724257032549 26647441241535162193323334617330476964344433334454 72463395769420225214343614245237240974142331159757 14226384625321023247202066906229042200415265466217 22420733370592047743255351070026772752224341534396
出力例1
2 1 1 2 1 1 2 1 3 2 3 3 3 4 3 4 2 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5
この結果は、下の図のようになります。
1 個目のピースのスコアは、1 \times 5 \times 3 \times 2 \times 2 \times 3 \times 3 \times 3 = 1620 より 1620 です。
2 個目のピースのスコアは、0 \times 3 \times 4 \times 7 \times 4 \times 9 \times 0 \times 0 = 0 より 0 です。
よって、このテストケースの得点は (1620+0)/10000=0.1620 の、小数点以下を切り上げて 1 となります。
ジェネレータとテスター
ジェネレータとテスターを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用したことで発生したトラブルには対応できません。ご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。
B - Food Collector
Time Limit: 10 sec / Memory Limit: 1024 MB
背景
わんわん！
問題文
H行W列の正方形のマップがあります。マップの各マスは、障害物のあるマス・空マスのいずれかです。いくつかの空マスには高々1個のエサが置かれています。
最初の行を1行目、最初の列を1列目とします。 マップのsr行sc列目のマスに1匹の犬がいます。犬は、開始から0,1,2,…秒後に、辺で隣接した障害物以外のマスに移動できます。犬の移動は瞬時に完了するものとします。 犬がエサのあるマスに移動すると、エサを必ず獲得します。エサを獲得すると、そのマスにあったエサは消え、あなたはエサに対応するスコアを得ます。 エサiのスコアの初期値はF_iで、1秒ごとにD_iずつ減少します。減少は犬が移動・獲得した直後に発生します。
犬の、開始から0,1,2,…,K-1秒後の行動を出力して、スコアを最大化してください。
入力
入力は以下の形式で標準入力から与えられます。入力はすべて整数です。
H W K sr sc s_1 s_2 : s_H N fr_1 fc_1 F_1 D_1 fr_2 fc_2 F_2 D_2 : fr_N fc_N F_N D_N
- H=W=50
- K=2500
- 1\leq sr\leq H
- 1\leq sc\leq W
- s_i (1 \leq i\leq H) はマップの i 行目を表す長さ W
の文字列であり、s_i
を構成する文字は
#,.のいずれかです。#は障害物マスを表します。.は空マスを表します。
- Nはエサの置かれるマスの個数を表します。
- 1\leq fr_i \leq H (1\leq i\leq N).
- 1\leq fc_i \leq W (1\leq i\leq N).
- 0\leq F_i \leq 10^5 (1\leq i\leq N).
- 0\leq D_i \leq 100 (1\leq i\leq N).
- fr_i, fc_i はエサの置かれるマスの行数, 列数を表します。
- F_i, D_i はエサのスコアの初期値, 1秒あたりの減少スコアを表します。
- (sr, sc), (fr_i, fc_i)は互いに異なります。またこれらは必ず空マスの位置を指します。
- マップの端(1行目、H行目、1列目、W列目)はすべて障害物マスです。
- 任意の空マスから、隣接する空マスのみを通って他の任意の空マスに行くことができます。
出力
出力は以下の形式で標準出力に出力してください。
movement
- 1 行目に ちょうどK 文字の文字列movementを出力してください。
- movementは犬の動作を表す文字列で、次のいずれかの文字からなります。
U- 現在のマスより1行小さいマスに移動します。
D- 現在のマスより1行大きいマスに移動します。
L- 現在のマスより1列小さいマスに移動します。
R- 現在のマスより1列大きいマスに移動します。
-- 移動しません。
ジェネレータとテスター
ジェネレータとテスターを次のリンクから提供しています。
テストケースの生成
テストケースの生成は以下のようにして行います。"ランダムに選ぶ"と表記してあるものは、一様分布に従いランダムに選んでいるものとします。
- H=W=50, K=2500とする。
- H\times Wの
#からなるマップを用意する。 - stepを、[HW, 1.5HW]の整数からランダムに選ぶ。
- 座標(H/2+1, W/2+1)と上下左右4方向からランダムに選んだ向きdirを初期状態として、step回次を行う。
- 現在の座標のセルを
.に変える。 - 確率1/3で、
dirに新しい向きをセットする。この向きは上下左右4方向からランダムに選ぶ。 dirの向きに移動する。- 現在の座標がマップの端(1行目、H行目、1列目、W列目)にある場合、座標(H/2+1, W/2+1)にワープする。
- 現在の座標のセルを
.となっているマスの中からランダムに(sr,sc)を選ぶ。- Nを、[0.1R, 0.8R]の整数からランダムに選ぶ。0.1R, 0.8Rは小数点以下を切り捨てる。Rは、
.となっているマスのうち(sr,sc)でないものの個数である。 .となっているマスのうち(sr,sc)でないものからランダムに、相異なるN個のマスを選ぶ。これのそれぞれをエサを配置するマスとする。- 各エサのF_iを、[0,10^5]の整数からランダムに選ぶ。
- 各エサのD_iを、[0,100]の整数からランダムに選ぶ。
入力例1
10 10 20 4 9 ########## ###.....## ##...##..# #...####.# #...###### #...###### #...###### #...###### #...###### ########## 2 3 9 10000 5 3 3 4 1
注意: この入力はテストケースとしての制約を満たしていません。
出力例1
ULRLULLLDLL-DDR-RRRR
開始時の位置をS, エサを1,2で表したときのマップは以下のようになります。最終的にXの位置に移動します。
########## ###.....## ##2..##.1# #...####S# #..X###### #...###### #...###### #...###### #...###### ##########
- 開始から0秒後にエサ1を獲得し、10秒後にエサ2を獲得します。
- 2秒後にエサ1の位置に戻ってきますが、エサ1は消滅しているので何も起こりません。
- 16秒後以降の移動は壁があるマスの方に向かっていますが、移動しない扱いになっています。
- この出力によって得られるスコアは、以下のように計算されます。
- 0秒後にエサ1を獲得したので、10000-5\times 0=10000だけ獲得。
- 10秒後にエサ2を獲得したので、4-1\times 10=-6だけ獲得。
- 合計で10000+(-6)=9994となり、これを10000で割って小数点以下を切り上げ、0との最大値をとって、1が最終的なスコアになります。
入力例2
50 50 2500 23 16 ################################################## ###......#########.#.###.##.###.################.# ########.#########.#.###.##.###.################.# ########.#.....###.#........###.################.# ########.##.##.###................##############.# ###...................##.######.#.##############.# ###########.###.#..#..##.######.#.##############.# ###########.#...#..#...............#############.# ###########.#.#...............#.....##...........# ###########.###.#.#.#..#......#....###.########### ###########.#####.#.##.#........#..###.########### ###########.####................#..###.########### ###########.####....#........#..#.........######## #########...............................########## ##.######.######...................###..########## #..######.#................#.#......##..########## #..######.#..#.#........................########## #.........................#..#......#...########## #..........#..............#..#......#...########## #..........#.....#......................########## #...#..#...#.................#......#...########## #..##..#.#.#........................#...########## #..........##.......................#....######### ##.#.#.#.#.#...................#....#.......###### ####.#.........................#....#...###.###### ####.....................................##.###### ####.........##.....#..........#..#.##...##.###### ####.......................#......#.#.......###### #.##......##.#....................#.#....######### #...................................#....######### #.##.##...##.##.#........................######### #.##.##...##.##.....................#....######### #.##..................#.............#...########## #....##....#........................#...########## #...................................#...########## #.......................................########## ##.#..##....###.##.#....................########## ####..##..#.###.##.#.##...#........#.#..########## ####..##..#.###.##.#.##...#.............########## ###.......#........#.##...#.#...####.#.########### ####..##..#####.####.##...#.#...#.........######## ####..##..#####.####.##...#.#...#.####.##.######## ####..##..#####.####......#.....#.###.....######## #####.###.#####.####..#.#.............###.######## #####.###.#####..###..####.##.#.#.#######.######## #####.###.#####..###..####.##.#.#.################ #.....###.####....##..####.#......################ #########..................##.......############## ####################.#..........#.################ ################################################## 128 36 6 33421 59 28 14 59990 74 21 15 91235 96 35 21 27683 71 20 11 11576 6 30 18 1583 87 6 4 21368 56 9 16 96637 100 26 11 21283 33 31 8 20294 33 2 21 65091 29 19 22 18039 17 5 33 98990 34 24 18 6500 60 14 10 26823 20 25 28 85792 28 47 18 537 36 26 23 60156 38 28 15 17810 17 20 39 28088 77 33 31 49621 37 20 32 83255 24 4 49 17499 96 31 9 93800 85 18 35 75782 37 24 25 61216 36 23 35 11322 33 6 5 84247 43 12 26 97308 40 6 6 7020 93 25 44 48412 4 6 15 30741 93 28 40 60392 6 23 28 50081 46 5 27 27989 38 23 32 91705 72 12 23 26710 59 28 17 36863 94 20 36 12665 77 17 12 69103 43 19 2 22817 20 18 38 27069 40 10 25 89918 76 32 28 7871 14 35 24 40156 17 32 16 50330 35 35 16 94626 5 17 33 2103 94 48 34 87848 82 19 21 52841 86 2 9 47976 39 46 17 10653 70 4 15 28399 40 5 30 85741 4 16 20 66310 36 13 27 79008 52 25 13 53822 71 8 18 96550 51 39 34 29271 54 38 24 92830 30 38 34 90137 86 48 18 82174 6 24 9 96186 3 7 18 21405 19 16 23 53528 2 31 31 8980 90 23 14 6256 21 49 24 57192 21 30 38 29651 33 16 24 80144 66 39 19 71496 10 26 38 22365 82 16 27 94591 4 30 19 13375 52 48 22 13906 29 45 21 15200 100 17 24 73814 1 5 15 89249 49 43 31 12710 19 16 21 89488 33 17 29 70865 55 33 20 71412 100 19 40 96591 32 8 30 6866 40 34 3 68501 20 24 28 99184 74 31 38 60999 70 8 22 88203 87 21 19 55945 64 14 18 46530 68 33 27 90347 100 44 31 40042 4 8 16 25939 91 44 28 17446 7 43 32 30346 61 22 2 16138 39 17 32 23668 8 20 29 3455 11 21 38 10036 59 14 19 80874 52 24 23 25439 55 29 8 7661 89 32 26 86161 51 22 27 18200 72 40 10 13922 31 8 23 58303 73 24 40 57936 38 27 11 14252 62 37 19 18676 93 17 21 46494 63 20 14 87223 9 39 39 9764 8 20 3 74043 69 47 16 76510 86 20 31 74695 46 29 26 78237 53 28 13 12037 81 38 19 65664 100 40 13 62357 39 27 13 95311 27 34 13 2537 69 46 6 94570 43 23 5 65255 8 2 25 93842 49 18 28 29560 48 12 24 60028 98 36 30 40774 28 24 42 57689 22
ジェネレータにseed=1を指定することで同様の入力が得られます。
出力例2
LDUDURRLDLRURDLURRU-DR--RRURDLRDRDRUULUDRRUDDD-DLLDRDLRD-R-UU-R--L-ULURDU-DULRL-RUDUUR-URUURUD-RDLLLRRDUURLDURLD-R-LDLURUULRULRLDUURLRDLDLUULLLU-DL-DLD-U-DLLURDR-RUD-URRUDLU-RUU-URUDL-DLLUDRUUURUU--RRL-DR-RDUUUULURDRU--UDLLRLDRU-DLLU-DDLLUD-RRDRLD-UDDRDDUUDLUR--D-L-RUUUDR--LL-LUURLUD--UDRDDL--UDL-RRR-L-LRUDUDD----D-DRDLU-UU-RRD-DL-RR-LDDR-UDRRRUU-DDR-U-L-UDUULRDRDLLUD--D--LRUU-UUULU-DDDDLDRUDLDRURUURLDRL-L-RRDRD-LL-D-LD--RDRLDULLLD-L-L-URRURLURL-L--DR--RD-LLULRUDRLLUDDRUUDD-URLRRRLUD-URLD-UDDUURLLUUR-LDULDRRDRD-LD-LRL-R-D-DLDRDD-LLLLDDDULL--LLDDLU--DU---LLDRUL--LDD-UL-L-ULUDUDDULD-R-LUR-LDDDRDL-LULLULLDUULU-DRRU--DDUUDLDRU-U--UUURDD-----URDLUDRDULU-L-U-D-LUUURRLUDD-R-UL-DUD-LLRRUULRU-D-R-L--RDRLLLRLDUDDLU--DULLD-LLLLDRUUURURRR-RDUDLUD--U-R-ULRLR-UL-U-RDDRRRRRLR-RURRUD--UUDRULDLRLURLD-R-RL-ULLL-DLRDD-U-DUR-L--DU-DLDR-RLRL-LLDLRDRU-LRLDDRD-U-L-RRD---ULD-RRDULLURL-RLDUR-DD-DLRDU---LUDRR-L-U-U--UD-UD--URUR--LUD-DUDR--URLD-DD---DU-RRUUUULLDUL-L-UUDUDDRURLRU-R-DR-DLUDRL--LRLDDL---DDULLUUUDLRUUDLRDUULDURRULURUL-DRDULDDR---U-URDRRUURLR-L-LDRLURR-R-UU-R-URDRD-U-RLLDD--L-RD-DRRRRU-L-LRR-UDLURLULRLRRDUDRL-RDLD-URRL-L-DURLU-UDDDLLLLLDUUU-ULUURRUR-UU-RDD--URL-UDDDDU-DULURUURD-DUL-LR--ULDLL-DLD--RULD-DUULRUDLD-DLDRL-DU--R-RRDDDRLRD-LDDRRR-R-RDDUULL-DRDUDLL-RDL--UUUUDLRR-L-RDRDRD-UDRUR--DLULURR-UD-LLRLRDL-LR-DUUUDLDD-ULURLRR--R--UDUDUDLDR-RUD-DRU-DDRLR--U-LLD-RDU-U-RRULDLUDRDUL-RDUULD-R--LRRRLULDD--UUU-D-RLDD-LLULL-L--R--LRDR-RRD-U-LUUURRRD--R-URRDU-RRRULURUR-RLULLL-UUUURLLDR--RLLDU-RRUL-DR-LURUDDURL-DRDR-R-UULDLR-RDURD---LLRUULLUDDRULLRRRRUURDDD-DLUDRURLLUDLLRL-DDR--L-URLRU--UR-LDRUURUDDU-DUD-UDDLL-RU-R-DDLDURLRUULULDURR-RRRDRUUDDRLRLLDDDULULRU--DRRLRRDL--ULLRRRLDUULULR-URULLLRDURR-LU-LURLUDLUURU-RU--D-DD-RD-LLRRU-RDUUR-RRDDRLDD---LLRRLL-LDDUUR-ULRUDRLRULDLDUDU-ULLLL--LRRUDDDDRLL-RDRUR-UULDDUL-L--DLLLDU-UDDULUR--D-LDDRDUU-L---RDRULRU-DDLRRLRU-URDRUURR-DD-RURULL-LLDL-DDRULLULL--LRURLUL--D-D-DDLUURUDUDURUL-DDDRLRDUU-RD-UU-URRL-RULDU-R--ULLRURRDRLLDLL-D-LUL-D-UULRU-DUUDLDULUL-DRRRRLRDRURDDRUU-RD--UDRUULLLL-L-RLDRRUD-ULRLURDD-LLDDLL--URLUUDULUDLUDR--DLDDLLLRRURLD-R--DR-U-U-LURUURDD-RRU--LDRLUUDLRUUUULRRRU-LULDD-UDULDLUU---D-LUUDRR-U-ULUU-LL-R-URLLD-RDRRUL-LLRU-R--DUDDU-R--RRULLUU-DRRLDLDDRUR--UD-R-DRDDL-LDRDLRRDUDUUDRDLU--D--RRD-DULR-R--ULUU-DRLUULLR-UD-LRL-LULRRDDU-LUDUDU-UR--R-RLLLULDD-L-URRDDDULDUU-RURUDLUUDUURDDDR-LRL--R-L-DU-DDD-DURDRRLDLLL-UULL-RLRRL--URUUL-RDR-RDLDDLDURRLDLDUUD-ULU-DR--RLR-LRDLRDDRLUL-RUR-U--URU-D-LD--RRURRRR-UDLU--LLRDDUDL---DUURRDUD-RUD-UURDLLD-RLD
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。