naoya_t@hatenablog

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

2014 TopCoder Open Algorithm Round 1A

GCJ QRの最中の開催。

GCCが動かないの忘れたままregisterしちゃって
慌ててXcodeをインストール。
コーディング時間開始30秒前にインストール完了!

Easy: EllysSortingTrimmer

後ろからソートして詰めていけばいいだけ、という事に気づくのに時間がかかりすぎました

class EllysSortingTrimmer {
 public:
  string getMin(string S, int L) {
    for (int i=S.size()-L; i>=0; --i) {
      sort(S.begin()+i, S.begin()+i+L);
    }
    return S.substr(0,L);
  }
};

Medium: EllysScrabble

cmp()の実装がまずかったせいでなかなか結果が合わず。

using namespace std;
#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)

typedef pair<int,char> ic;

int cmp(ic a, ic b) {
  if (a.second == b.second) return a.first < b.first;
  else return a.second < b.second;
}

class EllysScrabble {
 public:
  string getMin(string letters, int mD) {
    int n = letters.size();
    vector<ic> a;
    rep(i,min(n,mD)){
      a.pb(ic(mD+i+1,letters[i]));
    }
    vector<char> ans;
    for (int i=mD;;++i) {
      if (i < n)
        a.pb(ic(mD*2+1,letters[i]));

      if (a.size() == 0) break;
      tr(it,a) (it->first)--;
      sort(all(a));
      if (a[0].first == 0) {
        ans.pb(a[0].second);
        a.assign(a.begin()+1,a.end());
        continue;
      }
      sort(all(a),cmp);
      ans.pb(a[0].second);
      a.assign(a.begin()+1,a.end());
    }
    return string(all(ans));
  }
};

Hard: EllysLamps

開いただけ

//

EasyとMediumが通ったものの、時間かかりすぎ。予選通過ならず。
oo- (+0/-0) = 414.84pts Room 12/25, 949/2425

https://twitter.com/naoya_t/status/455040300893741056