SRM516 Div1 Medium(500) RowsOrdering

RowsOrdering

Example 0の{"bb", "cb", "ca"}は、1番目cb、2番目bb、51番目caと並べるのが最善。これを、1列目によってcbの順位が+0、bbの順位が+1、caの順位が+0され、2列目によってcbの順位が+0, bbの順位が+0、caの順位が+50されると考える。そうすると、それぞれの列について分けて考えることができる。

各列では多く出現する文字を前にするのが最善。

ある列iを最後に選ぶ場合の順位への寄与の和（下のプログラムでのcont[i]）をxとすると、列iをk番目に選んだときの順位への寄与は50^M-kx。列は順位への寄与の大きい順位に選んでいくのが最善。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class RowsOrdering{public:
int order( vector <string> rows )
{
    long long mod = 1000000007;
    int n = (int)rows.size();
    int M = (int)rows[0].size();
    
    vector<int> cont(M);

    for ( int i=0; i<M; i++ )
    {
        int c[256] = {0};
        for ( int j=0; j<n; j++ )
            c[(int)rows[j][i]]++;
        sort(c,c+256);
        cont[i] = 0;
        for ( int j=0; j<n; j++ )
            cont[i] += c[255-j]*j;
    }

    sort( cont.begin(), cont.end() );

    long long ans = 0;
    long long p = 1;
    for ( int i=0; i<M; i++ )
    {
        ans += cont[M-i-1]*p;
        ans %= mod;
        p *= 50;
        p %= mod;
    }

    ans += n;
    ans %= mod;

    return (int)ans;
}};