Tävlingsprogrammering/Uppgifter/Bokstavstärningar

Se problemet

Lösning

De olika fallen har faktiskt helt olika lösningsmetod. Att få 65 poäng var ganska enkelt. Man bara går igenom alla 6!=120 sätten att ordna tärningarna och, för varje ord, kollar om varje bokstav i ordet finns på den tärningen som man bestämt ska ha den platsen i ordet. Den kollen kan göras blixtsnabbt om man lagrat i en boolsk (true/false) array huruvida varje bokstav finns på tärningen eller ej. Att generera ordningarna (permutationerna) kan göras med biblioteksfunktioner i vissa språk (t.ex. next_permutation i C++) eller med hjälp av en enkel rekursiv funktion som i lösningen nedan.

Lösningsförslag i C, brute force (65p):

#include <stdio.h>

char tar[20][21];
char ord[100000][21];
int occurs[20][256];
int taken[20],t[20];
int tot;
int found[100000];
int N,K,M;

void MLX(int nr) {  // Rekursiv funktion som genererar alla permutationer av talen 0..(N-1)
  int i,j;
  if(nr==N) {   
    for(i=0;i<M;i++) if(!found[i]) {    // Gå igenom alla orden. Kolla ordet om det inte redan har hittats i någon annan permutation.
	for(j=0;j<N;j++) if(!occurs[t[j]][ord[i][j]]) break;
	if(j==N) {
	  tot++;
	  found[i]=1;
	}
      }
  }
  else {
    for(t[nr]=0;t[nr]<N;t[nr]++) if(!taken[t[nr]]) {
	taken[t[nr]]=1;
	MLX(nr+1);
	taken[t[nr]]=0;
      }
  }
}

int main() {
  char c;
  int i,j;
  scanf("%d %d %d", &N, &K, &M);
  
  for(i=0;i<N;i++) {
    for(c='A';c<='Z';c++) occurs[i][c]=0;    
    scanf("%s", tar[i]);
    for(j=0;j<K;j++) occurs[i][tar[i][j]]=1;   //Spara huruvida varje bokstav finns på tärningen, för snabb åtkomst sedan.
    taken[i]=0;
  }
  for(i=0;i<M;i++) {
    scanf("%s", ord[i]);
  }
  tot=0;
  MLX(0);
  printf("%d\n", tot);
  return 0;
}

För den sista testgruppen blir det dock alldeles för många ordningar för att kolla alla. Men lyckligtvis fanns det inte så många ord i de fallen. För varje ord handlar det ju om att matcha ihop en bokstav i ordet med en tärning. Man kan då använda standardalgoritmen för bipartit matchning, som exempelvis finns beskriven på GeeksforGeeks eller på vår egen gamla träningssajt.

Lösningsförslag i C++:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void PR(vi &v) { trav(x, v) cout << x << ' '; cout << endl; }

int main() {
	cin.sync_with_stdio(false);
	int N, K, M;
	cin >> N >> K >> M;
	vector<string> dice(N);
	vector<int> masks(N);
	rep(i,0,N) {
		cin >> dice[i];
		int m = 0;
		rep(j,0,K) m |= 1 << (dice[i][j] - 'A');
		masks[i] = m;
	}
	string word;
	int res = 0;
	rep(i,0,M) {
		cin >> word;
		vi reachable(1 << N), reachable2;
		reachable[0] = 1;
		rep(j,0,N) {
			reachable2.assign(1 << N, 0);
			int c = word[j] - 'A';
			rep(m,0,(1 << N)) {
				if (!reachable[m]) continue;
				rep(k,0,N) {
					if (!(masks[k] & 1 << c)) continue;
					if (m & (1 << k)) continue;
					reachable2[m | 1 << k] = 1;
				}
			}
			reachable.swap(reachable2);
		}
		bool works = reachable[(1 << N) - 1];
		if (works)
			res++;
	}
	cout << res << endl;
}