paizaのプログラミングゲームの最新作「電脳少女プログラミング2088-壊レタ君を再構築-」の問題のひとつ、「廃マンションの一室（paizaランク：C相当）」の回答・考え方・コードの流れの解説です。
この難問がCランクってマジですか…？
（たぶん処理の実装の簡単さでランク判定がされてそう）
※ あんまり上手な方法ではないです…。
綺麗な正答を見たい方はこちらをどーぞ！
問題（概略）
-
以下の表で表される「2 を -1 の意味として扱う特殊な 3 進数」があります。
-
標準入力から -100,000 ～ +100,000 の数値が10進数表記で渡されるので、上記の「特殊な 3 進数」に変換して出力！
「特殊な3進数」の仕様を考えてみる
正の数値
とりあえず、正の数値について考えてみます。
| 10進数 | 特殊な 3進数 |
普通の 3進数 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 12 | 2 |
| 3 | 10 | 10 |
| 4 | 11 | 11 |
| 5 | 122 | 12 |
きもちわるい！！
なんですかこの変な数列は…。
0 に 1 を加算するのは10進数と同じようなのですが、1 に 1 を加算した後の様子がヘンです。
どうも、1 に 1 を加算するとき、
- 一の位を 1 → 2
- 10進数だと 1 → -1（2 減少）
-
10 を加算
- 10進数だと 3 増加
とすることで、-2 + 3 = +1 ということで 1 の加算を表現しているようです。
- 10進数で 1 + 1 = 2 の場合（3進数で 1 + 1 = ?）
- 1の位の 1 に 1 を加算、1 → 2
- 上の加算による数値減少を打ち消すために 10 の位に 1 を加算、0 → 1
- 10進数で 4 + 1 = 5 の場合（3進数で 11 + 1 = ?）
- 1の位の 1 に 1 を加算、1 → 2
- 上の加算による数値減少を打ち消すために 10 の位に 1 を加算、1 → 2
- 上の加算による数値減少を打ち消すために 100 の位に 1 を加算、0 → 1
というようにすると、特殊な3進数の 2 , 5 がちゃんと表のとおりに計算できていることが確認できます。
2 に 1 を加算するときは 2 を 0 にするだけで良いので、最悪0から10万回インクリメントの処理をすれば表現できそう！
急に安心感が湧いてきました。
負の数値
安心したのも束の間、負の数値を忘れていたことに気づきました。
表の負の数を見てみると、マイナス符号を使わない、コンピュータでいうsigned intのような表記です。
2進数ってどうやって負の数を表現してたんだっけ…？と考えたとき、そういえば2進数では正の値 +n と負の値 -n を足すとなんか対応関係があることを思い出しました。
3進数でももしかしたら対応関係があるかもしれないので、とりあえず対応する数値を見比べてみます。
| 10 進 数 |
特殊 3進数 |
10 進 数 |
特殊 3進数 |
|
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 1 | -1 | 2 | |
| 2 | 12 | -2 | 21 | |
| 3 | 10 | -3 | 20 | |
| 4 | 11 | -4 | 22 | |
| 5 | 122 | -5 | 211 |
1と2が反転してる！！！
よかった…！全然難しくない！！
これ以上数学的な知識とかを要求されたら、頭がバクハツしてレイミちゃんみたいになっちゃうところでした。
わたしがバクハツしたら誰も頭部を拾ってくれません。よかったよかった。
正の数値の 1 と 2 を入れ替えて -1倍 すれば負の数値になるので、負の数値の変換を実装するのは簡単そうです。
10進数から「特殊な3進数」に変換する方法を考える
肝心カナメの、10進数を3進数もどきに変換する方法を考えてみます。
まずは簡単に考えるため、10進数を普通の2進数に変換する方法を考えてみます。
10進数の 2088 を2進数に変換してみます。
えーっと…
2088 = 2048 + 40
だから…
40 = 32 + 8
なので…
2088 = 2^11 + 2^5 + 2^3
となるので、右から数えて
12ビット目、6ビット目、4ビット目
を 1、それ以外を 0 にした2進数が 2088 になりそうです。
3進数の場合、
- 10進数を超えない最大の 3^n * 1 もしくは 3^n * 2 を用意
- 右から数えて (n+1) ビット目 に 1 もしくは 2 を加算する
- 2 を加算するときは、上の位に 1 を加算
とすることで10進数から3進数への変換ができそうです。
目途が立ったので、コードを書いてみます。
※ 注意：もっと効率的な変換方法があります。上にも書きましたが、詳しくはこちらのカンペキな解説ページをどうぞ
コードを書いてみる
変換の方法がわかったので、10進数を3進数もどきに変換するコードを書き始めてみることにします。
言語はPythonです。
まず「特殊な3進数」が最大で何ケタになるのかを考えます。
入出力例2を見ると、-100000 が 211021211102 になるみたい。
正負でケタ数は同じことがわかっているので、最大で12ケタで良さそうです。
まず、12ケタの 0, 1, 2 を格納するlistの型を定義します。
from typing import List
# 3進数もどきを1の位から順に格納する型（12桁で固定）
Num3 = List[int]
# Num3 の最大桁数
num3_max_digit = 12
paizaのPythonはtypingのlist[int]表記を標準サポートしていないバージョンなので、typingからListをインポートします。
次に、1 を加算する関数を書きます。
def add_1(num3: Num3, digit: int) -> None:
"""3進数もどきのNum3に1加算する"""
# 1増やす
if num3[digit] == 0:
num3[digit] = 1
elif num3[digit] == 1:
num3[digit] = 2
add_1(num3, digit + 1) # 繰り上がり
elif num3[digit] == 2:
num3[digit] = 0
else:
raise Exception()
対象のケタが 0, 2 だった場合は素直に次の数値、1 だった場合は 2 にした上で上の位にも 1 を加算します。
次に、正負反転の関数を書きます。
def minus(num3: Num3) -> None:
"""3進数もどきを -1 倍する"""
for digit in range(num3_max_digit):
if num3[digit] == 1:
num3[digit] = 2
elif num3[digit] == 2:
num3[digit] = 1
全ビットの 1, 2 を反転！
めちゃんこ楽です。
10進数はintで渡すとして、10進数を「特殊な3進数」に変換する処理は以下のように書きました。
def num10_to_num3(num10: int) -> Num3:
"""10進数のintを3進数もどきのNum3に変換する"""
num3: Num3 = [0 for _ in range(num3_max_digit)] # 返す用のNum3
left_abs_num10 = abs(num10) # 変換しきれていない残りの10進数
# 10進数の絶対値から 3^digit（最高で 3^10）を大きい順に引いていく
for digit in range(10, -1, -1):
pow_3_digit = 3 ** digit
if left_abs_num10 >= pow_3_digit * 2:
# 2
left_abs_num10 -= pow_3_digit * 2
# 3進数の右から(digit + 1)ケタ目を 2 加算
add_1(num3, digit)
add_1(num3, digit)
elif left_abs_num10 >= pow_3_digit:
# 1
left_abs_num10 -= pow_3_digit
# 3進数の右から(digit + 1)ケタ目を 1 加算
add_1(num3, digit)
# 渡された10進数が負だったらビット反転
if num10 < 0:
minus(num3)
# 返す
return num3
最初に渡された10進数の絶対値を用意して、それを超えない 3^n を大きい順に引いていって、対応するケタに 1, 2 を加算しています。
渡された10進数が負だった場合は、得られた絶対値の3進数に -1倍 をして返しています。
以上の処理をまとめて入出力の処理を追加すると、以下のような感じに！
from typing import List
# 3進数もどきを1の位から順に格納する型（12桁で固定）
Num3 = List[int]
# Num3 の最大桁数
num3_max_digit = 12
def add_1(num3: Num3, digit: int) -> None:
"""3進数もどきのNum3に1加算する"""
# 1増やす
if num3[digit] == 0:
num3[digit] = 1
elif num3[digit] == 1:
num3[digit] = 2
add_1(num3, digit + 1) # 繰り上がり
elif num3[digit] == 2:
num3[digit] = 0
else:
raise Exception()
def minus(num3: Num3) -> None:
"""3進数もどきを -1 倍する"""
for digit in range(num3_max_digit):
if num3[digit] == 1:
num3[digit] = 2
elif num3[digit] == 2:
num3[digit] = 1
def num10_to_num3(num10: int) -> Num3:
"""10進数のintを3進数もどきのNum3に変換する"""
num3: Num3 = [0 for _ in range(num3_max_digit)] # 返す用のNum3
left_abs_num10 = abs(num10) # 変換しきれていない残りの10進数
# 10進数の絶対値から 3^digit（最高で 3^10）を大きい順に引いていく
for digit in range(10, -1, -1):
pow_3_digit = 3 ** digit
if left_abs_num10 >= pow_3_digit * 2:
# 2
left_abs_num10 -= pow_3_digit * 2
# 3進数の右から(digit + 1)ケタ目を 2 加算
add_1(num3, digit)
add_1(num3, digit)
elif left_abs_num10 >= pow_3_digit:
# 1
left_abs_num10 -= pow_3_digit
# 3進数の右から(digit + 1)ケタ目を 1 加算
add_1(num3, digit)
# 渡された10進数が負だったらビット反転
if num10 < 0:
minus(num3)
# 返す
return num3
def num3_to_str(num3: Num3) -> str:
"""str(Num3)"""
return "".join(str(c) for c in reversed(num3)).lstrip("0")
def main():
num10 = int(input())
num3 = num10_to_num3(num10)
print(num3_to_str(num3))
main()
提出！！
やった～！！100点！！！
ドS系レイミちゃんからも満点評価！
ちなみに端折ってますが、ただの100点じゃなくてドS系レイミちゃんからの最高評価を貰うためにけっこう手間がかかりました。
変数を説明的な命名にしたり…わかりやすいコメントを追加したり…別にQiitaに投稿する予定も無いのにdocstring書いたり…
でもドS系レイミちゃんって細部に妥協しない評価コメントくれるから、最高評価目指して何回もコード書き直しちゃう！！
ほかの性格だと、及第点だったらヨシ！！って感じのレイミちゃんになることが多いので、なんだか特別な性格です。
オマケ：「特殊な3進数」の元ネタ
この記事を書く際に調べて知ったのですが、なんとこの「特殊な3進数」、実は3進数コンピュータとして実在していたらしいです。びっくり。
感想
むずかしい！
ランクはBだとおもいます…。（面白かったです）
そして、果たしてこんな自己満足記事を見る暇人さんはいるんですか…？
超滑り込みだし。この記事より後に投稿する人いなさそう。
なんかめちゃくちゃ丁寧に書いちゃったけど、適当に提出コードコピペして適当に解説書くだけで良かったんじゃ…
もっと雑な記事書いてる人割といるし…
（Amazonギフト券500円ほしい！！！という動機）