単調増加数 (Ruby / AIR-lang / Python)

問題	http://nabetani.sakura.ne.jp/hena/orde24tancho/
Ruby / AIR-lang / Python	https://qiita.com/cielavenir/items/6de720c9a12813c5f469
Perl / C / Crystal / D / Go	https://qiita.com/cielavenir/items/51f260519b62a3330234
Ruby-alpha	https://qiita.com/cielavenir/items/9048c60498a9385b25c0

前説

第24回の追加答案で勢いづいたため今回はしょっぱなから「ツインテールdeエンジェルモード!!」での参戦にしようと思いましたが、やはり少し厳しかったようです。
Rubyからの移植になります。

方針

単調増加ということは、組み合わせだけ考えて、出力時にソートしたことにすれば良いです。
あとはHKDnetさんの解説が近いです。

感想

シンプルなのに、立式するのが今回すごく大変でした…(オンサイトだったら 土 です)

ちなみに、全答案、テストケース

/*100*/ test('36,30000000000','134689bdefhijkrstuwyz');

を1秒以内で突破できます。これが突破できる答案が意外と少ないような…

Ruby

tyama_henae24.rb

#!/usr/bin/env ruby
#http://nabetani.sakura.ne.jp/hena/orde24tancho/
#https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7

def comb(n,k)
    r=1
    k.times{|i|
        r=r*(n-i)/(i+1)
    }
    r
end

STDOUT.sync=true
while gets
    b,n=$_.chomp.split(',').map{|e|e.to_i-1}
    topdigit=1
    loop{
        #b種類で作れるitopdigit桁の数
        x=comb(b,topdigit)
        break if b<topdigit || x>n
        n-=x
        topdigit+=1
    }
    if b<topdigit
        puts :-
        next
    end
    topdigit-=1
    curnumber=0
    topdigit.downto(0){|d|
        curnumber+=1
        loop{
            #b-curnumber種類の数で作れるd桁の数
            x=comb(b-curnumber,d)
            break if x>n
            n-=x
            curnumber+=1
        }
        print curnumber.to_s(b+1)
    }
    puts
end

Twintail

tyama_henae24.tt

#!/usr/bin/env tt
#http://nabetani.sakura.ne.jp/hena/orde24tancho/
#https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7

def comb(n,k){
    r=1
    for(i=0;i<k;i++){
        r=r*(n-i)/(i+1)
    }
    retn(r)
}

while(line=gets()){
    _=split(line,',')
    b=int(_[0])-1
    n=int(_[1])-1
    topdigit=1
    for(;1;){
        x=comb(b,topdigit)
        if(b<topdigit || x>n)break
        n-=x
        topdigit++
    }
    if(b<topdigit){
        print("-\n")
        continue
    }
    topdigit-=1
    curnumber=0
    for(d=topdigit;d>=0;d--){
        curnumber++
        for(;1;){
            x=comb(b-curnumber,d)
            if(x>n)break
            n-=x
            curnumber++
        }
        print("%c",curnumber+(curnumber<10 ? 48 : 87))
    }
    print("\n")
}

Python

• いつもながら Py2/3両対応です

tyama_henae24.py

#!/usr/bin/env python
#http://nabetani.sakura.ne.jp/hena/orde24tancho/
#https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7
from __future__ import print_function,division
import string
o = string.digits+string.ascii_letters

def comb(n,k):
    r=1
    for i in range(k):
        r=r*(n-i)//(i+1)
    return r

if __name__=='__main__':
    import sys
    if sys.version_info[0]>=3: raw_input=input
    try:
        while True:
            b,n=[int(e)-1 for e in raw_input().rstrip().split(',')]
            topdigit=1
            while 1:
                x=comb(b,topdigit)
                if b<topdigit or x>n: break
                n-=x
                topdigit+=1
            if b<topdigit:
                print('-')
                sys.stdout.flush()
                continue
            topdigit-=1
            curnumber=0
            for d in range(topdigit,-1,-1):
                curnumber+=1
                while 1:
                    x=comb(b-curnumber,d)
                    if x>n: break
                    n-=x
                    curnumber+=1
                print(o[curnumber],end='')
            print()
            sys.stdout.flush()
    except EOFError:
        pass