Official
B - Caesar Cipher Editorial by leaf1415
\(K \geq 26\) のとき、\(K\) 個後ろの英小文字は \((K-26)\) 個後ろの英小文字と等しいので、高橋君が選ぶ \(K\) は \(0 \leq K \leq 25\) を満たすとして良いです。
よって、
- 高橋君が \(K = 0\) を選んだ場合
- 高橋君が \(K = 1\) を選んだ場合
- 高橋君が \(K = 2\) を選んだ場合
- \(\cdots\)
- 高橋君が \(K = 25\) を選んだ場合
の \(26\) 通りそれぞれについて、「高橋君が操作を行った後の \(S\) が、\(T\) と一致するか」を調べ、\(26\) 通りのうち一致するものが一つでもあれば Yes
を、そうでなければ No
を出力すれば、この問題に正解できます。
ある \(K\) に対して「高橋君が操作を行った後の \(S\) が、\(T\) と一致するか」を調べるには、高橋君が行う操作を実際にシミュレーションすれば良いです。すなわち、実際に、入力で与えられた\(S\) のすべての文字を \(K\) 個後ろの英小文字に置き換えてみて、それが \(T\) と一致しているかを判定すれば良いです。
- 「 \(S\) の各文字を」走査するには、プログラミング言語の標準的な機能である繰り返しの機能を用いると良いでしょう。例えば C++ 言語であれば、例えば for 文がこれを実現します。
- 「文字を \(K\) 個後ろの英小文字に置き換え」るには、英小文字
a
からz
の ASCII コードがそれぞれ連番になっていることを用いると良いでしょう。
C++ 言語による実装例を実装例1として本解説の最後に記載します。
上に述べた、\(K = 0, 1, 2, \ldots, 25\) の \(26\) 通りの場合を調べる方法とは別の方法として、次の方法も考えられます。
- まず、「 \(T\) の先頭の文字が \(S\) の先頭の文字の何個後ろの文字か」を求め、これを \(K_0\) とおきます。
- このとき、「高橋君が操作を行った後の \(S\) が、\(T\) と一致する」可能性が残っているのは、\(K = K_0\) の場合のみに限られます。よって、\(K = K_0\) の場合のみについて、「高橋君が操作を行った後の \(S\) が、\(T\) と一致するか」を調べ、一致していれば
Yes
を、そうでなければNo
を出力すれば、この問題に正解できます。
C++ 言語によるこの方法の実装例を実装例2として記載します。
実装例1
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
string s, t;
cin >> s >> t;
for(int k = 0; k <= 25; k++){
string s2 = s;
for(int i = 0; i < (int)s.size(); i++){
s2[i] = ((s2[i]-'a')+k)%26 + 'a';
}
if(s2 == t){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}
実装例2
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
string s, t;
cin >> s >> t;
int k = (t[0]-s[0]+26) % 26;
string s2 = s;
for(int i = 0; i < (int)s.size(); i++){
s2[i] = ((s2[i]-'a')+k)%26 + 'a';
}
if(s2 == t) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
posted:
last update: