Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

Codeforces Round #604 (Div. 2)-A Beautiful String

codeforces.com

概要

t個の文字列が与えられる。それぞれの文字列は'a', 'b', 'c', '?'で構成されてる。各文字列に対して、'?'は'a' or 'b' or 'c'にすることができる。それぞれの文字列の’?’をうまく差し替えた時、同じ文字が隣り合わないような文字列の差し替え方あるか?

制約: 1 <= t <= 10^3 テストケース内での文字列の長さは10^5以下。

ACするまで

1. 早く解いて寝るぞー^^。
2. '?'の左右は多くても二通りなので、'?'は作る上で障害ではない。一方最初から隣り合わせてるもの以外は、全部作れそう。
3. 実装方針に苦しむ。そして寝た。


4. '?'を作る上では障害とはならない理由は、どのような状況でも'?'に代わる文字が存在するということ。これは前から貪欲に'?'の中身を決めても必ず'?'は埋まるということでもあるので、これで実装する。->AC

考察

おおむねACするまでのとおりである。
この問題では、'?'は3通りに変えられるが、左右はたかだか2通りしか存在しないので、どのような場合でも'?'は適切に埋められる

このように、どのような場合でもできる構築は、前から見るとかの楽な貪欲などで順に決定していけばうまくいくことが多い。

今回の場合は、事前に'?'以外の隣と同じ文字が既に存在してるのならばかならず作れない。それがない場合、'?'を前から順に決定するという楽な方法をとっても、必ず'?'が作れることから前から順に決定すればよい。
実装する際には、上から順に、

  • '?' -> 'a'でOKか?
  • '?' -> 'b'でOKか?
  • '?' -> 'c'でOKか?

の条件分岐すれば、かならずどれかはOKになる。

一言

こういう問題を絶対に素早く解けるようにするためにコドフォ精進を重ねる。