のグリッドの各マスには、人が住んでいるか、住んでいないかのいずれかです。行には上から順に 、列には左から順に の番号が付けられています。格子点の座標を と表し、、 です。
から まで、グリッドの辺に沿って移動する経路を一つ出力してください。1 回の移動では、上下左右に隣接する格子点へ移動できます。グリッドの外へ出ることはできません。
人が住んでいる各マスについて、そのマスを構成する四つの頂点のうち一つ以上を経路が訪れた場合、そのマスでコスト が発生します。同じマスの頂点を複数回訪れても、そのマスのコストは一度しか数えません。経路のコストは、コストが発生したマスの個数です。
具体的な得点の計算方法については、Scoring セクションを参照してください。
入力は次の形式で与えられます。
各テストケースについて、次の 2 行を出力してください。
は長さ の文字列であり、各文字は U, D, L, R のいずれかです。それぞれ、現在の格子点から上、下、左、右に隣接する格子点へ移動することを表します。
が表す移動は から始まり、常にグリッド内になければならず、最後には に到達しなければなりません。
この問題の採点はサブタスクごとに独立して行われ、以下の近似比に関する基準はすべてのサブタスクに同様に適用されます。
各テストケースの最適コストを 、参加者が出力した有効な経路の実際のコストを とします。近似比 を次のように定義します。
一つ目のテストケースには人が住んでいるマスがないため、出力された経路のコストは です。
二つ目のテストケースでは左側のマスに人が住んでおり、始点 がそのマスの頂点であるため、どのような経路を選んでもコストは少なくとも になります。出力例の経路のコストは です。
三つ目のテストケースでは人が住んでいるマスが存在しますが、出力された経路はそのマスのどの頂点も訪れません。したがって、経路のコストは です。
各テストケースは次の形式で与えられます。
各 は長さ の文字列であり、各文字は 0 または 1 です。
、 であるマス について、 の 番目の文字が 1 ならばそのマスには人が住んでおり、0 ならば人は住んでいません。
は、出力した経路の実際のコストと正確に一致しなければなりません。また、次の条件を満たさなければなりません。
0 または 1 です。各サブタスクに含まれるすべてのテストケースの の最大値を、そのサブタスクの とします。以下の条件のうち、満たしている最も高い得点率に応じて、そのサブタスクの得点を獲得します。
条件 | 得点率 |
|---|---|
すべてのテストケースで | |
その他 |
最後の条件における 、、 は、それぞれ同一のテストケースに対する値です。最終得点は、四つのサブタスクで獲得した得点の合計です。
出力した経路が有効でない場合、または同時に出力したコストが実際の経路のコストと異なる場合、その提出の得点は 点です。
| 3 | 15 | 追加制約:各テストケースで です。 |
| 4 | 65 | 追加制約:各テストケースで です。 |
四つ目のテストケースでは、最適コストが であり、出力された経路のコストは です。したがって、このテストケースの近似比は
です。
入力例に含まれるすべてのテストケースの近似比が 以下であるため、この出力例はすべてのサブタスクで最高得点率の条件を満たします。