N.Mです。皆さんはpaizaさんからリリースされたゲーム「電脳少女プログラミング2088 ─壊レタ君を再構築─」をプレイされたでしょうか？

面白そうだったのと、久々に競プロっぽいプログラミングをしたくなった¹ので、プレイさせていただきました。無事すべての問題を攻略できました。²

今回、その問題の中でも特に印象に残った問題 「廃マンションの一室」 （Cランク相当）を解く際にどう考えていたかを解説するとともに、C++のコードを紹介しようと思います。

問題内容

（実際のゲームより抜粋）

解説

ポイント

10進数を3進数に変換する問題ですが、我々が10進数を2進数に変換するとき、以下のように求めていると思います。

(1). 目的の数を2で割った余りを計算し、未決定の最下位ビットはその余りの値に決定する
(2). 目的の数を2で割った商（小数点切り捨て）で目的の数を更新し、次のビットを決めるために再度(1)を繰り返す
(3). 目的の数が1になるまで続け、最後に1を立てる

イメージ

負の数については、2進数のときは正の数の場合のビットをすべて反転させ、2進数上で1加えるということをやっていると思います。

今回の3進数は結構特殊ですが、2進数のときにやっている変換、負の値にするための反転を、3進数ではどうすれば実現できるかを考えるのがポイントだと思います。

問題を見て気がついた点

とはいっても、3進数なんて触れたことがないため、まずは問題にある10進数と3進数の対応表から手がかりを探してみましょう。³

1と-1, 2と-2の3進数の結果を見てみると、どうも0はそのままですが、1と2については1だったものは2に、2だったものは1になっていることに気づきました。

それもそのはずで、1と2を反転することで足し合わせている0以外の数値の全ての正負が反転するので、全体の正負も反転しますね。10進数である-4は(-3)+(-1)となり、3進数で22になりますが、2を1にし11とすれば(+3)+(+1)=4というようになります。このことから、正負反転は単純に1と2を入れ替えれば良いことがわかりました。変換についてはいったん正の数だけ考え、負の数については最後に3進数で正負反転すれば良さそうです。

次に、正の数の最下位ビットに注目しました。どうも、0~5については0→1→2→0→1→2の繰り返しとなっており、正の数の最下位ビットは普通に3で割ったときの余りとなることがわかります。このことから、割った余りを使う2進数の変換方法と似た方法がとれそうです。

変換の詳細

最初は2進数と同じように、小数点を切り捨てた2で割った商にどんどん数字を更新してみました。しかし、動作確認で回答が合いませんでした。ここでこの余りを用いた変換方法の考え方に立ち返ってみます。以下は43を変換する際の考え方の一部です。

(1). 43÷2=21余り1なので、最下位ビットは1となる
(2). 21×2+1=43であるので、最下位ビットを除いた残りビットは(1)の商である21を2進数変換したものとなる。つまり、2で割った小数点を切り捨てた商を2進数変換したものが残りのビットになる

ここで、今回は3進数での最下位が2のときは(-1)であることを思い出し、単純に小数点を切り捨てた商で数字を更新してはいけないことに気づきました。

例えば、3進数での最下位が2となる17は

× 17 = 5 × 3 + 2
◎ 17 = 6 × 3 + (-1)

となります。6×3の部分が残りの位を決める数字になりますが、元の数字に最下位で減らされる1を足し合わせた数字になります。小数点切り捨ての商での更新だとこの足すべき1が消えてしまうので、ずれてしまっていたんですね。このことから、以下のように数字を更新する必要がありました。

最下位が0の場合
元の数字をそのまま3で割った商に更新する。ex) 18→6 (18÷3)
最下位が1の場合
元の数字から1を引き、その数字を3で割った商に更新する。ex) 19→6 ((19-1)÷3)
最下位が2の場合
元の数字から1を足し、その数字を3で割った商に更新する。ex) 20→7 ((20+1)÷3)

解答例

最初に正解回答したものから、レイミちゃんのフィードバックを受けて、ブラッシュアップしたものになります。（最初はvector使わずに配列使っていたので、桁数増えた時どうするのかなどのご指摘をいただきました。）また、適宜コメントを追加しています。

#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int input = 0;
    cin >> input;
    
    bool isNegative = (input < 0);
    // bitの3進数版なのでtritとしています。
    std::vector<int> trit;

    // 負の数は正の数にしておき、最後に3進数の状態で符号反転します。
    if (isNegative) {
        input *= -1;
    }

    // 変換の詳細に記載した処理です。
    // 最下位ビットから求まりますが、最下位ビットは最後に表示する必要があるので、
    // vector<int>に格納して後で逆順に走査できるようにしています。
    while (input >= 2) {
        int currentTrit = input % 3;
        trit.emplace_back(currentTrit);
        switch (currentTrit) {
        case 1:
            input--;
            break;
        case 2:
            input++;
            break;
        }
        input = input / 3;
    }

    // 元々が0の場合は上のwhileが回らず、input=0となるため、このケースも対応できています。
    trit.emplace_back(input);

    // 最下位ビットがvectorの先頭に来ているので逆順に表示していきます。
    for (auto t = trit.rbegin(); t != trit.rend(); ++t) {
        if (isNegative) {
            switch (*t) {
            // 1と2は反転させ、0はそのまま表示。
            case 1:
                cout << 2;
                break;
            case 2:
                cout << 1;
                break;
            default:
                cout << *t;
            }
        }
        else {
            cout << *t;
        }
    }
    
    cout << endl;
    return 0;
}

レイミちゃんの反応

結構感想やフィードバックが的確で、今のAI技術ってやっぱすごいなと改めて思いました。

レイミちゃん、かわいいね

問題の感想

今までやっていた処理をどのように別の場面に当てはめるかといったパズル要素のある面白い問題だと思いました。ただ、他のCランク相当の問題と比べるとここだけ異様に難しい気はしました。（B～Aランク相当はある気がします。）でも、解けたときはこの問題を解説したいと思うくらいには爽快感がありました。

ゲーム全体としては楽しい時間を過ごさせていただきました～

とはいってもN.Mは競プロやったことないんですけどね。paizaのプログラミングの問題は就活の時とかにやってました。 ↩
このゲームではプログラミング以外にもMySQLのクエリ文の問題が出てきますが、最近データベースをいじる機会があったので、普通にクエリ文を書けました。 ↩
この手のパズル的な問題は簡単な例で実際に手を動かして試し、法則を見つけるのが良いと高校数学で教わりました。 ↩