Hatena::Grouptopcoder

shnyaの参戦記録

2011-04-09【練習】TopCoder SRM 502,434

問題内容はタイトルをクリックしてください。

SRM 502 Div1 Easy 22:25  [http://www.topcoder.com/stat?c=problem_statement&pm=11359&rd=14431:title=SRM 502 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11359&rd=14431:title=SRM 502 Div1 Easy] - shnyaの参戦記録

今回は参加できなかったのでプラクティスで。

考えたこと

同じSuffixの単語を消していけばいいだけ。

でもできるだけ少ない計算量でコーディングしようとする癖がついてしまっているのか、

ソートしてから連続するシーケンスをチェックするという面倒な方針を取ってしまった。

O(n^2)でやった方が楽だよなー。

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(a) int((a).size())

class TheLotteryBothDivs
{
public:
  double find(vector <string> goodSuffixes)
  {
    vector<string> v;
    REP(i,SZ(goodSuffixes)){
      string s = goodSuffixes[i];
      reverse(s.begin(),s.end());
      v.push_back(s);
    }
    sort(v.begin(),v.end());
    vector<string> v2;
    string s = v[0];
    v2.push_back(s);
    FOR(i,1,SZ(v)){
      string s2 = v[i];
      bool flg = true;
      REP(j,SZ(s)){
        if(s[j] != s2[j]){
          flg = false;
          break;
        }
      }
      if(!flg){
        s = s2;
        v2.push_back(s2);
      }
    }
    long double res = 0.0;
    REP(i,SZ(v2)){
      res += pow(0.1,int(v2[i].size()));
    }

    return (double)res;
  }
}

SRM 502 Div1 Medium 22:25  [http://www.topcoder.com/stat?c=problem_statement&pm=11357&rd=14431:title=SRM 502 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11357&rd=14431:title=SRM 502 Div1 Medium] - shnyaの参戦記録

考えたこと

あれ?ナップサック?簡単っぽい。

いや、ダメじゃん。T=10^6? DP使えない?

実際は10^6の要素は必要なく、取り得る値の数はもっと少ないはずだから

map<int,int> m[51]

とかで逃げよう。


いや、違う。T=10^5じゃないか!?

しかも、計算に使われるのは累積時間なのか!

2^50の組合せ? ビットDPもできないし・・・。範囲DPも無理っぽい。

うーん、とりあえず貪欲法で解く。システムテスト通らない。


ソートをすればよかったのか。。。

解き方わかっても、int型のかけ算でOverflowしてはまる。。

先は遠い。。。

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(a) int((a).size())
typedef long long int LLI;

LLI dp[52][100001];
class TheProgrammingContestDivOne
{
  LLI calc(LLI m, LLI p, LLI r){
    return m - p * r;
  }
public:
  int find(int T, vector <int> maxp, vector <int> pointm, vector <int> require)
  {
    CLR(dp);
    REP(j,SZ(maxp)){
      REP(i,SZ(maxp)-1){
        LLI n1 = calc(maxp[i],pointm[i], require[i])
          + calc(maxp[i+1], pointm[i+1], require[i] + require[i+1]);
        LLI n2 = calc(maxp[i],pointm[i], require[i] + require[i+1])
          + calc(maxp[i+1], pointm[i+1], require[i+1]);
        if(n1 < n2){
          swap(maxp[i],maxp[i+1]);
          swap(pointm[i],pointm[i+1]);
          swap(require[i],require[i+1]);
        }
      }
    }
    //cout << T << endl;
    //cout << maxp << endl;
    //cout << pointm << endl;
    //cout << require << endl;
    REP(i,SZ(maxp)) REP(j,T+1) {
      if(j - require[i] >= 0){
        //cout << calc(maxp[i],pointm[i],j) << endl;
        LLI k = calc(maxp[i],pointm[i],j);
        if(k + dp[i][j-require[i]] > dp[i][j])
          dp[i+1][j] = dp[i][j-require[i]] + calc(maxp[i],pointm[i],j);
        else
          dp[i+1][j] = dp[i][j];
      }else{
        dp[i+1][j] = dp[i][j];
      }
    }
    LLI res = 0;
    REP(j,T+1){
      //cout << j << " " << dp[SZ(maxp)][j] << endl;
      if(res < dp[SZ(maxp)][j])
        res = dp[SZ(maxp)][j];
    }

    return res;
  }
}

SRM 434 Div1 Easy 22:25  [http://www.topcoder.com/stat?c=problem_statement&pm=10268&=13696:title=SRM 434 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10268&=13696:title=SRM 434 Div1 Easy] - shnyaの参戦記録

考えたこと

勉強会で解きました。

問題内容がよくわからない。。

とりあえず全探索かなーと書き始めるが、コーディング途中で時間切れ。

全探索の方針は間違えてなさそうなので、家に帰ってから解いた。

実装早くならないとな。。。

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(a) int((a).size())

class FindingSquareInTable
{
public:
  int findMaximalSquare(vector <string> table)
  {
    int rnum = SZ(table);
    int cnum = SZ(table[0]);

    int res = -1;
    vector<int> v;
    FOR(i,0,50000) v.push_back(i*i);

    REP(i,rnum) REP(j,cnum) FOR(k,-rnum+1,rnum) FOR(l,-cnum+1,cnum) {
      string s;
      int m = 0;
      while(1){
        int newr = i + m * k;
        int newc = j + m * l;
        if(newr < 0 || newr >= rnum || newc >= cnum || newc < 0)
          goto fail;
        s += table[newr][newc];
        int n = toInt(s);
        if(n > res && binary_search(v.begin(),v.end(),n)) res = n;
        //cout << s << endl;
        if(k == 0 && l == 0) goto fail;
        m++;
      }
    fail: ;
    }

    return res;
  }
}