はじめに
本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
質問や指摘などもコメント等に書いてくださったら対応していきたいと考えていますのでどしどしコメントしてください。(内容がわかりにくいぞ！みたいな文句でもオールオッケーです笑)
AtCoder Beginner Contest 285 [C問題]
問題のURLはこちらです。AtCoder Beginner Contest 285
使う手法
今問題ではN進数の考え方を利用していきます。
N進数とは、あらかじめ定められたN種類の記号や数字を列べることによって数を表す方法です。
普段私たちが使っている数は、0~9の10個の記号(数字)を用いているため、10進数です。
今回の入力「S」はアルファベット26文字で作らているため、26進数の数と考えることができます。
つまり今問題は、26進数の値を10進数の値に変更してくださいという問題に置き換えることができます。
N進数->10進数への変換
一般に、l桁で構成されたN進数の数「L」を10進数の数$L_{10}$に変換する場合
L_{10} = \sum_{k=1}^{n} n_k × N^{i-1}
という式で変換することができます。($n_k$は左からk桁目の値を表しています。)
式だけを見てもなんのこっちゃ？ってなると思うので、10進数の値「365」を用いて説明します。
365を桁ごとに分解すると、以下のようになります。
365 = 3×10^{3-1} + 6×10^{2-1} + 5×10^{1-1}
このように見てみると、左からi番目の桁に書かれている値「ni」は、元々の値(今回の例では365)の中に$10^{i-1}$がいくつあるかを表しているのがわかります。
N進数についても同様のことがいえ、左からi番目の桁に書かれている値「ni」は、元々の値の中に$N^{i-1}$がいくつあるかを表しています。
従って、全ての桁について上記の操作を行うことで、N進数を10進数に変換することができます。
考え方
値として並べられているものが全てアルファベットなので、各アルファベットを10進数の値とリンクさせる必要があります。
今回私はアルファベットが順番に並んでいるリスト「alpha」を作成し、それが格納されているインデックスを用いることで、各アルファベットと数字をリンクさせました。
あとは先ほど述べた操作を行い、10進数に変換していきます。
実装例
#標準入力
s = input()
#sの長さを取得
n = len(s)
#最終的に出力する値を設定。初期値は0
num = 0
#アルファベットを格納するリスト「alpha」を作成。
#その後A、B、・・・・Zまで順番にalphaに格納していく
alpha = []
for i in range(97, 123):
alpha.append(chr(i).upper())
for i in range(n):
#右からi番目のアルファベットを取り出す
sub_s = s[i]
#取り出したアルファベットが格納されているインデックスを調べる
number = alpha.index(sub_s) + 1
#取り出した値を足す
num += number * 26**(n-1-i)
print(num)
最後に
N進数の考え方は意外と応用が効くので便利です。
私は競プロ典型問題002 Encyclopedia of Parenthesesでも2進数の考え方を応用しました。
公式解説とは全然解法が違いますが、ぜひ2進数の考え方を用いて解いて見てください。
(需要がありましたら、こちらについてもコード例を載せてみます。)
追記(2023/2/4日)
「最後に」の部分で競プロ典型問題002を2進数の考え方を使ったと書いていますが、正しくは「ビット探索」と言いう探索系のアルゴリズム(?)らしいです。アルゴリズムの点では解説と同じことをしていました。
調子に乗って、公式解説とは違う！と書いていますが、ほとんど公式解説と変わりませんすみません笑