AtCoder

ABC285 D問題(Change Usernames)を解く

AtCoder_ABC285_D

AtCoder が提供しているABC(AtCoder Beginner Contest)285 のD問題をC++とPythonで解いてみました。ABC285は、2023年1月15日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Change Usernames(Difficulty : 663)

問題はリンク先をご覧ください。

ABC285 D問題 Change Usernames

グラフの閉路を求める問題でした。AtCoder Problems による Difficulty は 663でした。

解答案

変更前→変更先の文字列の関係を、有向グラフと考えます。入力例2にあるように a → b → c → a のような閉路を持つと変更できません。逆に閉路が無ければ、グラフの末端(葉に近い方)から、処理することができます。

    C++ プログラム例(ABC285D)

    グラフを map で表現している例としては、ABC277 C問題がありました。この問題は、グラフを string と vector<string> の map で表現しました。

    グラフは、DFS(深さ優先探索:Depth-First-Search)で探索しました。基本と異なるのは、「訪れたか」を表す bool 型の seen に「訪れきったか」を表す finished を加えました。seen が true で、finished が false であれば、閉路を検出したことになります。

    閉路を検出したかを bool 型の変数 is_dected に記憶して、最後に出力をしています。

    以下は、C++ プログラムです。ポイントとなる行の背景行を変更しました。

    #include <bits/stdc++.h>
    using namespace std;
    
    map<string, vector<string>> e;
    map<string, bool> seen;
    map<string, bool> finished;
    
    bool is_detect;
    
    void dfs(string v)
    {
    	seen[v] = true;
    
    	for (auto next_v : e[v]) {
    		if (seen[next_v]) {
    			if (!finished[next_v]) {
    				is_detect = true;
    			}
    		} else {
    			dfs(next_v);
    		}
    	}
    
    	finished[v] = true;
    }
    
    int main()
    {
    	int n;
    	cin >> n;
    	vector<string> s(n);
    	vector<string> t(n);
    	for (int i = 0; i < n; ++i) {
    		cin >> s[i] >> t[i];
    		e[s[i]].push_back(t[i]);
    	}
    
    	is_detect = false;
    	for (int i = 0; i < n; ++i) {
    		if (!seen[s[i]]) {
    			dfs(s[i]);
    		}
    	}
    
    	if (!is_detect) {
    		cout << "Yes" << endl;
    	} else {
    		cout << "No" << endl;
    	}
    
    	return 0;
    }

    AC(Accepted=正しいプログラム)と判定されました。

    Python プログラム例(ABC285D)

    Python 版も、C++ のプログラムをそのまま移植しました。

    """AtCoder Beginner Contest 285 D"""
    import sys
    from collections import defaultdict
    
    LIMIT = 10 ** 5
    sys.setrecursionlimit(LIMIT)
    
    
    def dfs(v):
        global is_detect
        seen[v] = True
        for next_v in e[v]:
            if seen[next_v]:
                if not finished[next_v]:
                    is_detect = True
            else:
                dfs(next_v)
        finished[v] = True
    
    
    n = int(input())
    s = []
    t = []
    e = defaultdict(list)
    seen = defaultdict(lambda: False)
    finished = defaultdict(lambda: False)
    
    for i in range(n):
        s_t, t_t = input().split()
        s.append(s_t)
        t.append(t_t)
        e[s_t].append(t_t)
    
    is_detect = False
    for i in range(n):
        if not seen[s[i]]:
            dfs(s[i])
    
    print("Yes" if not is_detect else "No")

    このプログラムは、Python(3.8.2)では、RE(Runtime Error)判定でした。一方、PyPy3(7.3.0)では、AC 判定となりました。今回は、このプログラムを Python 版として紹介します。

    最後に

    この問題は、コンテストでは解くことができませんでした。set と map を使って、最終的には、グラフの閉路を求めることに近いことをやっていました。

    問題をグラフなどの良く知られているデータ構造に帰着できると、解きやすいことが学べました。

    引き続き ABC に挑戦して、解説記事を書いていくつもりです。

    COMMENT

    メールアドレスが公開されることはありません。 が付いている欄は必須項目です

    CAPTCHA