単調増加数 (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