オフラインリアルタイムどう書く E24 の実装例（腕力版）

問題 : http://nabetani.sakura.ne.jp/hena/orde24tancho/
実装リンク集 : https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7

で。

想定解の一つだったけど、参加者は（私以外）だれも書かなかったやつ。
腕力版。

まずは C++

```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: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: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 はどうなんだろ。未調査ですすいません。