Tävlingsprogrammering/Uppgifter/Bokstavstärningar
Lösning
redigeraDe 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;
}