B - Faucets and Drains Editorial
by
Mitsubachi
Editorial for printing
蛇口 $i$ が詰まっているならば,$S_i$ はすべて x からなり,これら以外は o となります.同様に,排水管 $j$ が詰まっているならば,$S_1, S_2, \cdots, S_N$ の $j$ 文字目はすべて x からなり,これら以外は o となります.
答えが一意に定まるとあるので,まず,x のみからなるような $S_i$ があるかを調べます.方法は色々ありますが,例えば,$S_i$ が o を含まないかを $i$ ごとに調べれば良いです.そのような $S_i$ があれば,答えは Faucet $i$ です.
そのような $S_i$ がない場合,$S_1$ はちょうど $1$ つの x を含むことになります.その場所が $j$ 番目ならば,答えは Drain $j$ となります.
実装の際は,文字列の index は基本的に 0-indexed ですが,入力の番号は 1-indexed であることに注意されると良いかと思います.計算量は \(O(NM)\) です.
posted:
last update:
