AOJ 0246 Bara-Bara Manju

問題文

Bara-Bara Manju

感想

難しいが良問。去年の予選終わったあと、バックトラックとかしてて泥沼にはまってしまって、わかんなかったのでsemiexp先生に解法教えてもらった。

ただAOJのテストケース厳しいナァ。

ほかの人たぶん違う解法をしていて気になる。



解法

  • とりあえず10を作れるパターンを全列挙しておけば、そのパターンを何個使うか?みたいなナップサック問題みたいなのに帰着できるのでそうしとく。
  • しかし,ナップサックDPが厳しそうに見える。
  • が、2個の饅頭だけ使って10を作りまくるのはちょっと考えると最善なので、それをまず貪欲する。つまり(1,9),(2,8),(3,7),(4,6),(5,5)の組について試す。
  • この操作をした後、それぞれの組の片方の饅頭の数は必ず0になる。ただし、(5,5)についてはは1個余るか全部なくなる。
  • つまり、大雑把に状態数O(100^9)のDPがO(100^4*2=2億)の状態数になる。
  • が、実際に饅頭の数は高々100個なので、このテーブルには穴だらけなので速そう。なのでメモ化探索すればよい。
  • でも残りの饅頭の状態を手抜きして配列で持ってmapにつっこんだりすると、AOJではMLE,TLEする。
  • そこで7bit区切りで9個の饅頭についての残り数を7bit区切りでlong longに突っ込んでそれを状態として扱う。
  • すると、通る。

ソース

#include <iostream>
#include <vector>
#include <map>
using namespace std;
  
map< pair<int,long long>, int>  dp;
vector< long long > e;
  
void gen_pattern(int pos,int r,long long v){
    if( pos >= 10 ){
        if( r == 0 ){
            e.push_back( v );
        }
        return;
    }
    for(int i = 0 ; r - pos * i >= 0 ; i++){
        gen_pattern(pos+1,r - pos*i,v+((long long)(i)<<((pos-1)*7)));
    }
}

int dfs(int pos,long long v){
    if( pos >= e.size() ) return 0;
    if( dp.count(make_pair(pos,v)) ) return dp[make_pair(pos,v)];
    long long V = v;
    int ans = 0 , c = 0;
    while(1){
        ans = max( dfs(pos+1,v) + c , ans);
        c++;
        bool f = true;
        for(int i = 0 ; i < 9 ; i++){
            int s = v >> (7*i) & 127;
            int x = e[pos] >> (7*i) & 127;
            if( s < x ){
                f = false;
                break;
            }
        }
        if( !f ) break;
        v -= e[pos];
    }
    v = V;
    return dp[make_pair(pos,V)] = ans;
}
  
  
 
int main(){
    int n;
    gen_pattern(1,10,0);
    while(cin >> n && n){
        vector<char> v(10);
        for(int i = 0 ; i < n ; i++){
            int t;
            cin >> t;
            v[t]++;
        }
        int greedy = 0;
        for(int i = 1 ; i < 5 ; i++){
            int u = min(v[i],v[10-i]);
            greedy += u;
            v[i] -= u; 
            v[10-i] -= u;
        }
        greedy += v[5] / 2;
        v[5] %= 2;
        long long enc = 0;
        for(int i = 1 ; i < 10 ; i++){
            enc += (long long)(v[i]) << (7 * (i-1));
        }
        dp.clear();
        cout << dfs(0,enc)+greedy << endl;
    }
}