AtCoder

ABC276 A問題(Rightmost)を解く

AtCoder_ABC276_A

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

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

A問題 Rightmost(Difficulty : 13)

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

ABC276 A問題 Rightmost

条件を満たす配列のインデックスを求める問題です。AtCoder Problems による Difficulty は、13 でした。ABC A問題として、標準的な問題です。

解答案

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

  • 文字列を読み込む。
  • 最後に現れる ‘a’ の場所を探す。
  • 求めた場所を表示する。

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

単純に先頭から文字 ‘a’ を探します。’a’ が複数ある場合、表示する結果(変数 result)を更新します。解答として表示する数字は、1から開始(1オリジン)ですが、配列は0から開始(0オリジン)なので1を加えています。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	cin >> s;

	int result = -1;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == 'a') {
			result = i + 1;
		}
	}

	cout << result << endl;

	return 0;
}

別の解答としては、文字列の後ろから探します。見つかったらループを抜けます(13行目)。平均のループ回数はこちらの方が減ります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	cin >> s;

	int result = -1;
	for (int i = s.length() - 1; i >= 0; --i) {
		if (s[i] == 'a') {
			result = i + 1;
			break;
		}
	}

	cout << result << endl;

	return 0;
}

ただし、最悪のループ回数は前者も後者も同じです。前者の場合は、文字列に依らず文字列長さ分だけ調べます。後者の場合も、文字列の先頭にのみ ‘a’ がある場合、文字列長さ分だけ調べることになります。

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

Python プログラム例(ABC276A)

Python 版として、C++ の前者版を書き換えました。

"""AtCoder Beginner Contest 276 A"""
s = input()
result = -1
for i in range(len(s)):
    if s[i] == "a":
        result = i + 1
print(result)

コードチェックツール pylint で、”Consider using enumerate instead of iterating with range and len” と表示されました。Python では、enumerate を使う方が好ましいと考えてられているようです。

次が enumerate を使って書きなおしたプログラムになります。差分は背景色を変更しました。こちらの方が Python らしいのかもしれません。

"""AtCoder Beginner Contest 276 A"""
s = input()
result = -1
for i, c in enumerate(s):
    if c == "a":
        result = i + 1
print(result)

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

最後に

A問題は内容は簡単ですが、まだ Python に慣れていないわたしには、ちょうどよい演習になっています。

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

COMMENT

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

CAPTCHA