読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

yukicoder No.18 うーさー暗号

yukicoder yukicoder-★

問題

問題のURLはこちらです。
No.18 うーさー暗号 - yukicoder


考えたこと

i個目の文字について、

  1. 文字を数値に変換する
  2. その数値からi引く
  3. 数値を文字に変換する

と行えばよさそうですね。


コード(C++)

#85751 No.18 うーさー暗号 - yukicoder

#include <iostream>
#include <string>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    std::string S;
    std::cin >> S;
    for(size_t i=0; i<S.size(); ++i){
        S[i] = ((S[i]-'A')-(i+1)+1300)%26+'A';
    }
    std::cout << S << "\n";

    return 0;
}

コードの説明など

入力に対して計算を行っているのはforループの中の1文のみなので、その右辺について順を追って説明します。

S[i]-'A'

ここでは「文字を数値に変換」しています。
C++では、半角アルファベットを数値(ASCIIコード)として扱っています。
その対応表は次のとおりです。

アルファベット A B C D ... X Y Z
ASCIIコード 0x41 0x42 0x43 0x44 ... 0x58 0x59 0x5A

(0x41は「16進数の41」を表します)

よって、「このアルファベットはAから数えて何番目なのか?」ということを調べたいときは、そのアルファベットから'A'(つまり0x41)だけ引いてやればいいのです。

S[i]の意味する文字 A B C D ... X Y Z
S[i]の数値(16進法表記) 0x41 0x42 0x43 0x44 ... 0x58 0x59 0x5A
S[i]の数値(10進法表記) 65 66 67 68 ... 88 89 90
S[i]-'A'(10進法表記) 0 1 2 3 ... 23 24 25

確かに、S[i]-'A'を計算することで、Aから数えて何番目かということがわかりますね。

(S[i]-'A')-(i+1)

次に、「数値からi引」いています。
コードではi+1引いていますが、配列の中身にアクセスする添字は0から始まるためです。

S[i]のi 0 1 2 3 ...
数えるとき 1文字目 2文字目 3文字目 4文字目 ...

と、添字のiとはちょうど1だけ大きいことがわかりますね。

((S[i]-'A')-(i+1)+1300)%26

ここでは、「Zの次はA」とループすることの計算をしています。

理想としては、計算した数値に対しするアルファベットは次のようになったらいいですね。

数値 0 1 2 ... 24 25 26 27 ... 50 51 52 53 ...
アルファベット A B C ... Y Z A B ... Y Z A B ...


では、どうしたら良いかというと、数値を26で割った余りを求めれば良いのです。
26で割った余りを欄を上の表に追加してみると、

数値 0 1 2 ... 24 25 26 27 ... 50 51 52 53 ...
数値を26で割った余り 0 1 2 ... 24 25 0 1 ... 24 25 0 1 ...
アルファベット A B C ... Y Z A B ... Y Z A B ...

となることがわかります(26はアルファベットAZまでの文字数です)。


ところで、C++での剰余(%)は「絶対値を割った余り」を算出してしまうようです。
具体的には次のような感じです。

ある整数Nに対して、

N ... -5 -4 -3 -2 -1 0 1 2 3 4 5 ...
N\% 3 ... -2 -1 0 -2 -1 0 1 2 0 1 2 ...


上記のコードで「(S[i]-'A')-(i+1)」としているため、入力文字数が最大である1024ほど大きいときには割られる数が負になることもあるのです。
これでは、最後に数値から文字に直す際におかしな事になってしまいますね。

その解決法として、割る数26の倍数であり1024より大きい1300を加える事で、入力がどんなものであったとしても必ず割られる数は正になるため、正確な「26で割った余り」を求めることが出来ます。

((S[i]-'A')-(i+1)+1300)%26+'A'

最後に、'A'を加える事によって「数値を文字に変換」することが出来ます。


あとはこれを各文字に対してループすると良いですね。


備考

計算量は、文字数に対するループのみなのでO(Sの文字数)ですね。


なお、C++のstd::stringでは、operator[](int)で参照・代入するときはchar型に変換されるので、Cと同じようなコードを書くことが出来ます。


感想など

この問題の「最後の次は最初に戻す」というような操作は、色々な場面で使えるものだと思います。
(ゲームでのカーソルの移動とか、ルーレットとかを想像したらわかりやすいですかね)

また、char型の文字に対する数値的な演算というものも覚えておいて損はないと思います。
この問題の「'A'を引いてAから何番目の文字かを調べる」といったことや、「'A'-'a'の値を使って大文字・小文字の変換をする」などが出来るので、あるとたまに役に立ったりします。


そのため、この問題を解くことで文字処理などの基本的なことの勉強になりますね。プログラミングを勉強し始めて少し経った頃に演習問題としてこの問題を解くと良いんじゃないでしょうか。