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

naoya_t@hatenablog

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

2012 TCO Algorithm - Round 1B

TopCoder Openの第1ラウンド(予選みたいなもの)の2回目。
1回目を寝倒したので今回は頑張って起きて参加。日本時間1amから。

赤い人から灰色の人まで満遍なく揃ったRoom1。
EasyとMediumが通って 204.52 + 451.30 = 655.82点。部屋2/24位、全体122/1948位
とりあえず第2ラウンド進出決定。
レーティング上がった:1568 → 1655(自己ベスト)
f:id:n4_t:20120408104413p:plain

Easy(250) FoxAndKgram

  • 可能なkを全て洗い出して、大きい順に可能かどうか試していくだけ
    • 実際はkの洗い出しとか要らない。鉛筆の本数が行数maxなのでそこからdecrementしていけばいい
  • 204.52point = 14'3''
#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(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class FoxAndKgram {
 public:
  int maxK(vector<int> len) {
    sort(all(len));int n=sz(len);
    set<int>le;
    tr(len,it){
      le.insert(*it);
    }
    set<int>wa;
    tr(le,it)wa.insert(*it);
    for(int i=0;i<n-1;++i)
      for(int j=i+1;j<n;++j)
        wa.insert(len[i]+1+len[j]);

    vector<int> va(all(wa)); reverse(all(va));
    tr(va,it){int k=*it,r=0;
      vector<int> l2(all(len));sort(all(l2));reverse(all(l2));
      rep(i,n) {
        if(l2[i]<0)continue;
        if(l2[i]>k)continue;
        if(l2[i]==k){
          r++;l2[i]=-1;
        }else {
          for(int j=i+1; j<n;++j) {
            if (l2[j]==k-l2[i]-1){
              r++; l2[i]=l2[j]=-1;
            }
          }
        }
        if (r>=k) return k;
      }
    }
    return 0;
  }
};

Medium(500) FoxAndDoraemon

  • ドラえもんってw
  • それぞれの狐はタスクを1つしか行わない。
    • 2つのタスクがあったとして、狐を分裂させて処理するとして、分裂前と分裂後どちらに行うべきか?分裂してからそれぞれにやらせた方が合計時間は短い。
  • タスクの後に分裂することはない、ということはタスク完了から時系列を逆に辿ってみてはどうか
    • タスク所要時間が短い2匹からフュージョンしていく感じ。フュージョンの所要時間も含め1匹のタスク所要時間とみなせば再帰的に処理できる
    • こういうのってプライオリティ・キューで書くと簡単ですね
  • 451.30point = 9'32''
    • Easyよりあっさり仕上がった
    • 部屋1位のひと(Min,lu、赤)と同じ解法だったので安心してChallenge phaseを傍観(撃墜はしない)
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class FoxAndDoraemon {
 public:
  int minTime(vector<int> workCost, int splitCost) {
    priority_queue<int,vector<int>,greater<int> > pq;
    tr(workCost,it) pq.push(*it);
    while(true){
      int a = pq.top(); pq.pop();
      if (pq.empty()) return a;
      int b = pq.top(); pq.pop();
      pq.push(max(a,b) + splitCost);
    }
  }
};

Hard(1000) FoxAndPhotography

40分使えたけど提出に至らず。