Xmas Contest 2018 H: Hello, Xmas Contest 2018 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_h

問題概要

文字列 $S, T$ が与えられる．グリッドの一部に A-Z または * を書いて，

各行の最初の非空白文字を順に繋げて * を除いた文字列が $S$
各列の最初の非空白文字を順に繋げて * を除いた文字列が $T$

となるようにする．最低何文字書く必要があるか？ (入出力例の図を見るのがわかりやすいです)

解法

ある文字 $c$ が $S$ に $a$ 回， $T$ に $b$ 回現れたとすると，文字 $c$ は少なくとも $\max\{ a, b \}$ 個書かなければいけません．これを A-Z について足すことで答えの下界が得られます．

この下界はだいたい達成できそうな気がします：

 |AAACCB
-+------
A|A.....
A|.AA...
B|.....B
C|...CC.
B|......

具体的には， $S$ と $T$ の両方に現れる文字は問題なく配置できます．片方にしか現れない文字がある場合は，

 |UNAGI
-+-----
U|UN...
S|S....
A|..A..
G|...G.
I|....I

 |BAD
-+---
A|.AD
B|B..
C|C..

のように $1$ 行目の文字や $1$ 列目の文字で隠してしまえばよいです．隠せないのは，

 |AC
-+--
W|..
A|AC

のように $1$ 行目の文字が $T$ に現れない場合，あるいは $1$ 列目の文字が $S$ に現れない場合，のみです．そのような場合は * を $1$ 個以上書く必要があり，逆に * を $1$ 個左上に書いてしまえば隠したい文字を隠せます (看板を作ることが不可能なケースはありません)．

まとめると，