ntk log ntk

競プロや非競技プロのやったことを書いています.

Codeforces Round #595 (Div. 3) C2. Good Numbers (hard version)

C2. Good Numbers (hard version)

バチャをした.4か月くらい前にも解いたのだけれど,3ペナ出した.うーん.

整理のために言語化しておく.

問題概要

n以上の整数のうちで,最も小さな「良い数」mを出力せよ,というクエリがいくつか与えられる.整数nはクエリごとに与えられる.「良い数」の条件は,異なる3の累乗数のみの和で表せる,である.例えば,4は30 + 31と異なる3の累乗数のみの和で表せるので良い数であり,2は30 + 30のように異なる3の累乗数のみの和では表せないので良い数でない.

解法

与えられた整数nを3進数に直す.このとき,'0'か'1'のみからなる3進数であれば異なる3の累乗数のみの和で表せている.例えば,12は3進数に直すと110_{(3)}であり,12 = 3^2 + 3^1でもあるから「良い数」である.逆に3進数に変換したときに'2'が存在すると,異なる3の累乗数の和では表せない.例えば,15は3進数だと120_{(3)}である.31が2つ(15 = 3^2 + 2 \times 3^1)や,30が6つ(15 = 3^2 + 6 \times 3^0)は必要であり,15は異なる3の累乗数のみの和では表せない.よって,'2'があれば,その桁に'1'を足して繰り上げるようにする.繰り上げた時点で,元の数nより大きくなるので,'2'があった桁と,それより小さい桁はすべて0にしてよい.このようにして構成した3進数を10進数に直したものが答え.

サンプル

input:96

output:108

それぞれ3進数に直すと,10120_{(3)}11000_{(3)}

実装

解法の前半はその通りに,3進数に直す.cnv_baseという基数変換の関数を書いた.解法の後半は実際に3進数を保持するのではなく,10進数の計算結果だけ持てばよい.r_cnvという関数を作成した.

コード

def main():
    def cnv_base(n, base):
        if n == 0:
            return 0
        digits = []
        while n != 0:
            digits.append(str(n % base))
            n //= base
        return "".join(digits)

    def r_cnv(S):
        d = 1
        ret = 0
        carry = 0  # 繰り上がり
        for s in S:
            v = int(s)
            if carry == 0:
                if v <= 1:
                    # 0か1なら足す
                    ret += v * d
                else:
                    # 繰り上げる
                    carry = 1
            else:
                ret = d
                # 繰り上がりがあったら,繰り上げた桁に1をたてる
                # 10120で考えてみるといいかもしれない
                # s = "2"でcarry = 1になったあと始めてret = d
                # が行われて,ret = 9になる.9は3進数に直すと100_{(3)}
                if v == 0:
                    carry = 0
                # else v が 0でないとさらに繰り上がりが起きる
            d *= 3
        if carry:
            # 117 = 11100_{(3)}のように繰り上げたときに100000になると
            # forの外にもif文が一つ必要
            ret = d
        return ret

    Q = int(input())
    for _ in range(Q):
        N = int(input())
        S = cnv_base(N, 3)
        print(r_cnv(S))  # , cnv(r_cnv(S)))


if __name__ == '__main__':
    main()

提出コードへのリンク


上手く言語化できた気がしないな….おおまかな考察が進んだ後に,きれいな実装ができないのは考察を詰め切れていないからな気がする.ただその考察を詰め切るのが難しい…….

記事ツイートしたら反応もらった.bbgeさんすげ~~~になっています.簡潔な解法.こういう風にやるとわざわざ3進数に直さなくてよい.