Hatena::Grouptopcoder

nase@topcoder

2011-09-17

SRM517

16:20

Div1 Easy CompositeSmash

さくっと再帰で書いて提出。238点。

一応TLEのチェックをしておくかと、100000, 3を入れたらなんとYesが返ってきやがる。

がーん、Mediumが600点問題でEasy勝負と思って気合入れてたのにやってしまった。。

再提出して186.80点に沈む。

Div1 Medium AdjacentSwaps

問題はシンプルだが最初は全く解ける気がしなかった。

「分からない時はサンプルを吟味」の格言?を実行。

サンプル2の解が2になることから解答の大ヒントに気づいた。

つまり、最初の1手で問題が2つに分解されるってこと。

その後も実装で大苦戦したがなんとか終了数分前に答えは合うプログラムを書くことが出来た。

しかし、memoを入れると答えが合わない。

残り時間2分とかになってたため、とりあえずという感じで

map<pair<vector<int>, vector<int> >, ll> memo;

といういかにもダメそうなmemoを入れて気分としては記念submitのつもりで提出。

一応格闘の跡が残る汚いコードを載せておく。

typedef long long ll;
#define FOR( i, a, b ) for ( int i = a; i < (int)b; i ++ )
#define dump(x) cout << #x << " = " << (x) << endl
#define dump_(x) cout << #x << " = " << (x) << " "
#define dump_vec(x) cout << #x << " => "; for ( int ZzZ = 0; ZzZ < (int)x.size(); ZzZ ++ ) cout << x[ZzZ] << ", "; cout << endl
 
 
#define MOD 1000000007
#define CSIZE 60
ll choose[ CSIZE+1 ][ CSIZE+1 ];
void choose_init()
{
    memset( choose, 0, sizeof( choose ) );
    for ( int i = 0; i <= CSIZE; i++ ) {
        choose[i][0] = 1;
        for ( int j = 1; j <= i; j++ )
            choose[i][j] = ( choose[i-1][j-1] + choose[i-1][j] ) % MOD;
    }
}
 
 
map<pair<vector<int>, vector<int> >, ll> memo;
 
//ll memo[52][52];
 
ll doit(vector<int>& p, vector<int>& target, int start, int end)
{
//    dump_vec(p);
//    dump_vec(target);
 
    if (p.size() == 0) return 1;
    if (p.size() == 1) {
        if (p[0] == target[0]) return 1;
        return 0;
    }
    if (p == target) return 0;
    vector<int> sp = p, st = target;
    sort(sp.begin(), sp.end());
    sort(st.begin(), st.end());
    if (sp != st) return 0;
#if 0
    ll& res = memo[start][end];
    if (res != -1) return res;
#else
    ll res = 0;
#endif
    res = 0;
 
    int convert[51];
    for (int i = 0; i < target.size(); i++)
        convert[target[i = i;
    for (int i = 0; i < p.size(); i++)
        p[i] = convert[p[i;
 
    if (memo.count(make_pair(p, target))) return memo[make_pair(p, target)];
    
    
    for (int last = 0; last + 1 < p.size(); last++) {
        vector<int> p1, p2, target1, target2;
        for (int i = 0; i <= last; i++) p1.push_back(p[i]);
        for (int i = last + 1; i < p.size(); i++) p2.push_back(p[i]);
        for (int i = 0; i <= last; i++) target1.push_back(i);
        for (int i = last + 1; i < p.size(); i++) target2.push_back(i);
        swap(target1[target1.size() - 1], target2[0]);
        ll r1 = doit(p1, target1, 0, last+1);
        ll r2 = doit(p2, target2, last + 1, p.size());
        int num1 = last;
        int num2 = p.size() - last - 2;
        // mix
        ll mix = choose[num1 + num2][num1];
        ll r = r1 * r2 % MOD;
        r = r * mix % MOD;
        res += r;
        res %= MOD;
    }
    memo[make_pair(p, target)] = res;
    return res;
}
 
class AdjacentSwaps {
public:
    int theCount(vector <int> p)
    {
        memo.clear();
        // backward
        // last : l
        choose_init();
        vector<int> target;
        FOR(i, 0, p.size()) target.push_back(i);
        //memset(memo, -1, sizeof(memo));
        return doit(p, target, 0, p.size());
    } 
};


challenge phase

Easyで自分と同じ間違いを探したが発見出来ず諦めた。

しかし結果的にはたくさん落ちていてちょっと残念だった。

次にMediumを書き写したらサンプルで落ちることを発見。

しかし書き写しミスの懸念のためチャレンジ自重。

もし自分のMediumに自信があれば失敗してもほとんど順位が変わらなかったためチャレンジしたのだが。

結果的にチャレンジしてれば成功していたようだ。

結果

予想外に両方通って69/828位と好順位。

twitter ホーム 吉祥寺 わいわい将棋