naoya_t@hatenablog

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

SRM619

久々に参加するSRM

こないだのTCO R1CでVolatilityが上がってるから、ここで良い点を出せばスムーズに黄色に戻れるかも?(0完だと逆に急降下のおそれが)


去年の8/12に青に陥落し、一度は1200台までレーティングを下げてからの黄色復帰。
f:id:n4_t:20140506103458p:plain

それにしても 250-600-1000 って何?

Easy (250) SplitStoneGame

  • 山の数が3つなければ終わり
  • 2以上の山がなくなったら(=すべてが1)終わり
  • 1手ごとに山が1つずつ減っていく。山が減る過程ですべてが1になることはありえないよね。
  • てことは山の数が3つ以上 && 2以上の山が1つでもある場合、最初の山の数の偶奇で勝敗が決まるのでは。
  • これってDiv2 Easyな感じじゃない?
  • 本当にこれで大丈夫?ってしばらく悩んで提出遅れた感
  • 232.80pt
  • AC
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define sz(a)  int((a).size())
#define all(c)  (c).begin(),(c).end()

class SplitStoneGame {
 public:
  string winOrLose(vector<int> number) {
    int N=sz(number);
    sort(all(number),greater<int>());
    if (N <= 2 || number[0] ==1) return "LOSE";
    return (N & 1) ? "WIN" : "LOSE";
  }
};

Medium (600) GoodCompanyDivOne

  • ツリーの根元から部署を1つずつ訪れて、トレーニングコストの安い順に0,1,2,3,4,...みたいに振ってみる(ので親は0)
  • 子供の数が多いやつに大きな番号を振ったほうがいいかな?
  • rootには0しか入ってないので1を追加
  • みたいなのでテストケースは通ったけど
  • 赤い人にも撃墜されなかったけど
  • 234.72pt→0pt (WA)

以下WAコード

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
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(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> II;

class GoodCompanyDivOne {
 public:
  int minimumCost(vector <int> superior, vector <int> training) {
    int N=sz(superior), T=sz(training);
    map<int,set<int> > children;
    set<int> os;
    vector<int> floor(N,0);

    sort(all(training));

    rep(i,N){
      int o=superior[i]; if (o==-1) continue;
      children[o].insert(i);
      floor[i] = floor[o]+1;
      os.insert(o);
    }

    vector<int> cns(N,0);
    tr(it,children){
      int cn=sz(it->second), o=it->first;
      if (1+cn > T) return -1; // impossible
      cns[o] = cn;
    }

    vector<II> fs;
    rep(i,N){
      fs.pb(II(floor[i],i));
    }
    sort(all(fs));

    vector<vector<int> > alo(N, vector<int>());
    alo[0].pb(1);

    rep(j,N){
      int i = fs[j].second;
      alo[i].pb(0);
      int k=0;
      vector<II> fs_;
      tr(it,children[i]){
        int ch=*it;
        fs_.pb(II(cns[ch],ch));
      }

      sort(all(fs_));
      tr(it,fs_){
        int ch=it->second;
        if (k == alo[i][0]) k++;
        alo[ch].pb(k++);
      }
      if (alo[i][1] == alo[i][0]) alo[i][1]=1;
    }

    int sum=0;
    rep(i,N){
      sum += training[alo[i][0]] + training[alo[i][1]];
    }

    return sum;
  }
};

Hard (1000) 開いてない