A45 - Card Elimination

入出力

1
2
3
let N,C = stdin.ReadLine().Split() |> fun x -> int x.[0], char x.[1]
let S = stdin.ReadLine()
solve N C S |> stdout.WriteLine

方針

文字列間の距離をL^1距離(マンハッタン距離)で表して考えます. 特に(R,B,W)で原点からの距離を表すと, 初期値は原点からの距離がNで, そこからL^1距離を1ずつ減らして目標地点((1,0,0),(0,1,0),(0,0,1)のどれか)に到達できるかが問題です.

次に文字の変換を距離で解釈します. 名前があると便利なため, それぞれの変換に番号をつけます.

  1. WW - W: W-1移動
  2. WR - R: W-1移動
  3. WB - B: W-1移動
  4. RR - B: R-2,B+1移動
  5. BB - W: B-2,W+1移動
  6. RB - W: 立方体の対角線上の移動でR-1, B-1, W+1

いずれにせよステップごとに原点からのL^1距離は1ずつ減ります. ある時点での距離Lを別に記録して状態を(R,B)だけで考えると, 注目すべきは上記の2,3,6です. 特に直線R-B=k上で考えると, 6は直線上の移動で, 2,3 はk ± 3移動します. 三つつのゴールはそれぞれk=1,-1,0にあたるため, 初期位置からkを±3して目標に位置合わせできるなら"Yes"です. 特に(R-B)%3の値がそれぞれ1,2,0のどれになるかが問題です.

解説

アルゴリズムさえ考えられれば, あとは各文字を数値に変換して計算すれば終わりです.

1
2
3
4
5
6
7
let solve N C S =
  let f c = match c with | 'W' -> 0 | 'R' -> 1 | _ -> 2
  S |> Seq.sumBy f |> fun n -> if n%3 = f C then "Yes" else "No"

let N,C = stdin.ReadLine().Split() |> fun x -> int x.[0], char x.[1]
let S = stdin.ReadLine()
solve N C S |> stdout.WriteLine