問題 : http://nabetani.sakura.ne.jp/hena/orde24tancho/
実装リンク集 : https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7
で。
想定解の一つだったけど、参加者は（私以外）だれも書かなかったやつ。
腕力版。
まずは C++
c++
# include <iostream>
# include <cstdio>
# include <cstdlib>
# include <memory>
# include <cstring>
# include <array>
# include <cstdint>
# include <ctime>
using namespace std;
int64_t maxvalue( int base )
{
uint64_t r=0;
for( int i=1 ; i<base ; ++i ){
r*=base;
r+=i;
if ( (int64_t)r<0 ){
return 0x7fffffffffffffff;
}
}
return r;
}
std::string to_str(int64_t num, int base )
{
std::string s;
s.reserve(base+1);
while( num ){
s+="0123456789abcdefghijklmnopqrstuvwxyz"[num%base];
num/=base;
}
reverse( s.begin(), s.end() );
return s;
}
bool is_mono( int64_t num, int base )
{
std::string str = to_str(num,base);
for( int i=0 ; i<str.size()-1 ; ++i ){
if ( str[i+1]<=str[i+0] ){
return false;
}
}
return true;
}
std::string solve( int base, int order )
{
int count=0;
if ( (1LL<<(base-1)) < order ){
return "-";
}
int64_t max = maxvalue(base);
for( int64_t i=1 ; i<=max ; ++i ){
if ( is_mono(i,base) ){
++count;
if ( count==order ){
return to_str(i, base);
}
}
}
return "-";
}
void test( char const * src, char const * expected )
{
int base, order;
sscanf( src, "%d,%d", &base, &order );
time_t start = time(0);
std::string actual = solve( base, order );
double tick = time(0) - start;
bool okay = actual == expected;
cout << (okay ? "ok" : "**NG**") <<" " << tick << " " << src << " " << actual << " " << expected << std::endl;
}
int main()
{
/*0*/ test( "16,333", "38e" );
/*1*/ test( "2,100", "-" );
/*2*/ test( "2,1", "1" );
/* 中略 */
/*56*/ test( "36,44811", "abpu" );
}
そして Go の実装
go実装
package e24
import (
"strconv"
"strings"
)
func maxvalue(base int) int64 {
r := int64(0)
for i := 0; i < base; i++ {
r *= int64(base)
r += int64(i)
if r < 0 {
return 0x7fffffffffffffff
}
}
return r
}
func isMono(num int64, base int) bool {
str := strconv.FormatInt(num, base)
for i := 0; i < len(str)-1; i++ {
if str[i+1] <= str[i+0] {
return false
}
}
return true
}
func impl(base, ord int) int64 {
count := 0
if (int64(1) << uint(base-1)) < int64(ord) {
return 0
}
max := maxvalue(base)
for i := int64(1); i <= max; i++ {
if isMono(i, base) {
count++
if count == ord {
return i
}
}
}
return 0
}
func solve(src string) string {
nums := strings.Split(src, ",")
base, _ := strconv.Atoi(nums[0])
ord, _ := strconv.Atoi(nums[1])
ans := impl(base, ord)
if ans == 0 {
return "-"
}
return strconv.FormatInt(ans, base)
}
Go のテスト
goテスト
package e24
import "testing"
func TestMaxValue(t *testing.T) {
got := maxvalue(10)
if got != 123456789 {
t.Errorf("maxvalue(10)=%d want %d", got, 123456789)
}
}
func TestIsMono(t *testing.T) {
got1 := isMono(int64(12345678), 10)
if got1 != true {
t.Errorf("isMono(12345678)=%v want %v", got1, true)
}
got2 := isMono(int64(12345578), 10)
if got2 != false {
t.Errorf("isMono(12345578)=%v want %v", got2, true)
}
}
func Test(t *testing.T) {
var tests = []struct {
name string
input string
want string
}{
{"0", "16,333", "38e"},
{"1", "2,100", "-"},
{"2", "2,1", "1"},
// 中略
{"56", "36,44811", "abpu"},
}
for _, test := range tests {
got := solve(test.input)
if got != test.want {
t.Errorf("%v: solve(%q)=%q, want %q\n", test.name, test.input, got, test.want)
}
}
}
解答の値を N とすると、O(Nlog(N)) ぐらいだと思う。大変遅い。
遅いんだけど、手元のマシンで C++ で 1分、Go で 30秒ぐらい。
C++ 大好きな私としては C++ のほうが遅いのがなんか納得行かない。std::string を使ったのが敗因かなと思っているけど調べていない。
ruby で同等の実装をすると、10分ぐらいなので、会場で実装に 30分かけても一時間に収まる感じで、勝利。
という想定でテストデータを作ったんだけど、誰も書かなかった。
速い拙実装は https://qiita.com/Nabetani/items/800c127e5ed9cb0ca207 を参照のこと。
6月2日 追記
ininsanus さんの指摘(ありがとうございます)
https://twitter.com/ininsanus/status/1001647161677762560
の通り、符号付き整数のオーバーフローがきれいに計算されることを期待したコードになっていることが原因で、g++ では正しく動作していなかった。
ので、修正した。
具体的には、maxvalue で r が int64t だったのを uint64_t に変更した。
テストしていたのは clang++。
g++ は違うんだなぁと思った。
あと。Go はどうなんだろ。未調査ですすいません。