読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

SRM588

TopCoder Single Round Match

久々のSRM参戦かも。いつの間にかPythonが入っていたりC++11になっていたり。
250-450-1100


typeofは

#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

という常用のマクロで使ってました。咄嗟に

#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)

と書きなおしてコンパイル通しましたが、これC++11ならそもそも for (auto i : c) みたいに書けるのでは疑惑

Easy (250)

みんなDPで書いてたりするんですが

提出コード。AC。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
//#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))

class GUMIAndSongsDiv1 {
 public:
  int maxSongs(vector <int> duration, vector <int> tone, int T) {
    int n = sz(duration);
    map<int,vector<int> > mu;
    rep(i,n){
      mu[tone[i]].pb(duration[i]);
    }
    int ton=0;
    vector<pair<int,vector<int> > > to;
    tr(it,mu){
      int k=it->first;
      sort(all(it->second));
      to.pb(cons(k, it->second));
      ton++;
    }

    int maxcnt = 0;
    for(int i=0; i<ton; ++i){
      for(int j=i; j<ton; ++j){
        int tfrom = to[i].first, tto = to[j].first;
        int cost = tto - tfrom; if (cost > T) continue;
        int rem = T - cost;
        vector<int> dus;
        for (int k=i; k<=j; ++k) {
          dus.insert(dus.end(), all(to[k].second));
        }
        sort(all(dus));

        int cnt = 0;
        tr(it,dus){
          if (*it <= rem) {
            ++cnt; rem -= *it;
          } else {
            break;
          }
        }
        maxcnt = max(maxcnt, cnt);
      }
    }
    return maxcnt;
  }
};

Medium (450)

next_permutationを使ってざっくり書いてみたコード(case 4で3.5秒かかる)

class KeyDungeonDiv1 {
 public:
  int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys) {
    int n = sz(doorR);

    vector<int> ixs(n);
    rep(i,n) ixs[i] = i;

    int W = 1 << n;
    vector<int> visited(W, -1);
    visited[0] = keys[0]+keys[1]+keys[2];
    int visc = 1;

    do {
      int place = 0;
      int r=keys[0], g=keys[1], w=keys[2];

      rep(i, n) {
        int ix = ixs[i];

        r -= doorR[ix];
        if (r < 0) { w -= -r; r = 0; }
        g -= doorG[ix];
        if (g < 0) { w -= -g; g = 0; }
        if (w < 0) break;

        r += roomR[ix]; g += roomG[ix]; w += roomW[ix];

        place |= (1 << ix);
        printf("%d %x\n", i, place);
        if (visited[place] == -1) {
          visited[place] = r+g+w; ++visc;
          if (visc == W) {
            printf("FILLED.\n");
            goto out;
          }
        }
      }
   next:;
    } while(next_permutation(all(ixs)));
 out:;

    int kmax = 0;
    rep(i,W) kmax = max(kmax, visited[i]);
    return kmax;
  }
};

提出コードを仕上げるに至らず。

みんなDP使ってほいほいと解いてた。

黄色くなった(おそらく10回目)

Mediumがfailed system test出まくって、Coding Phase終了直後411位だったのが273位/756人まで上がってた。部屋では12位→10位。
1466→1511
f:id:n4_t:20130813084326p:plain

C++11

ローカルに処理系入れるところから始めないと。
と言っても既に入ってるLLVMのコンパイラで -std=c++11 を付ければ良さげ