Time Limit: 2 sec / Memory Limit: 1024 MiB
ストーリー
高橋くんは、色とりどりのスライムたちを率いる王様である。 日が暮れてきたので、あちこちで遊んでいる仲間たちを、それぞれの色の巣へ帰すことにした。
スライムたちの得意技は、縦に重なり、下の仲間の弾力を借りて跳ぶ「宙返りジャンプ」だ。 王様が指示を出すと、塔の上の一団がくるんとひっくり返って飛んでいく。 巣に着くと、一番上から順に、巣と同じ色のスライムたちが帰っていく。
高橋くんも早く巣に帰って休みたい。 できるだけ少ない指示で仲間全員を巣へ帰せるよう、ジャンプの手順を考えてほしい。
問題文
N\times N マスの盤面がある。 左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 各マスは床または壁である。
盤面には 0,1,\ldots,K-1 の K 色のスライムがいる。 スライムは床の上で縦に重なって塔を作ることができる。 異なる色のスライムも同じ塔に重なることができ、融合することはない。 塔の高さはスライムの数であり、上限は8である。 スライムのいないマスの高さは0とする。
初期状態では各マスのスライムは高々1匹であり、巣のあるマスにはいない。 各色の巣が1か所ずつあり、スライムは自分と同じ色の巣へ帰ることを目指す。
次の操作「宙返りジャンプ」を最大 100000 回行える。 できるだけ少ない操作回数で、すべてのスライムを帰巣させよ。
宙返りジャンプ
高さ h>0 の塔があるマス (i,j) を選び、下に残す匹数 k、上下左右の方向 d、飛距離 \ell を指定する。 着地点の操作前の高さを g として、次の条件をすべて満たさなければならない。
- k,\ell は整数であり、0\leq k<h、1\leq\ell\leq k+1。
- (i,j) から d 方向へ1マス、2マス、…、\ell マス進んだ先がすべて盤面内の床である。 途中の塔は飛び越えてよい。
- g+(h-k)\leq8。 すなわち、着地後の塔の高さが8以下でなければならない。 帰巣によって高さが減る場合も、帰巣前の高さで判定する。
出発点の上側 h-k 匹が一団となって跳び、上下の順序を反転させて着地点の塔の上に重なる。 出発点に残る k 匹と、着地点にもともといたスライムの順序は変わらない。 その後、出発点と着地点の両方で、以下の帰巣を行う。
帰巣
色 i の巣があるマスでは、塔の一番上が色 i である限り、そのスライムを盤面から取り除くことを繰り返す。 これを帰巣と呼ぶ。 異なる色が現れたら、その下のスライムは帰巣しない。 巣のないマスでは何も起こらない。
帰巣したスライムは盤面に戻らない。 帰巣は自動的に行われ、操作回数には数えない。
帰巣の例
色0の巣に、下から (0,0,1) の順にスライムが重なっているとする。 k=2 として一番上の色1を3マス右にある、スライムのいない色1の巣へ跳ばすと、出発点の色0の2匹と着地点の色1の1匹が帰巣する。 ただし、途中のマスはすべて床とする。
得点
操作回数を T、操作終了時に盤面に残っているスライムの数を E とする。 絶対スコアは
\[ S=T+100000E \]
とする。
絶対スコアは小さければ小さいほど良い。
各テストケースごとに、\mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) の相対評価スコアが得られ、その和が提出の得点となる。
最終順位はコンテスト終了後に実施される、より多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは 0 点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは CE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。
テストケース数
- 暫定テスト: 50 個
- システムテスト: 2000 個、コンテスト終了後に seeds.txt (sha256=67cf8463e118af25951c5e583a5b41607e58143174ac6aa6ca8477285fa70323) を公開
相対評価システムについて
暫定テスト、システムテストともに、 CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケースごとの全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。
順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認できる各提出のスコアは各テストケースごとの絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出について、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認できるスコアは 0 となるが、順位表には正解したテストケースに対する相対スコアの和が表示される。
実行時間について
実行時間には多少のブレが生じる。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されている。 そのため、実行時間制限ギリギリの提出がシステムテストで TLE となる可能性がある。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせることを推奨する。
入力
入力は以下の形式で標準入力から与えられる。
N K
C_0
\vdots
C_{N-1}
- 12\leq N\leq20、4\leq K\leq12。
-
C_i は長さ N の文字列であり、j 文字目はマス (i,j) の初期状態を次のように表す。
#：壁.：スライムも巣もない床a〜l：色0〜11のスライムが1匹いる床A〜L：色0〜11の巣がある床
-
床は少なくとも 2K マスあり、上下左右の隣接関係について連結である。
- 英字は大文字・小文字ともに先頭の K 種類のみが使われ、各大文字はちょうど1回、各小文字は1回以上現れる。
出力
以下の形式で標準出力に出力せよ。
t 回目の操作の出発点 (i_t,j_t)、残す匹数 k_t、方向 d_t、飛距離 l_t を、1行に1操作ずつ計 T 行出力せよ。
i_0 j_0 k_0 d_0 l_0
\vdots
i_{T-1} j_{T-1} k_{T-1} d_{T-1} l_{T-1}
d_t は上・下・左・右に対応する U、D、L、R の1文字である。
入力生成方法
seed=0 の入力は手動で作成されたものであり、暫定テスト、システムテストには含まれない。 それ以外の入力は以下の方法で生成する。
生成パラメータ
N を 12 以上 20 以下、K を 4 以上 12 以下の整数から、それぞれ独立に一様ランダムに生成する。
スライムの密度 \rho を区間 [0.12,0.65)、壁の提案率 \beta を区間 [0,0.40) から、それぞれ独立に一様ランダムに生成する。
地形
最初は全マスを床とする。 全マスを一様ランダムな順番に並べる。
並べた順に各マスについて、独立に確率 \beta で壁への変更を試みる。 変更後も床が少なくとも 2K マス残り、床が連結である場合に限って壁へ変更する。
巣と初期位置
床から異なる K マスを一様ランダムに選び、選んだ順に色 0,\ldots,K-1 の巣を置く。
巣のない床の数を F とし、スライムの総数を M=\max(K,\mathrm{round}(\rho F)) とする。 巣のない床から異なる M マスを一様ランダムに選び、それぞれにスライムを1匹置く。
色の割り当て
整数区間 [0,M-K] から、K-1 個の整数をそれぞれ独立に一様ランダムに選ぶ。 同じ値を複数回選んでもよい。 選んだ値を昇順に並べて s_1,\ldots,s_{K-1} とし、s_0=0、s_K=M-K とする。 各色 i=0,\ldots,K-1 のスライムの数を
\[ b_i=s_{i+1}-s_i+1 \]
とする。
各色 i を b_i 個ずつ用意し、全 M 個の色を一様ランダムに並び替え、初期位置のスライムへ割り当てる。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示と手動プレイが可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
コンパイルが通らない場合は
rustup updateをお試し下さい。- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中は、seed=0 の入力に対するビジュアライザの出力画像・動画と点数のみ、X で共有できます。 ハッシュタグ #AHC072 と #visualizer を付け、公開アカウントを使用して下さい。 出力文字列、他の入力に対するビジュアライズ結果や点数の共有、および解法・考察に関する言及は禁止されています。
生成AIの利用に関して
現行の AtCoder Heuristic Contest 生成AI利用ルール－20250616版 では、AIエージェントに解答プログラムを実行させ、その実行結果に基づく改善を自動的に繰り返させることを禁止しています。
一方、最新の生成AIでは、ChatGPTのような対話型サービスと、CodexのようなAIエージェントとの区別が曖昧になっています。 対話型サービスであっても、利用者が明示的に指示していない場合に、内部でテストケースの生成、解答プログラムの実行、および実行結果に基づく改善を 自動的に繰り返すことがあります。
一部の参加者は、このような挙動を防ぐため、生成AIに対して禁止事項を明示しています。参加者間の公平性を確保し、現行ルールの趣旨を徹底するため、本コンテストで生成AIを利用する場合は、以下の指示文を各チャットの冒頭に入力するか、各生成AIツールが提供するカスタム指示、プロジェクト指示、または自動的に読み込む指示ファイル （例：AGENTS.md、CLAUDE.mdなど）に設定しなければなりません。
I am currently participating in an AtCoder Heuristic Contest, and I will use this generative AI to assist in developing my solution. When using this generative AI, the "AtCoder Heuristic Contest Generative AI Usage Rules - Version 20250616" apply. https://info.atcoder.jp/entry/ahc-llm-rules-en Most importantly, after running the solution program, you must not modify or improve the solution, its approach, or its code based on the execution results unless the user gives a new explicit instruction to do so. You may run the solution program and report its execution results, logs, scores, or other observations. After reporting them, you must stop and wait for a new instruction from the user before making any improvement based on those results. Here, "solution program" refers to any program created or being created for the purpose of solving this contest problem, regardless of whether it was created by the user or by generative AI, and regardless of whether it is still in progress or already complete.
Story
Takahashi is the king of a colorful kingdom of slimes. As dusk approaches, he decides to send his companions, who have been playing here and there, back to their nests of matching colors.
The slimes have a special skill: the "somersault jump." They stack into towers and use the springiness of the slimes below them to jump. At their king's command, the upper part of a tower flips over and flies through the air. Upon landing on a nest, slimes of the matching color return home, starting from the top.
Takahashi would also like to return to his nest and rest. Help him find a sequence of jumps that sends all his companions home with as few commands as possible.
Problem Statement
There is an N\times N grid. Let (0,0) be the coordinates of the top-left cell, and let (i,j) be the coordinates of the cell located i cells downward and j cells to the right from there. Each cell is either floor or a wall.
The grid contains slimes of K colors, numbered 0,1,\ldots,K-1. Slimes can stack vertically on floor cells to form towers. Slimes of different colors can share a tower, and they do not merge. The height of a tower is the number of slimes in it, with a maximum of 8. A cell with no slimes has height 0.
Initially, each cell contains at most one slime, and no slime is on a nest. There is one nest of each color, and each slime aims to return to the nest of its own color.
You can perform the following operation, called a "somersault jump," at most 100000 times. Send all slimes home using as few operations as possible.
Somersault Jump
Choose a cell (i,j) containing a tower of height h>0, and specify the number k of slimes to leave behind, a direction d (up, down, left, or right), and a jump distance \ell. Let g be the height at the destination before the operation. All of the following conditions must hold.
- k,\ell are integers, 0\leq k<h, and 1\leq\ell\leq k+1.
- The cells located 1, 2, ..., \ell cells from (i,j) in direction d are all floor cells within the grid. The jump may pass over intermediate towers.
- g+(h-k)\leq8. In other words, the tower height after landing must be at most 8. This is checked before any slimes return home, even if doing so reduces the height.
The top h-k slimes at the starting cell jump together, reverse their vertical order, and land on top of the tower at the destination. The order of the k slimes left behind and that of the slimes originally at the destination remain unchanged. Then, the following return-home process takes place at both the starting cell and the destination.
Returning Home
At a cell with a nest of color i, repeatedly remove the top slime from the grid as long as it has color i. This is called returning home. If a different color is encountered, the slimes below it do not return home. Nothing happens at cells without a nest.
Slimes that have returned home never reappear on the grid. Returning home happens automatically and does not count as an operation.
Example of Returning Home
Suppose slimes are stacked in the order (0,0,1) from bottom to top on the nest of color 0. With k=2, the top slime of color 1 jumps three cells to the right onto the nest of color 1, which has no slimes on it. The two slimes of color 0 at the starting cell and the slime of color 1 at the destination then return home. Assume that all intermediate cells are floor cells.
Scoring
Let T be the number of operations and E be the number of slimes remaining on the grid after all operations. Your absolute score is
\[ S=T+100000E \]
The lower the absolute score, the better.
For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.
The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases. The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.
Number of test cases
- Provisional test: 50
- System test: 2000. We will publish seeds.txt (sha256=67cf8463e118af25951c5e583a5b41607e58143174ac6aa6ca8477285fa70323) after the contest is over.
About relative evaluation system
In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE . Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.
The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.
About execution time
Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.
Input
Input is given from Standard Input in the following format.
N K
C_0
\vdots
C_{N-1}
- 12\leq N\leq20, 4\leq K\leq12.
-
C_i is a string of length N. Its j-th character represents the initial state of cell (i,j) as follows.
#: a wall.: a floor cell with neither a slime nor a nesta–l: a floor cell with one slime of color 0–11, respectivelyA–L: a floor cell with a nest of color 0–11, respectively
-
There are at least 2K floor cells, and they are connected by vertical and horizontal adjacency.
- Only the first K uppercase and lowercase letters are used. Each uppercase letter appears exactly once, and each lowercase letter appears at least once.
Output
Output to Standard Output in the following format.
For the t-th operation, output the starting cell (i_t,j_t), the number k_t of slimes to leave behind, the direction d_t, and the jump distance l_t, with one operation per line for a total of T lines.
i_0 j_0 k_0 d_0 l_0
\vdots
i_{T-1} j_{T-1} k_{T-1} d_{T-1} l_{T-1}
d_t is one of the characters U, D, L, and R, corresponding to up, down, left, and right, respectively.
Input Generation
The input for seed=0 is created manually and is not included in the provisional or system tests. All other inputs are generated as follows.
Generation Parameters
Generate N and K independently and uniformly at random from the integers between 12 and 20 inclusive and between 4 and 12 inclusive, respectively.
Generate the slime density \rho and the wall proposal probability \beta independently and uniformly at random from [0.12,0.65) and [0,0.40), respectively.
Terrain
Initially, all cells are floor cells. Arrange all cells in a uniformly random order.
In that order, independently attempt to turn each cell into a wall with probability \beta. Make the change only if at least 2K floor cells remain and the floor cells remain connected.
Nests and Initial Positions
Choose K distinct floor cells uniformly at random, and place the nests of colors 0,\ldots,K-1 in the order chosen.
Let F be the number of floor cells without a nest, and let the total number of slimes be M=\max(K,\mathrm{round}(\rho F)). Choose M distinct floor cells without a nest uniformly at random, and place one slime on each.
Assigning Colors
Independently choose K-1 integers uniformly at random from the integer interval [0,M-K]. The same value may be chosen more than once. Sort the chosen values in ascending order as s_1,\ldots,s_{K-1}, and set s_0=0 and s_K=M-K. For each color i=0,\ldots,K-1, the number of slimes is
\[ b_i=s_{i+1}-s_i+1 \]
Prepare b_i copies of each color i, uniformly shuffle all M colors, and assign them to the slimes at the initial positions.
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations and manual play.
- Local version: You need a compilation environment of Rust language.
If it does not compile, please try
rustup update.- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
During the contest, you may share only images or videos produced by the visualizer for the seed=0 input and the corresponding scores on X. Use the hashtags #AHC072 and #visualizer and a public account. Sharing output text, visualization results or scores for other inputs, or discussing solutions or ideas is prohibited.
Use of Generative AI
Under the current AtCoder Heuristic Contest Generative AI Usage Rules — Version 20250616, it is prohibited to have an AI agent execute a solution program and automatically repeat improvements based on the execution results.
However, with the latest generative AI systems, the distinction between conversational services such as ChatGPT and AI agents such as Codex has become increasingly blurred. Even conversational services may, without an explicit instruction from the user, internally generate test cases, execute a solution program, and automatically repeat improvements based on the execution results.
Some participants already explicitly instruct generative AI systems not to engage in such behavior. To ensure fairness among participants and to enforce the intent of the current rules, anyone using generative AI in this contest must provide the instruction below either at the beginning of each chat or through a custom instruction, project instruction, or instruction file automatically loaded by the relevant generative AI tool, such as AGENTS.md or CLAUDE.md.
I am currently participating in an AtCoder Heuristic Contest, and I will use this generative AI to assist in developing my solution. When using this generative AI, the "AtCoder Heuristic Contest Generative AI Usage Rules - Version 20250616" apply. https://info.atcoder.jp/entry/ahc-llm-rules-en Most importantly, after running the solution program, you must not modify or improve the solution, its approach, or its code based on the execution results unless the user gives a new explicit instruction to do so. You may run the solution program and report its execution results, logs, scores, or other observations. After reporting them, you must stop and wait for a new instruction from the user before making any improvement based on those results. Here, "solution program" refers to any program created or being created for the purpose of solving this contest problem, regardless of whether it was created by the user or by generative AI, and regardless of whether it is still in progress or already complete.
Time Limit: 0 msec / Memory Limit: 1024 MiB