Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-01-07

LampsGrid (SRM432 DIV2 Medium)

| 23:47 | LampsGrid (SRM432 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - LampsGrid (SRM432 DIV2 Medium) - TopCoder煮ブログ

格子状のランプでなるべく多くの行を点灯させようという問題。ON/OFF は列ごとに行う。

2^50 の総当りだと時間足りないし、かといって点灯回数は1000とこちらも総当りは無理そう。

しばらく考えて、行ごとに点灯するときのパターンが固定だと気づいた。パターンごとに何行あるかを map に格納して、key ごとに K 回の点灯で実現できるかを調べていけばよい。

ゆっくり解いて30分ぐらい。集計と測定でループを2回書いたけど SRM432 - naoya_t@topcoderで紹介されていたコードは短い。確かに1回でいけますな。

一応自分のコード。

    long long L[50];
    int N = initial.size();
    int M = initial[0].size();
    map<long long, int> score;
    for(int i = 0; i < N; i++){
        L[i] = 0;
        for(int j = 0; j < M; j++){
            L[i] <<= 1LL;
            L[i] += (initial[i][j] == '0' ? 1 : 0);
        }
        score[L[i]]++;
    }

    int ret = 0;
    for(map<long long, int>::const_iterator p = score.begin(); p != score.end(); p++){
        if(ret > p->second) continue;
        int c = countbit(p->first);
        if(c == K || (c < K && (c - K) % 2 == 0)){
            ret = p->second;
        }
    }
    return ret;

ソートするかなーと思って、配列 L に格納したけど不要だった。

KaleighKaleigh2011/07/22 22:40This article ahcieved exactly what I wanted it to achieve.

zfheyhxzfheyhx2011/07/23 17:29Se43py <a href="http://vmwznwwadodd.com/">vmwznwwadodd</a>

jyjyozjparjyjyozjpar2011/07/23 22:14Y5NYXE , [url=http://pkdnrubsxigg.com/]pkdnrubsxigg[/url], [link=http://dsgtnofwuklq.com/]dsgtnofwuklq[/link], http://ydxgxqliwsxo.com/

zyynmjpdazyynmjpda2011/07/25 21:35DAcasi <a href="http://nwntvgsssznt.com/">nwntvgsssznt</a>

xqtexmjkwzxqtexmjkwz2011/07/26 00:57wkX3mk , [url=http://fivzffwazwyz.com/]fivzffwazwyz[/url], [link=http://lmbouqeprmwa.com/]lmbouqeprmwa[/link], http://cmczbpqluwvp.com/