競技プログラミング用 知識集積所
ABC430F - Back and Forth Filling
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
考察問題。
「各マスに何種類の数を書き込めるか？」は、「各数字をどの位置なら書き込めるか？」を全数字について求めて、1をその範囲に加算することを繰り返せばよい。
では、まず、1をどこに書き込めるかを考える。
仮に、文字列の先頭にLがk文字並んでいたとする。（k+1番目はR、または終端）
このとき「2は1より左」「3は2より左」……「k+1はkより左」という関係が成り立つため、2からk+1までは1より左になくてはならない。
つまり、1を左からkマス目までに入れることはできない。
このとき「2は1より左」「3は2より左」……「k+1はkより左」という関係が成り立つため、2からk+1までは1より左になくてはならない。
つまり、1を左からkマス目までに入れることはできない。
しかし、k+1マス目に入れることはできる。
なぜなら、左から順にk+1から1まで順に書き込んだ後、k+2以上のn-(k+1)個を適当に条件を満たすように並べた列をk+2番目以降に書き込めばいいからである。
なぜなら、左から順にk+1から1まで順に書き込んだ後、k+2以上のn-(k+1)個を適当に条件を満たすように並べた列をk+2番目以降に書き込めばいいからである。
そして、k+2マス目からnマス目までに入れることもできる。
というのは、隣接するマスに差が2以上である数の組が入っていた場合、それら2つの入れ替えをしてもLRの条件に影響を与えないからである。
つまり、k+1マス目に入れた状態から、「1を右隣と交換」を必要なだけ繰り返すことができるからである。
というのは、隣接するマスに差が2以上である数の組が入っていた場合、それら2つの入れ替えをしてもLRの条件に影響を与えないからである。
つまり、k+1マス目に入れた状態から、「1を右隣と交換」を必要なだけ繰り返すことができるからである。
したがって、文字列の先頭にLがk文字並んでいた場合、1が置ける場所は左端のkマス以外全てとなる。
同様に、文字列の先頭にRがk文字並んでいた場合、1が置ける場所は右端のkマス以外全てとなる。
同様に、文字列の先頭にRがk文字並んでいた場合、1が置ける場所は右端のkマス以外全てとなる。
これは、どの数でもほぼ同じ理屈が成り立つ。
全ての数iに対して「そこから左に何個L/Rが連続しているか」「そこから右に何個L/Rが連続しているか」を両方求め、その範囲を優先的に端に固定すると、固定に使った範囲以外の好きな場所にiを置くことができる。
（左側にLが、右側にRが並んでいた場合、両方左に固定することになるが、固定に使う個数は単純な足し算でよい）
全ての数iに対して「そこから左に何個L/Rが連続しているか」「そこから右に何個L/Rが連続しているか」を両方求め、その範囲を優先的に端に固定すると、固定に使った範囲以外の好きな場所にiを置くことができる。
（左側にLが、右側にRが並んでいた場合、両方左に固定することになるが、固定に使う個数は単純な足し算でよい）
ということで、与えられた文字列の各合間から見て
- 左にLが何連続しているか
- 右にLが何連続しているか
- 左にRが何連続しているか
- 右にRが何連続しているか
