Official
A - Rightmost Editorial by KoD
\(S\) の文字数を \(n\) とします。この問題は、次のような一連の処理を実現できれば解くことができます。
- \(S\) の \(n\) 文字目が
a
なら、\(n\) を出力して実行を終了する。 - 次に、\(S\) の \(n - 1\) 文字目が
a
なら \(n - 1\) を出力して実行を終了する。 - 次に、\(S\) の \(n - 2\) 文字目が
a
なら \(n - 2\) を出力して実行を終了する。 - 次に、\(S\) の \(n - 3\) 文字目が
a
なら \(n - 3\) を出力して実行を終了する。
\(\qquad \vdots\)
- 次に、\(S\) の \(1\) 文字目が
a
なら \(1\) を出力して実行を終了する。 - 最後に、ここまでで
a
が見つかっていなければ、\(-1\) を出力して実行を終了する。
これら一つ一つの処理は、if 文を用いて実装することができます。しかし、この問題では \(n\) が最大で \(100\) になるので、このままだと \(100\) 個もの if 文を書くことになってしまいます。
そこで、これらの処理が、ほとんど同じ形をしていることに注目します。実際、最後の処理を除いて「\(S\) の \(i\) 文字目が a
なら\(i\) を出力して実行を終了する」という形になっており、これを \(i = n, n - 1, \dots, 1\) の順に行えばよいということがわかります。
このようなときに役立つのがループであり、for 文や while 文などを用いて実装することができます。例えば、C++ での実装例は次のようになります。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = size(s);
for (int i = n; i >= 1; i -= 1) {
if (s[i - 1] == 'a') {
cout << i << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
プログラム内における添字は 0-indexed なので、\(S\) の \(i\) 文字目はプログラム内では s[i - 1]
のようになることに注意してください。
また、補足ですが、return 0;
という文は「main
関数の実行を終了する」ことを表すため、これを用いて「\(i\) を出力して実行を終了する」という処理を実現しています。
なお、Python における実装例は次のようになります。
def main():
s = input()
n = len(s)
for i in range(n, 0, -1):
if s[i - 1] == 'a':
print(i)
return
print(-1)
main()
posted:
last update: