ARC 101-200/ARC197A - Union of Grid Paths - 競技プログラミング用 知識集積所

---

問題

ARC197A

必要知識

簡単な内容は省略

考え方

入力例1の1つ目を以下のように考える。

0	1	2	3	4
1	2	3	4	5
2	3	4	5	6
3	4	5	6	7

と番号付けして、番号ごとに1+1+2+2+2+2+1+1=12と求める。

この足し算を、Sの中身と並べてみる。

1+1+2+2+2+2+1+1=12
  D ? D R R ? R

つまり、各項は1スタートで、途中までは?が出てくるたびに増加し、後半は?が出てくるたびに減少する。
その境界は「そこより前の?を全部Dにしたり全部Rにしたりできない」「そこより後の?を全部Dにしたり全部Rにしたりできない」ところまで。
したがって、それまでの?の個数を数えながら、?にDを入れられる個数やRを入れられる個数と比較しながら総和を取ればいい。

具体的には、最初に1を加算しておき、その後Sを前から見て

• それまでの?の個数+1
• H - Dの個数
• W - Rの個数
• H+W-1 - Dの個数 - Rの個数 - それまでの?の個数

のうちの最小値を加算していけばよい。

解答例

解答例

注意点

解答はlong long型で。

全部?だった場合、全部黒で塗れる。
ということは、解答は最大でH×Wになり、int型に収まらない可能性がある。

別解