アルゴリズム::白駿::Breutforce,グリンディ::1339:単語数学

16197 ワード
白駿 アルゴリズム#アルゴリズム# bruteforce グリディ テキストリンク

1.問題の分析


1.1. 問題の意図.

  • これは、すべての場合において、まず個数を求め、次に最適解を求めるBrutforce問題である.

    • 2.問題解決

  • この問題には2つの解決方法があります.
  • Breutforceメソッド:最大10文字なので10!=1,034,76810! = 1,034,76810!=すべての1034768を見つけたら、最適な解を探します.
  • Greedyメソッド:大きな数字を高桁数のアルファベット順に割り当てる

    • 1.Breutforceメソッド

  • N個の単語を読み出し、出現したすべてのアルファベットを取得する.
  • この場合、アルファベットがAから順番に現れるとは限らない!QまたはZなどのアルファベットも表示されます.注意!
  • は、出現するアルファベットに0から9を付与する.
  • next_permutation()関数を使用してすべての組合せの和を計算します
  • 合計の最大値.

    • 2.Greedyメソッド

  • N個の単語を読み出し、出現するアルファベットに数字の桁数を追加します.
  • GAFA = alpha[‘G’ - ‘A’] = 1000 , alpha[‘A’ - ‘A’] = 100 , alpha[‘A’ - ‘F’] = 10 , alpha[‘A’ - ‘A’] = 101
  • alpha昇順に並べます.
  • alphaアレイは、末尾から9、8、および7を乗じる.
  • GCF + ACDEB
  • A( alpha[0] ) = 10,000
    B( alpha[1] ) = 1
    C( alpha[2] ) = 1,010
    D( alpha[3] ) = 100
    E( alpha[4] ) = 10
    F( alpha[5] ) = 1
    G( alpha[6] ) = 100
  • ソート0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 10 100 100 1010 10000
  • 9,8,7…代入
  • 90000 + 8080 + 700 + 600 + 50 + 4 + 3 = 99437

    • 3.コード


    1.Breutforceメソッド

    #include <iostream>
#include <algorithm>
using namespace std;

int N, alpha[26], mappingTable[10], answer;
char words[10][9];

int cvt2Num(char str[9]) {
	int ret = 0, idx = 0;
	while (str[idx] != '\0') ret = ret * 10 + mappingTable[alpha[str[idx++] - 'A']];
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
    	// alpha와 mappingTable 배열 초기화
	for (int i = 0; i < 26; ++i) alpha[i] = -1;
    	for (int i = 0; i < 10; ++i) mappingTable[i] = i;
    	// 단어 입력받기.
	for (int i = 0, k = 0; i < N; ++i) {
		int j = 0;
		cin >> words[i];
        	// words[i] 속 알파벳이 mappingTable의 k번째 인덱스에 매핑.
		while(words[i][j] != '\0') {
			if (alpha[words[i][j] - 'A'] == -1) alpha[words[i][j] - 'A'] = k++;
			j++;
		}
    	}	
	do {
		int sum = 0;
		for (int i = 0; i < N; ++i) sum += cvt2Num(words[i]);
		answer = max(answer, sum);
	} while(next_permutation(mappingTable, mappingTable + 10));
	cout << answer;
}

    2.Greedyメソッド

    #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N, len, ans, alphabet[26];
int main() {
	char str[9];
	scanf("%d", &N);
	while (N--) {
		scanf("%s", str);
		len = strlen(str);
          	// 모든 단어 속에서 특정 알파벳이 위치했던 자릿수를 더한다.
		for (int i = len - 1, j = 1; i >= 0; --i, j *= 10)
			alphabet[str[i] - 'A'] += j;
	}
	sort(alphabet, alphabet + 26);
	for (int i = 0; i < 10; ++i) ans += alphabet[25 - i] * (9 - i);
	printf("%d", ans);
}

    4.結果


    1.Breutforceメソッド



    2.Greedyメソッド


    URL短縮符号化、10ビットと64ビットの変換
    [アルゴリズム]迷宮探索2178py - BFS