「限られた数字で作れる数の、まんなかの値」を求めたい。

Question

###前提・実現したいこと
「限られた数字で作れる数の、まんなかの値」を求めたいです。
例えば，
0, 4, 5以外の数を使わずに作ることができる3桁以下の非負の整数は，
0, 4, 5, 40, 44, 45, 50, 54, 55, 400, 404, 405, 440, 444, 445, 450, 454, 455, 500, 504, 505, 540, 544, 545, 550, 554, 555
の27個です。
中央は14番目の数なので、求める値は444になります。
入力は，
3 045(桁数␣使える数)
という感じです。
出力は，
444
のように，中央の値を出力します。
作れる数が偶数個の場合には、中央に近い数を2つ，小さい順にコンマ区切りで並べます。
なお，桁数の上限の最小値は1。最大値は15です。
不正な入力に対処する必要はありません。

入力	出力
15 12345789	444444444444444,444444444444445
15 123456789	494949494949495
15 0123456789	499999999999999,500000000000000

ソースコードを提示していただければ自分で解読します。
アルゴリズムのヒントでもいいので教えていただけると幸いです。

###発生している問題・エラーメッセージ
処理に時間がかかりすぎて終わりません。

###該当のソースコード

#include <iostream>
#include <string>
#include <vector>
void median(std::vector<std::string> *str, const std::string &number, const int &digit, const std::string &buffer = "", const bool &flag = false) {
	if (digit > 0) {
		if (flag == false && digit > 1 && number.front() > '0') {
			median(str, number, digit - 1, buffer + '0');
		}
		for (const char c : number) {
			median(str, number, digit - 1, buffer + c, true);
		}
	}
	else if (digit == 0) {
		str->push_back(buffer);
	}
	return;
}
int main(void) {
	int digit;
	std::string number;
	while (std::cin >> digit >> number) {
		std::vector<std::string> str;
		//m:組み合わせの数
		/*
		long long int m = 0;
		if (number.front() > '0') {
			for (int i = 1; i < digit; ++i) {
				m += pow(number.size(), i);
			}
		}
		m += pow(number.size(), digit);
		*/
		median(&str, number, digit);
		if (str.size() % 2 == 0) {
			std::vector<std::string>::const_iterator itr = str.cbegin();
			std::advance(itr, str.size() / 2 - 1);
			std::cout << *itr << "," << *(itr + 1) << std::endl;
		}
		else {
			std::cout << str.at(str.size() / 2) << std::endl;
		}
	}
	return EXIT_SUCCESS;
}

###試したこと
数を文字列として扱い，組み合わせをすべて探索して，そこからまんなかの値を求めました。
ソースコード中にあるように組み合わせの数は求めることができます。
この問題は自分も最初勘違いしていましたが，使用できる数に「0」がなくても空白は使用できるようです。

###補足情報(言語/FW/ツール等のバージョンなど)
言語:C++11

Comments

[MasahikoHirata]

入力の意味を理解するまで時間がかかった。’桁数’＋’空白’+’使える数字’と説明があれば理解しやすいですね。

[matsu]

入力の最初の数字は桁数、2つ目はどの数字を使うか、ということで良いですかね

[MasahikoHirata]

matsuさん、質問者が問題を修正され、その通りの出題です。

Answer 1

アルゴリズムのプロトタイピングにPython言語を使ってみました。基本的な考え方は次の通りです。

• 「使う数字の個数」を基数(raidx)とみなす。つまりn桁のradix進数として中央値を考える。
• 「使う数字」に0が含まれない場合、長さがn桁未満の組合せ総数をカウントし(offset)中央値計算時のオフセットとする。
• 「使う数字」に0が含まれる場合、n桁のradix進数数え上げにて既にn桁未満の数を含むため、オフセットを調整する。（入力が3 045のとき、総数radix ** nには004, 005, ...が計上されている）

n = 15
a = list("12345789")

# 10進数値valueを"使う数値からなるradix進数"で再構築
def dump(value):
  result = ""
  while 0 < value:
    result = a[value % radix] + result
    value = value // radix
  print(result)

radix = len(a)  # 基数

offset = 0
if not '0' in a:
  # offset = Σ_{i=0}^{i < n} (radix ^ i)
  offset = sum([radix ** i for i in range(n)])
else:
  offset = 1

# 中央値を計算(10進数)
median = (radix ** n - offset) // 2

if radix % 2 == 0:
  dump(median)
  dump(median + 1)
else:
  dump(median)

Comments

[yohhoy]

余談ですが「使用できる数に「0」がなくても空白は使用できる」は私も騙されました。というか競技プログラミング（？）的には暗黙に読み取るべき仕様なんすねコレ...

[raccy]

入力と出力の例が3つあるので競プロ勢ならそこら辺から読み取るもんなのかなと思ってます。答えがどうしても合わなくて、私も最初悩みまくってしまいましたが…。

[MasahikoHirata]

さすが、C++でコーディングしている間に、見やすい答え。

[s8079]

Pythonは初めてなので少し説明がほしいのですが，dump関数の中はどうなっているのでしょうか。

[yohhoy]

dump関数では 10進数→radix進数変換 を行なっています。Python版をC++に置き換えると概ね次のような感じです（コメント内でインデント表現のため全角空白を使っています）：

std::vector<char> a = { 使う数値を文字単位で格納 };
size_t radix = a.size();

void dump(uint64_t value) {
　std::string result;
　while (0 < value) {
　　result = a[value % radix] + result;
　　value = value / radix;
　}
　std::cout << result;
}

追記：たしかにPythonの「//」演算子は説明が要りますね... 整数同士の切り捨て除算（例: 5/2 == 2）を行いますから、C++だと普通に整数型同士の除算「/」に置き換えられます。

[s8079]

Pythonでは「/」も「//」も除算なんですね。
解決しました。

Answer 2

ソースを書いている内に、考え方はyohhoyさんが書いてしまったので、ソースだけです。Rubyですけど。

n_s, list_s = gets.split
n = n_s.to_i
list = list_s.chars.sort
base = list.size
max_n = base**n
pattern_num = max_n
(1...n).each { |x| pattern_num += base**x } unless list.include?('0')
middle_list = [max_n - pattern_num / 2 - 1]
middle_list << middle_list[0] + 1 if pattern_num.even?
puts(middle_list.map do |num|
  num.to_s(base).chars.map(&:to_i).map { |i| list[i] }.inject(&:+)
end.join(','))

実は0を含んだ方が簡単です。なぜなら、そのままn桁のbase進数と見なせてしまうので。"000...0001"は"1"に集約されるので、それぞれの桁を数える必要は無くなります。

Answer 3

メモ的に考えをまとめてみます。

---

問題点：

• 中央値を正しく計算できていない（これは必ず15ケタ以下になるはずのため）

---

方向性：

• 該当のリストが総数いくつになるか計算し半分の数を出す
• 上記番目の数字を出力する

---

課題：

• リストの数は[使える数の数]乗の[桁数]になる
• 使える数が奇数の場合、使える数の中央値を連続したものがリストの中央値になる？
• 使える数が偶数の場合は最大値を半分にした数が中央値になる？

Comments

[raccy]

問題点は「処理に時間がかかりすぎて終わりません。」です。質問にも明記されています。

[matsu]

すみません。そこ、端折りました。出力結果を見た際、指定桁数以上の値がでているようだったので必要以上の計算をしているであろうと判断しました。
ですが、. ではなく , が使われていることに今気付きました。

Answer 4

とりあえず０を考えない場合の基本的な考え方だけ提案します。
桁数 = K, 使える数の種類 = N とします。

各桁の組み合わせの数
1桁 : N
2桁 : N^2
:
K桁 : N^K
総数 : N + N^2 + ...+ N^K となります。
よって、求める中間値が何桁目(k)の先頭から何番目(x)に位置するかは簡単に計算できます。
あとはk桁目の組み合わせを辞書順にx番目まで走査（列挙）すればよいです。
また、この走査も、k桁目の組み合わせの総数は N * N^(k-1) という法則（部分解）を利用すれば
実際の列挙（数字の作成）もかなり端折ることができます。

おそらく０を含む場合の各桁の組み合わせの数も簡単な式で表せると予想しています。

Comments

[s8079]

確かにx番目までの走査で良いです。
しかし，この問題は組み合わせの最大が1000兆通りになります。
したがって，x番目までの走査でも500兆通り試さなければなりません。

[can110]

編集した回答に追記したのですが、部分解を使えば実際の走査もかなり端折る（ジャンプする）ことができます。
例えば12345の３桁の組み合わせ からx番目までジャンプしたい場合
"1"始まりの総数 (＝２桁の組み合わせの総数）=sum1を超える？→とばす
+"2"始まりの総数(＝２桁の組み合わせの総数）=sum2 超える？→超えない
この位置から2桁の組み合わせ総数のx-sum1+sum2番目を探す
といった感じです。

[can110]

０を含む場合は、０が左端にくる場合のみを除けばよいので
1桁 : (N-1)
2桁 : (N-1) * N
:
K桁 : (N-1) * N^(K-1)
総数 : (N-1) + (N-1) * N + ...+ (N-1) * N^(K-1) でよさそうですね。

[can110]

スマートな回答出ましたね。
こんな考えでもできるという提案までで閉めます。

Answer 5

考え方をまとめてみる。
入力は桁数、使える数字である。
使える数字に’０’があった場合、頭が’０’のものは’０’だけである。（解の１つ）
後は桁数になる数字の組み合わせをカウントして、その組み合わせ数が前述の’０’が選択できる数字にある場合は＋１して偶数か奇数かを判断し、それを算出する。

15桁までという事を考えてlong long intで処理してみる。

#include <iostream>
#include <string>
#include <vector>
unsigned char used_number[10];　　　// 使用数字　0=not used,1=used

long long int check_number(int digit)
{
    long long int work;
    if( digit == 1 )
    {
        for(int i = 0,work = 0LL;i <10;i++)
            if(used_number[i] != 0)
                work++;
        return work;
    }
    for(int i = 0;i<10;i++)
        work += check_number(digit-1);
　　if(used_number[0] == 1) // 頭が’0’場合、その数を引く
        work -= number_of_count;
    return work;
}
long long int calc_number(int digit,long long int current_pos,long long int result_pos)
{
    long long work;
    if( digit == 1)
    {
        for(int i = 0,work = 0LL;i<10;i++ )
        {
            if(used_number[i] != 0 )
            {
                if(work == result_pos )
                {
                    cout << used_number[i] ;
                    return;
                }
            }
        }
        return work;
    }
    for(int i = 0;i<10;i++)
    {
        current_pos += calc_number(digit-1,current_pos,result_pos);
    }
　　if(used_number[0] == 1) // 頭が’0’場合、その数を引く
        current_pos -= number_of_count;
    return current_pos;
}

int main(void) {
    int digit;
    std::string number;
　　long long int work;
    int number_count;
    long long int count_of_result=0LL;

    std::cin >> digit >> number；

    if((digit <= 0) || ( digit >15))
    {
       cout << "Illegal number" << endl;
       return -1;
    }
// 重複確認
    for(int i = 0;i<10;i++)
        used_number[i]= 0;
    for(int i = 0,number_count =0;i<strlen(number);i++)
    {
        if((number[i] >= '0')&&(number[i] <='9'))
        {
            if( used_number[(number[i]-'0')] == 0 )
            {
                number_of_count++;
                used_number[(number[i]-'0')]=1;
            }
        }
        else {
            cout << "Illegal number" << endl;
            return -1;
        }
    }
// 解の数を算出
    work = check_number(ditit);
//
    if( work & 1 )    //解が奇数
    { // 答えは２つ
       cout << calc_number(work/2) << "," << calc_number((work/2)+1) << endl;
    } else
    { // 答えは１つ
        cout << calc_number(work/2) << endl;        
    }
}

机上なのでバグあるだろうなぁ。

Comments

[MasahikoHirata]

桁数が15桁までで、C++なので無理に文字列ではなくてlong long int型を使ってと考えてコーディング中。

Answer 6

数字でなく文字列として処理するといいと思います。

１ 該当する文字列の集合を作る。
２ ソートする。
３ 中央のものを選ぶ。

まあ、集合を作らずに答えを導けるならば、なお良いですね。

Comments

[s8079]

すでに数字でなく文字列として処理しています。