naoya_t@topcoder

過去問マラソン(#2):SRM145

過去問マラソン | 12:45 |

過去問マラソン2日目。

Easy(250): Bonuses

• 前にも見たかなあ
• Sample caseで答えが合わず悩んでたら、小数点以下を切り捨てたパーセンテージで上から数えててたorz
• 12'32''遅すぎ
• systest一発

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)

class Bonuses {
 public:
  vector<int> getDivision(vector<int> points) {
    int n=sz(points);
    int sum=0;rep(i,n)sum+=points[i];

    vector<int> pd(n);
    int left=100;
    rep(i,n){pd[i]=100*points[i]/sum;left-=pd[i];}

    vector<int> added(n,0);
    while (left>0) {
      int maxpt=0,maxat=-1;
      // rep(i,n){if(added[i]==0&&maxpt<pd[i]) maxpt=pd[i],maxat=i;} // !oops
      rep(i,n){if(added[i]==0&&maxpt<points[i]) maxpt=points[i],maxat=i;}
      added[maxat]++; left--;
    }
    rep(i,n) pd[i]+=added[i];
    return pd;
  }
};

てか後半はソートを使って簡単に書きたい。やり直し

• ソート順が小さい順（昇順）なことを感覚的に捉えられてなくて、テスト動かしてみて確認してるのが時間もったいない

#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()

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

class Bonuses {
 public:
  vector<int> getDivision(vector <int> points) {
    int n=sz(points);
    int sum=0;rep(i,n)sum+=points[i];

    vector<int> pd(n);
    int left=100;
    rep(i,n){pd[i]=100*points[i]/sum;left-=pd[i];}

    vector<i_i> pp(n);
    rep(i,n)pp[i]=cons(-points[i],i);
    sort(all(pp));
    rep(i,left) pd[cdr(pp[i])]++;
    return pd;
  }
};

Medium(600):VendingMachine

• 見たことある気もする
• 実装するだけなんですが
  • コード書き始めるのはもうちょっと問題を咀嚼してからでいいかも。焦っても意味ない
• max_element()で何か変な値が出るので延々悩んでたら、カラムの数にprices[0].size() が入ってた。これはカラム数ではなく文字数！
  • ちょっとiteratorの扱いに慣れてきたぞ
• しかし74'38''...遅い
• systestは一発
  • Easyすっ飛ばしてこれだけ解いてsubmitすれば218.51点はとれた計算
  • Easy, Mediumともに解ける問題なので、２問とも時間内にぜひともクリアしたい

vector<string> split(string str, int delim=' '); // 略

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

int stoi(string s){ return atoi(s.c_str()); }

class VendingMachine {
 public:
  int motorUse(vector <string> prices, vector <string> purchases) {
    int n_shelves=sz(prices), n_columns;
    // n_columns = sz(prices[0]); // !oops
    vector<vector<int> > table(n_shelves);
    vector<int> pricesum;
    rep(sh,n_shelves){
      table[sh] = map_atoi(split(prices[sh])); // sh[i][s>=3] : 1..10000
      if (sh==0) {
        n_columns = sz(table[sh]);
        pricesum.resize(n_columns); rep(i,n_columns) pricesum[i]=0;
      }
      rep(col,n_columns) pricesum[col] += table[sh][col];
    }

    int motorrun = 0;
    int last_t = 0;

    // autorot
    int curr_col = 0, new_col, diff;

    {
      vector<int>::iterator max_at = max_element(all(pricesum));
      new_col = max_at - pricesum.begin();
      diff = abs(new_col - curr_col);
      motorrun += min(diff, n_columns-diff);
      curr_col = new_col;
    }

    set<i_i> boughts;
    rep(i,sz(purchases)){
      vector<string> a1 = split(purchases[i],':'), a0 = split(a1[0],',');
      int shelf=stoi(a0[0]), column=stoi(a0[1]), time=stoi(a1[1]);

      int lapse = time - last_t;
      if (lapse>=5) {
        // autorot at last_t
        vector<int>::iterator max_at = max_element(all(pricesum));
        new_col = max_at - pricesum.begin();
        diff = abs(new_col - curr_col);
        motorrun += min(diff, n_columns-diff);
        curr_col = new_col;
      }

      {
        new_col = column;
        diff = abs(new_col - curr_col);
        motorrun += min(diff, n_columns-diff);
        curr_col = new_col;
      }
      
      i_i key = cons(shelf,column);
      if (found(boughts,key)) return -1;
      boughts.insert(key);

      pricesum[column] -= table[shelf][column];
      table[shelf][column] = 0;
      
      last_t = time;
    }

    // last autorot
    {
      vector<int>::iterator max_at = max_element(all(pricesum));
      new_col = max_at - pricesum.begin();
      diff = abs(new_col - curr_col);
      motorrun += min(diff, n_columns-diff);
      curr_col = new_col;
    }

    return motorrun;
  }
};

Hard(1000): HillHike

(to be continued)