Codeforces ECR82 C. Perfect Keyboard (グラフにして判定と結果の再構築)

https://codeforces.com/problemset/problem/1303/C

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です。

<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/834c0b49-52ec-aad4-1e08-378981726af6.png width=50%>

さて、それでは、次数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)$です。

```Python
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()
```

https://codeforces.com/contest/1303/submission/108178074