Atcoder ABC285をpythonで解いてみた
目的
Atcoder ABC285に出場したので、その結果、感想、復習を兼ねて記事を書きました。特に、自分としてパフォーマンスが優れなかった!と感じた際には、必ず書くというのを今年続けようと思っています。
解いたコードで、気になって色々修正もしたものは下記に置いてあります。動作確認済みです。
結果
ABCDの4完で、Dで大量のWAを出しながら、ギリギリで通すことができましたが、E問題には時間をかけて取り組むことができませんでした。
D問題に関しては、方針はすぐ立ったものの、WAを取るにあたっての考察がゆるく、問題を解くのに時間がかかったと思っています。
振り返りに関しては、A, B問題は簡単であったと感じるので、解答のみに留めます。
A問題
- グラフをリストで表現した際に、0-indexで書いてしまい、1 WA出してしまったのは反省点(7分かかった)
B問題
- 問題文の意味を理解するのに苦戦し、15分程度時間をかけてしまった
C問題
与えられた文字列(ex. A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...) が、辞書順に並べた際に、何番目になるか?を求める問題
考察
まず、各文字は A-Z で与えられるので、26通りあることが、わかります。基数変換を書いたことがあったので、これは 1-indexed な26進数とみなせるのでは?と考えて解きました。
基数変換のロジックは上記のサイト他、多数で紹介されているため、ここでは割愛します。
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分程度の時間で、解くことができました。
D問題
ユーザ名の遷移をグラフとして表現し(問題文の意図通りに考えると、有向グラフであるが、今回の条件では無向グラフとして扱っても解くことができる)、閉路のある成分があるか?という問題
考察
まず、問題文を読み、入力例を見ながら紙にユーザの遷移を書いたことで、下記がわかりました(だいたい5分くらい?かかったかなと)
- 遷移を扱うので、有向グラフとして扱えそう
- 入力例2 を見る感じで行くと、閉路がある場合は、Noとなりそう
その上で、有向グラフの閉路検出方法としては
- DFS/ BFSで巡回し、今まで訪ねた要素に到着するか?どうかで判定する
- 以前、leetcodeで解いた際に使った フロイドの循環検出 でも解くことができると思ったが、戻ってくる要素の場所を知りたいといったニーズもないので、今回は使わなかったが、今思い返すと使った方が楽に解けたかも?と思う
- トポロジカルソートを行う
- 知識としてはあって、書いたこともあったが、空でかけるほどの自信はなかったので今回は選ばなかった
- UnionFindを使う
- 無向グラフの平路検出で使える。今回のグラフは問題の制限上、一直線になるか、円になるか?しかないので使えそうだなと思ったが、若干自信なく、最初は選択しなかった
以上より、DFSをまず採択し、問題を解き進めました。この時、変更前/ 変更後のユーザ名はユニークであるため、下記のような1つの要素から、2つの辺が伸びることはないです。
つまり、各成分は下記の3つのどちらかの形になるはずで、成分中に閉路が1つでも発見できれば、Noになるはずです。
そこで、下記のようなコードを書き提出したのですが、WAが6つでてしまいました。
コンテスト中は問題の原因には、はっきりわからなかったのですが、おそらく、探索開始の要素の条件を指定していないので、下記のように探索してしまい、閉路と誤認しているのではないのか?と思いました。
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")
ポイントは、下記の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が使うことができました。この辺りは、感覚でやっていましたが、同僚と毎週やっている勉強会で指摘され、改めて認識することができました。
E問題
考察
(解いたら載せます)
まとめ
今回は、D問題で多くの時間を使い、かつ多くのWAを出してしまったことで、自分の期待するperfomanceが出ませんでした。 考察の詰めの甘さが課題かと思っているので、引き続きこのような復習を繰り返し、見通しの良い考察と方針を立て、より早く問題が解けるようにしたいと思います。