perogram

【数え上げ】L, Rのマッチング。Lを溜め込んで歩いてRとぶつかったら

f:id:peroon:20190825022212p:plain

  • https://youtu.be/JTH27weC38k?t=2936 この辺の話題
  • LとRをペアにする方法は何通りあるか?
  • これは左から人間が右に歩いていき、Lがあれば溜め込み、Rとぶつかったら溜め込んだLのどれかとマッチングさせてLを1減らすことを繰り返せばいい
  • 具体的に数えてみる(下記)

f:id:peroon:20190825023240p:plain

  • 左端のLに対し、Rは3パターンあり、どれを選んでも破綻しない
  • 選んだ後に他のペアも作ることを考えると、中・右の場合はペアが強制的に1通りとなる
  • そういう場合の数え上げが、「Lを溜め込んで歩いてRとぶつかったら~」である
  • これは https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c の解法で必要となる知識の一部なのだが、知らなかったので覚えておこう