F - Gather Coins

Contest Duration: 2024-08-31(Sat) 12:00 - 2024-08-31(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Gather Coins Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。このグリッドの上から $i$ 行目、左から $j$ 列目にあるマスのことを $(i,j)$ と表記します。

このグリッド上には $N$ 枚のコインが落ちており、 $i$ 個目のコインはマス $(R_i,C_i)$ を通ることで拾うことができます。

あなたの目標は、マス $(1,1)$ から始めて下か右に $1$ マス移動することを繰り返し、できるだけ多くのコインを拾いながらマス $(H,W)$ まで行くことです。

あなたが拾うことのできるコインの枚数の最大値、およびそれを達成するための移動経路を $1$ つ求めてください。

制約

$2\leq H,W \leq 2\times 10^5$
$1\leq N \leq \min(HW-2, 2\times 10^5)$
$1\leq R_i \leq H$
$1\leq C_i \leq W$
$(R_i,C_i)\neq (1,1)$
$(R_i,C_i)\neq (H,W)$
$(R_i,C_i)$ は互いに相異なる
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $H$   $W$   $N$ 
 $R_1$   $C_1$ 
 $R_2$   $C_2$ 
 $\vdots$ 
 $R_N$   $C_N$

出力

$2$ 行出力せよ。 $1$ 行目には、あなたが拾うことのできるコインの枚数の最大値を出力せよ。 $2$ 行目には、それを達成するための移動経路の $1$ つを長さ $H+W-2$ の文字列として出力せよ。ここで、出力する文字列の $i$ 文字目は、 $i$ 回目の移動において下に移動するならば D、右に移動するならば R である。

拾うコインの枚数が最大となるような移動経路が複数存在する場合は、そのどれを出力しても良い。

入力例 1Copy

Copy

出力例 1Copy

Copy

3
DRRDR

上図のように $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$ と移動することで、 $(2,1),(2,3),(3,3)$ にある $3$ 枚のコインを拾うことができます。

入力例 2Copy

Copy

2 2 2
2 1
1 2

出力例 2Copy

Copy

1
DR

RD という移動経路も正解となります。

入力例 3Copy

Copy

出力例 3Copy

Copy

5
DRRRRRRRRDDDDDRRDRDDRRR

Score : $500$ points

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the cell at the $i$ -th row from the top and $j$ -th column from the left.

There are $N$ coins on this grid, and the $i$ -th coin can be picked up by passing through the cell $(R_i,C_i)$ .

Your goal is to start from cell $(1,1)$ , repeatedly move either down or right by one cell, and reach cell $(H,W)$ while picking up as many coins as possible.

Find the maximum number of coins you can pick up and one of the paths that achieves this maximum.

Constraints

$2\leq H,W \leq 2\times 10^5$
$1\leq N \leq \min(HW-2, 2\times 10^5)$
$1\leq R_i \leq H$
$1\leq C_i \leq W$
$(R_i,C_i)\neq (1,1)$
$(R_i,C_i)\neq (H,W)$
$(R_i,C_i)$ are pairwise distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $H$   $W$   $N$ 
 $R_1$   $C_1$ 
 $R_2$   $C_2$ 
 $\vdots$ 
 $R_N$   $C_N$

Output

Print two lines. The first line should contain the maximum number of coins you can pick up. The second line should contain one of the paths that achieves this maximum as a string of length $H+W-2$ . The $i$ -th character of this string should be D if the $i$ -th move is downward, and R if it is rightward.

If there are multiple paths that maximize the number of coins picked up, you may print any of them.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

3
DRRDR

As shown in the figure above, by moving $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$ , you can pick up three coins at $(2,1),(2,3),(3,3)$ .

Sample Input 2Copy

Copy

2 2 2
2 1
1 2

Sample Output 2Copy

Copy

1
DR

The path RD is also acceptable.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

5
DRRRRRRRRDDDDDRRDRDDRRR