AtCoder

ABC280 C問題(Extra Character)を解く

AtCoder_ABC280_C

AtCoder が提供しているABC(AtCoder Beginner Contest)280 のC問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。

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

C問題 Extra Character(Difficulty : 64)

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

ABC280 C問題 Extra Character

2つの文字列を比較して、最初に差があるインデックスを出力する問題です。AtCoder Problems による Difficulty は、64 でした。ABC C問題としては、非常に簡単な問題です。

解答案

問題を解く方針を書きだします。

  • 文字列 S と 文字列 T を読み込む。
  • S と T を比較して、一致しない最初のインデックスを出力する。

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

    方針に従いプログラムしますが、注意点があります。文字列 T の末尾に文字を加える場合があります。この場合、文字列 S の長さの範囲では、文字列は一致します。

    文字列 S の長さの範囲で、文字列 T と一致した場合は、文字列 T の長さ(=文字列 S の長さ + 1)を出力します。

    解答は、場所の先頭を 1 からカウントしています。配列の先頭は、添え字 0となるため、1 を加えて出力しています。

    以下が、C++の実装例です。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	string s, t;
    	cin >> s >> t;
    
    	for (int i = 0; i < s.length(); ++i) {
    		if (s[i] != t[i]) {
    			cout << i + 1 << endl;
    			return 0;
    		}
    	}
    
    	cout << t.length() << endl;
    
    	return 0;
    }

    C++ の string は、s[s.length()] に ’\0′ が格納されていることが保証されています。これは、Cの文字列と整合を取るためです。このため、string は、実際の文字数よりも1個多い文字列のバッファを持っています。

    挿入される英小文字は、’\0′ ではありません。このため、以下のように文字列 S の長さ + 1(=文字列 T の長さ)まで比較することができます。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	string s, t;
    	cin >> s >> t;
    
    	for (int i = 0; i <= s.length(); ++i) {
    		if (s[i] != t[i]) {
    			cout << i + 1 << endl;
    			break;
    		}
    	}
    
    	return 0;
    }

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

    Python プログラム例(ABC280C)

    Python の場合は、文字列 S の長さの範囲で比較しました。その範囲で一致していれば、文字列 T の長さを出力しました。

    for 文を break で抜けていないときにだけ通過する else を使いました。

    """AtCoder Beginner Contest 280 C"""
    s = input()
    t = input()
    for i in range(len(s)):
        if s[i] != t[i]:
            print(i + 1)
            break
    else:
        print(len(t))

    こちらも「AC」と判定されました。

    最後に

    文字列の違いを判定するアルゴリズムは、興味深いものがあります。今回は、一番簡単な難易度の問題だと思われますが、もっと複雑な場合も解けるようになりたいと考えています。

    ABC280 について、引き続き、D問題まで紹介します。

    COMMENT

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

    CAPTCHA