Codeforces Round #414 C - Naming Company
2者がそれぞれn文字の集合を持っていて、さらに????で埋まったn文字のマスがある。両者が互いに?を自分の文字を使って埋めていく。先行は辞書順最小、後攻は辞書順最大になるように最適な戦略を取る時最終的にできる文字列を答えよ。
先行を昇順ソート、後攻を降順ソートすると、それぞれ(n+1)/2, n/2文字目までしか使わない。これらをとりあえずキューに入れる。先頭の文字が先行<後攻を満たす間は貪欲にマスの先頭を自分の文字列の先頭の文字で埋めていく。
その後ある時点で、先頭の文字が 先行＞=後攻 となる。この時点から、自分の持っている一番悪い文字(先行なら辞書順最大、後攻なら辞書順最小)を一番影響の少ないところ、つまり一番うしろから詰めていく。O(N)。
これできないのはちょっと頂けなかった。多分典型問。
