def id_to_int(s):
    num = 0
    for i, ss in enumerate(s[::-1]):
        num += (ord(ss) - ord("A") + 1) * pow(26, i)
    return num


S = input()
print(id_to_int(S))

上記のように、文字列を辞書で何番目に来るか？に変換することで、コンテスト内で6分程度の時間で、解くことができました。

atcoder.jp

D問題

ユーザ名の遷移をグラフとして表現し(問題文の意図通りに考えると、有向グラフであるが、今回の条件では無向グラフとして扱っても解くことができる)、閉路のある成分があるか？という問題

atcoder.jp

考察

まず、問題文を読み、入力例を見ながら紙にユーザの遷移を書いたことで、下記がわかりました(だいたい5分くらい？かかったかなと)

遷移を扱うので、有向グラフとして扱えそう
入力例2 を見る感じで行くと、閉路がある場合は、Noとなりそう

その上で、有向グラフの閉路検出方法としては

DFS/ BFSで巡回し、今まで訪ねた要素に到着するか？どうかで判定する
- 以前、leetcodeで解いた際に使ったフロイドの循環検出でも解くことができると思ったが、戻ってくる要素の場所を知りたいといったニーズもないので、今回は使わなかったが、今思い返すと使った方が楽に解けたかも？と思う

leetcode.com

トポロジカルソートを行う
- 知識としてはあって、書いたこともあったが、空でかけるほどの自信はなかったので今回は選ばなかった

output-zakki.com

UnionFindを使う
- 無向グラフの平路検出で使える。今回のグラフは問題の制限上、一直線になるか、円になるか？しかないので使えそうだなと思ったが、若干自信なく、最初は選択しなかった

output-zakki.com

以上より、DFSをまず採択し、問題を解き進めました。この時、変更前/ 変更後のユーザ名はユニークであるため、下記のような1つの要素から、2つの辺が伸びることはないです。

つまり、各成分は下記の3つのどちらかの形になるはずで、成分中に閉路が1つでも発見できれば、Noになるはずです。

そこで、下記のようなコードを書き提出したのですが、WAが6つでてしまいました。

atcoder.jp

コンテスト中は問題の原因には、はっきりわからなかったのですが、おそらく、探索開始の要素の条件を指定していないので、下記のように探索してしまい、閉路と誤認しているのではないのか？と思いました。

WAを出しながらも、カイゼンしたものの、DFSではコンテスト中には解くことができず、UnionFindを使った方法に方針転換しました。ちなみに、コンテスト後下記のように改良し、無事に解くことができました。

from collections import defaultdict
from sys import setrecursionlimit

from pypyjit import set_param

set_param("max_unroll_recursion=-1")
setrecursionlimit(pow(10, 9))


def dfs(cur):
    visited[cur] = True
    if not edge[cur]:
        return
    s_set.remove(cur)
    for nxt in edge[cur]:
        if visited[nxt]:
            print("No")
            exit()
        dfs(nxt)


N = int(input())
edge = defaultdict(list)
in_cnt = defaultdict(int)
visited = defaultdict(bool)
s_set = set()
for _ in range(N):
    S, T = input().split()
    in_cnt[S] += 0
    in_cnt[T] += 1
    edge[S].append(T)
    s_set.add(S)
deps = [k for k, v in in_cnt.items() if v < 1]
if not deps:
    print("No")
    exit()
for dep in deps:
    dfs(dep)
if s_set:
    print("No")
    exit()
print("Yes")

atcoder.jp

ポイントは、下記の2点かと思います。

入次数をカウントし、入次点0(= rootになるべき要素)から、DFSするようにした
完全に閉路なグラフ(= 図3. の一番下のような形)の場合、入次点0の要素がないため、探索しないことになるので、各要素を探索したか？のstatusをsetで管理し、もし閉路が見つからなくても、探索していない要素があればNoとする

寄り道しましたが、コンテスト中UnionFindを使い、下記のように解きました。自分の持っているUnionFindのライブラリでは、UnionFindの要素はindexが数値で、かつListで管理していたため、defaultdictを使って、index numberが連続値でなくとも使えるようにしたのと、keyがstringだったため、intに変換し利用しました。

from collections import defaultdict


class UnionFind():
    def __init__(self):
        self.parents = defaultdict(lambda: -1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


def str_to_int(s):
    num = 0
    for i, ss in enumerate(s[::-1]):
        num += (ord(ss) - ord("a") + 1) * pow(26, i)
    return num


N = int(input())
uf = UnionFind()
for _ in range(N):
    S, T = map(str_to_int, input().split())
    if uf.same(S, T):
        print("No")
        exit()
    uf.union(S, T)
print("Yes")

無事、下記の通り、解くことができました。図3. にある通り、今回は3パターンのグラフの形しかなく、無向グラフとみなしても、有向グラフと同じ閉路が検出できるため、UninonFindが使うことができました。この辺りは、感覚でやっていましたが、同僚と毎週やっている勉強会で指摘され、改めて認識することができました。

atcoder.jp