未証明です。
問題リンク
問題概要
3つの非負整数A,B,CとN個の文字列(AB,AC,BCのいずれか)が与えられる。
\(1\leqq i \leqqN\)に対し、i番目の文字列がABならば「Aに1足しBから1引く」「Bに1足しAから1引く」のいずれかを選ぶ(AC,BCについても同様)。
途中でA,B,Cのいずれかが負になってはいけない。
そのような手順が存在するならばYesと出力して手順を1つ示せ。
存在しなければNoを出力せよ。
解法
相当厳しい条件でないとNoにはならなさそうなので、実際にシミュレーションした。
「A,B,Cのうち2つ以上が正」の状態を常に保ち続ければ、手順が存在する。
なので、できるだけ数のバランスを保つようにする。
i番目の文字列がABの時は
- A=B=0ならばNoを出力して終了
- i+1番目がAC、かつA=1かつC=0ならばAに1足す
- i+1番目がBC、かつB=1かつC=0ならばBに1足す
- それ以外の場合は小さい方に1足す
とした。
提出
https://atcoder.jp/contests/abc166/submissions/12745093
感想
Dに続きビクビクしながら提出した。
