pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TCO 2016 Round 1C Medium. ThreeProgrammers

問題概要

A,B,C で構成された文字列が与えられる。B 同士の距離が 2 以上、C 同士の距離が 3 以上になるように文字列を並び替えよ。

解法

「A の残り数」、「B の残り数」、「C の残り数」、「あと何ターン B が使えないか」、「あと何ターン C が使えないか」という状態を使って左から並べる DFS をする。状態数 50*50*50*2*3 、遷移は O(1) 通りなので十分間に合う。

TCO 2016 Round 1C Medium. ThreeProgrammers

意外と貪欲が難しいので、何も考えずに探索を掛けた方が良さそう。