はじめに
ITエンジニア向け転職・就活・学習サイトである paiza にて、
新作ゲーム「電脳少女プログラミング2088 | 壊レタ君を再構築」がリリースされました。
paizaでは「スキルチェック」と呼ばれるプログラミングの学習支援を行っており、
実際に問題をクリアする事でレートスコアが与えられ、
自分がどれだけ正確に、かつ高速でプログラミングを行い、解く事が出来るかを
スコアで可視化する事が出来るサービスが提供されています。
本ゲームもこのスキルチェックの様にプログラミングの問題を解いて進めるゲームで、
問題をクリアする事でゲーム中のキャラクターの見た目を変更するパーツが手に入ったり、
性格を変更するアイテムが手に入ったりする事が出来る様になっています。
paizaのコンセプトである「楽しみながらプログラミングを」を実現する形となっています。
問題C 「廃マンションの一室」
今回は、「電脳少女プログラミング2088 | 壊レタ君を再構築」で解くことが出来る、
難易度Cである「廃マンションの一室」を取り上げて解説します。
実際の問題は、ゲーム内でご確認下さい。
問題の概要
与えられた10進数の数値を「特殊な3進数」で表現した数値に変換する事が、
本問題の主旨になります。
特殊な3進数とは？
今回の問題に適用される特殊な3進数とは、以下の様なルールになっています。
2 を -1 の意味として扱う特殊な 3 進数を使っています。
問題文に示されている例を示すと、-5 から 5 までの数値は以下の様に表現されます。
上表の10進数の値が与えられるので、それを特殊3進数に変換して表示する事が出来れば、
この問題をクリアする事が出来ます。
そもそも10進数とか3進数って何？
多くの方は普段「10進数」を扱っていると思いますが、
10進数とは数値を「10のN乗の塊がそれぞれ何個あるか」という形で表現した物です。
具体的に、10進数で 12345 という数値は以下の様に表現する事が可能です。
この値から1の位の桁の数値を取り出す場合、
元の数値から10の1乗で割った余りを利用する事で取り出す事が可能です。
また、10の位の桁の数値を取り出す場合は、
元の数値から１の位の桁の数値を引いた値を算出し、
その値から10の2乗で割った余りを算出し、
さらに10の1乗で割る事により取り出す事が出来ます。
この様な手法を延々繰り返す事で、各桁の値を導出する事が出来ます。
計算手法を図示すると、以下の様になります。
最終的には数値は全桁０となり、
その時取り出した各桁の数値を下から表した数がその進数での値となります。
上の図で言えば10進数を10進数で表したので、元の数値と同じ値になっています。
10進数を一般的な3進数に置き換える場合もこの方法を適用する事が出来ます。
例えば10進数の「14」は 14 = (9 * 1) + (3 * 1) + (1 * 2) なので、
3進数に置き換えると「112」となりますが、
以下の図の様に処理をする事で3進数に置き換える事が出来ます。
この様な形で10進数→N進数の変換を行う事が可能です。
特殊な3進数への変換
しかしながら上記の変換は、
「N進数の各桁の取り得る値は 0 ~ N-1 の間である」という前提条件があります。
もう少し丁寧な形で説明するなら、
除算における剰余の取り得る値の範囲が各桁の取り得る値の範囲と等しければ成立します。
この問題における「特殊な3進数」では、2が-1の役割を示しており、
残念ながらこの前提条件を満たしておらず、そのまま適用する事が出来ません。
この為、もう少し上記の計算処理自体に手を加える必要があります。
具体的には以下の図の様に、取り扱える範囲のギャップを埋める事です。
各桁の数値を求め終わった後に、元の数値から値をいくつか引く場面がありますが、
ここで取り扱える値の範囲のギャップを調整します。
本来元の値から数値を引く所を、ギャップとなる数値を加算する事で値を補正します。
2（-1として扱う）が出現した時、通常の3進数変換では引き算処理になってしまいますが、
代わりに3のN乗（Nはその位の桁数）を加算することで、
結果的に正しい特殊3進数の値を得ることができます。
例えば、最下位の桁で2が出現した場合、-2として扱うべき所を、
3^0=1を加算することで、次の桁の計算に正しく影響を与えることができます。
これで修正した特殊3進数計算を行う事が可能です。
負の値の取り扱い
ここまでは正の値のみ取り扱ってきましたが、本問題では負の値も考える必要があります。
ただ、この特殊な3進数では値の取り得る範囲が0,1,2(-1)と対称になっている事から、
負の値は「正の値の1と2を入れ替えたもの」となります。
この事から「基本的には正の値で計算し、元の値が負なら1と2を入れ替える」手法で
負の値も同じ計算式で対応することが出来ます。
提出コード
提出したコードは以下となります。利用したのはpython3です。
提出コード
# 10進数でinputし、絶対値も算出する
num_10:int = int(input())
num_10_abs:int = abs(num_10)
# 結果文字列
result:str = ''
pos:int = 1
# num_10_abs==0になるまで3進数の桁を追加する
while num_10_abs:
value:int = num_10_abs % pow(3, pos) // pow(3, pos-1) # 3進数での各桁の値
result += str(value)
if(value<2):
num_10_abs -= value * pow(3, pos-1) # valueが0,1の場合は元の値から引く
else:
num_10_abs += pow(3, pos-1) # valueが2の場合は元の値にギャップを加算しておく
pos += 1
# 逆順になった配列を反転させる
result_rev:str = result[::-1]
# 元の値が負数の場合は特殊3進数を考慮して1と2を入れ替える
if(num_10 < 0):
for i in range(len(result_rev)):
if(result_rev[i] == '1'):
result_rev = result_rev[:i] + '2' + result_rev[i+1:]
elif(result_rev[i] == '2'):
result_rev = result_rev[:i] + '1' + result_rev[i+1:]
# return
print(result_rev)
実行結果は以下の通りで、高速で解を求める事が出来ました。
別解
別解として、この問題の入力数値の範囲がそれほど大きくない事に着目します。
-100,000 ≦ N ≦ 100,000
要求される数値範囲が大きくない事を前提にするなら、
正の値における特殊3進数を0~100000の値まで全て計算し、
先に配列に格納しておき、要求された数値を配列から参照する手法も検討出来ます。
この場合、0から値を1ずつ足しながら配列に格納していくだけなので、
特殊3進数に1を適切に加算出来るロジックを作りさえすれば簡単に実装可能です。
一番小さい桁に1を加算し、繰り上がりがある場合は次の桁の処理を、
繰り上がりが無い場合はそこで終わって配列に追加、という処理を規定回数行います。
以下が提出したコードとなります。
提出コード
result_list = ['0'] # 結果配列の初期作成
current = ['0'] # 現在の特殊3進数の値配列
# 1~100000までの値の算出と格納
for _ in range(100000):
i = 0
carry = 1 # 繰り上がりの有無
# 1足した後の各桁の数値変更を行う
while i < len(current) and carry:
digit = int(current[i])
if(digit == 1):
current[i] = '2'
carry = 1
elif(digit == 2):
current[i] = '0'
carry = 0
else:
current[i] = '1'
carry = 0
i += 1
# 全ての計算を終えた後に繰り上がりが残っている場合
if carry:
current.append('1')
# 結果配列result_listに追加
result_list.append(''.join(current[::-1]))
# 10進数でinputし、絶対値も算出する
num_10:int = int(input())
num_10_abs:int = abs(num_10)
# 配列から値を取得
result:str = result_list[num_10_abs]
# 元の値が負数の場合は特殊3進数を考慮して1と2を入れ替える
if(num_10 < 0):
for i in range(len(result)):
if(result[i] == '1'):
result = result[:i] + '2' + result[i+1:]
elif(result[i] == '2'):
result = result[:i] + '1' + result[i+1:]
# return
print(result)
こちらも、先程のプログラム程高速ではありませんが、満点を取る事が出来ました。
要求される値の範囲が今以上に大きくなった場合は、
計算量も大幅に増大するプログラムなので、計算が大幅に遅くなる事は考慮して下さい。
おわりに
他にも解き方は色々あるのではないかと思いますが、
今回は記事化に際して二通りの解き方で解いてみました。
もっと高速に解く方法もありますし、短いコードで解決させる方法もあると思います。
様々な楽しみ方で楽しみながらプログラミングが出来るので、
是非皆さんも問題にチャレンジしてみて下さい。