paizaの新作プログラミングゲーム【電脳少女プログラミング2088 ─壊レタ君を再構築─】廃マンションの一室（paizaランク：C相当）をPython3で実装しました。
数学苦手な僕が数学苦手な方のために解説しようとおもいます。
問題
こういう問題
ということです。
と…特殊な三進法？？
| 通常の三進法 | 特殊な三進法 |
|---|---|
| [0, 1, 2] | [-1, 0, 1] |
特殊な三進法では2の代わりに-1を使います。
10進法→通常の3進法
割り算と余りを使って商が3で割り切れなくなるまで繰り返します。
で、割り切れなくなったら余り部分を下から上に読んでいきます。
例:157(問題で入力される値なので)
| 計算 | 商 | 余り (3進数の桁) | |
|---|---|---|---|
| 157 ÷ 3 = 52 ... 1 | 52 | 1 | |
| 52 ÷ 3 = 17 ... 1 | 17 | 1 | |
| 17 ÷ 3 = 5 ... 2 | 5 | 2 | |
| 5 ÷ 3 = 1 ... 2 | 1 | 2 | |
| 1 ÷ 3 = 0 ... 1 | 0 | 1 | ここから上に読んでいく |
答え:12211
となります。
3進法→10進法に直すときは？
各桁の値を3のn乗したものを足していきます。(^は累乗を表します。)
| 桁の値 | 対応する指数 (n) | 計算式 | 結果 |
|---|---|---|---|
| 1 | 4 | 1 × 3^4 = 81 | 81 |
| 2 | 3 | 2 × 3^3 = 54 | 54 |
| 2 | 2 | 2 × 3^2 = 18 | 18 |
| 1 | 1 | 1 × 3^1 = 3 | 3 |
| 1 | 0 | 1 × 3^0 = 1 | 1 |
| 合計 | 157 |
10進法→特殊な三進法は？
まずは計算の流れから
| 計算 | 商 | 余り | バランス3進法の桁 | 繰り上げ調整 | 最終桁(余り) |
|---|---|---|---|---|---|
| 157 ÷ 3 = 52 ... 1 | 52 | 1 | 1 | なし | 1 |
| 52 ÷ 3 = 17 ... 1 | 17 | 1 | 1 | なし | 1 |
| 17 ÷ 3 = 5 ... 2 | 5 | 2 | -1 | 商+1 (6) | 2 |
| 6 ÷ 3 = 2 ... 0 | 2 | 0 | 0 | なし | 0 |
| 2 ÷ 3 = 0 ... 2 | 0 | 2 | -1 | 商+1 (1) | 2 |
| 1 ÷ 3 = 0 ... 1 | 0 | 1 | 1 | なし | 1 |
考え方:
余りが2(-1として扱う)の場合に、マイナスされた分を
次に計算される商に＋1(余りを1増やす)をして差分を埋めます。
何を言ってるかというと...
2の表し方って 2 = 3 + (-1) も同じだよね？ってことです。
5の表し方って 5 = 3 + 2 = 9 + (-3) + (-1) も同じだよね？ってことです。
マイナスされた桁は次の桁で取り返す！！
| 5(10進数)の計算 | 商 | 余り(特殊な3進数表記) | 10進数表記 | 繰り上げ |
|---|---|---|---|---|
| 5 ÷ 3 = 1 ... 2 | 1 | 2 | -1 | 余り2なので商に+1をして2にする |
| 2 ÷ 3 = 0 ... 2 | 0 | 2 | -3 | 余り2なので商に+10にして1にする |
| 1 ÷ 3 = 0 ... 1 | 0 | 1 | 9 |
なんとなくわかってきました？
なので今回やりたいことは
通常の10進法→3進法の処理をしていく中で、余りが2(-1として扱う)の場合に、次の商を+1するようにコードを書いてみよう！
・通常の10進法→3進法の処理
・余りが2の場合、商を+1する
一旦ここで読むのを止めて実装してみてください。
実装できれば...
^^
どうしても分からない方は下にコードを示すので、正解を基に落とし込んでください。
通常の10進法→3進法の処理
N = int(input())
mod_list = []
while N :
mod_num = N % 3
mod_list.insert(0, mod_num)
if mod_num == 2:
N += 1
N //= 3
print("".join(map(str ,mod_list)))
余りが2の場合、商を+1する
if mod_num == 2:
N += 1
がっちゃんこコード
N = int(input()) #入力値
mod_list = [] #余りを入れる用
while N : #Nが0になるまでループ
mod_num = N % 3 #ここで余りを出す
mod_list.insert(0, mod_num) #mod_listの先頭に余りを入れる(余りは下から上に読むため)
if mod_num == 2: #もし余りが2なら
N += 1 #商を+1します
N //= 3 ##小数点切り捨てる割り算をする
print("".join(map(str ,mod_list)))
まとめ
Cランクというから安易に手を出したけど、
初めは分からな過ぎてAランクぐらいあるだろうって思ってましたけど
考え方のところさえクリアできればコーディング内容自体はCランクで妥当なのかなって思います。
10進数から2進数の変換方法すら分からなかったので調べましたし....
適当な理解で済ませたくない方は、平衡三進法と呼ばれるものらしいので調べてみてください。