1600点。制約のある順序列が複数あるかと思ったら1つ。考察大切。
競技プログラミングを初めて半年くらいの頃、闇のような実装で解いたことがあるのですが、今だときれいに考察できるし実装できるよねという話。
https://qiita.com/recuraki/items/8a449b4fabdf8175c3c0
通ったのですが、あまりに実装がひどいです。アプローチを間違えている気がします。
@自分 アプローチ間違えている気がするなら(解説見て)upsolveしよう！
題意
- ある1列に並んだキーボードを作りたい。それぞれの小文字英語が1文字ずつ必ず含まれる。(つまり26キーのキーボードを作りたい
- 同時にある文字列を１つ考える。キーボードを使って、この文字列を１つ横のキーに移動するだけで打ち込みたい。
- YES or NOを判定し、YESの場合、１つキーボードを作れ。
例
- ababa ⇒ YES。aとbが隣り合っていればいいので、例えば、abcd...でもいいし、cdef...ab...xyzなどでもいい
- axay ⇒ YES。aの隣にxとyがあればいいので、xay...やyax...でもいいし、bcd...xya...opsなどでもいい
- axayaz ⇒ NO。 aのとなりにx,y,zがないといけない。1列では3文字を置くことはできないのでNO。
こう考えた
まず、順序が必要な文字とどこにあってもよい文字があります。後者は1度も出現しない文字です。
前者は例えば上の例の２つ目でいえば、"xay"か"yax"という文字列は満たさなければならない文字列で、これをいかに構築するかが問題になりそうです。
最初、この問題を見たとき、前者の文字列がいくつかあるように見えました。例えば、"xay" と "owp"のような順序が必要な文字列が出てきて、"xay..(ほかの文字列)..owp..."のように構築する例です。ですが、順序が必要な文字列は１つしかできません。すべての文字は隣り合っているので、(後述の)ある隣接関係のグラフのノードになるからです。(例えば、上の場合、"xay" と "owp"に分かれることはなくて、"xayowp"などに入力的に制約されることになります)
※もしも、入力が「別にスペースキーがあることとする」などだと状況が変わってきます
各文字をノードとしたグラフで考えます。こうすると以下のようになります。各パターンごとに上がグラフ、下が入力とします。各隣接する文字を見ていき、辺が張られていなければ辺を張ると上のグラフのようになります。多重辺や自己ループ辺がないようにします。（尚、今回の場合は自己ループ辺がない入力です）
下で具体的な例を見ていきますが、各次数ごとに考えます。
次数0: 1度も出現していない文字です。制約には一切かかわらないのでどこにあってもよいです。
次数1: このノードからたどった文字列は制約を満たす文字列になります。結果（キーボード）の端に持ってきても酔いです。持ってこなくてもよいです。このノードはグラフに2つしか現れません。
次数2: ほかの文字に挟まれている文字列です。この文字列は結果(キーボード)の端に来ることはありません。
次数3以上: あってはいけません。これはある文字の隣(=2か所)に3文字が存在できないことから明らかです。つまり、このノードがあった場合NOです。
さて、それでは、次数3のノードがなければ必ずYESでしょうか？以下で例を見ていきます。
1は成功する例です。dとeが次数1のノードなので、どちらからだどると"dcae"か"eacd"を作れます。bはどこにあってもよいです。
2は失敗する例で、次数1のノードがない例です。入力を見ると、a, c, e、それぞれ互いが隣接することを要求します。例えば、a->c->e->aと打てないとなりませんが不可能です(キーボードが円であれば実現できますが今回は直線です)
3も失敗する例で次数3のノードがある例です。aはbとcとdを隣接関係が必要ですが、すべてを同時に満たす文字列は作れません。
実装
e[アルファベットの順番]を辺にしたグラフとしました。まず、辺を張り、0-25(各アルファベット)をループします。次数3が見つかればNOなので打ち切ります。次数0はどこに来てもいいので結果に積みます。次数2はいったん無視します。次数1のノードから参照されるはずだからです。次数1の場合、次の次数1が来るまで探索していきます。
この結果、26文字が含まれていなければNOです。26文字が含まれない場合とは、上記例の3のパターンで、次数1の入り口(制約の端に来てもよい文字列)ないので、結果に追加されることはありません。
計算量は$O(N)$です。
def do():
s = input()
e = [[] for _ in range(26)]
for i in range(len(s) - 1):
a = ord(s[i]) - ord("a")
b = ord(s[i+1]) - ord("a")
if a not in e[b]:
e[b].append(a)
if b not in e[a]:
e[a].append(b)
res = ""
used = [False] * 26
for i in range(26):
if used[i]:
continue
if len(e[i]) == 0:
used[i] = True
res += chr(ord("a") + i)
continue
if len(e[i]) == 2:
continue
if len(e[i]) > 2:
print("NO")
return
# 1
res += chr(ord("a") + i)
used[i] = True
p = i
cur = e[i][0]
while True:
res += chr(ord("a") + cur)
used[cur] = True
if len(e[cur]) == 1:
break
if len(e[cur]) != 2:
break
if e[cur][0] == p:
p = cur
cur = e[cur][1]
else:
p = cur
cur = e[cur][0]
if len(res) != 26:
print("NO")
return
print("YES")
print(res)
q = int(input())
for _ in range(q):
do()