SRM 413 Div1

TopCoder

easyとmediumをsubmit, hardは問題文を読んだけども残り20分で実装できる気がしなくてぐだぐだ。gcdとlcmを実装したけどBoostにあるなぁ。boost::rationalってのの存在を知った。でもアルゴリズムは全然思いついていない。

easyはその後のシステムテストで落とされた。思いついた素直な方法で実装して手元のテストで落ちて、がんばって直したのだが。。mediumの方が簡単じゃないかな。

問題の内容は、書類を書いて出して次の書類を受け取って書いて出して、、というプロセスを再短時間でやるにはどうするかというもの。ただ、書類の提出窓口が空いている時間が一日のうちの何時間と決まっていて、書類を書き上げても窓口が閉まっていたら開くまでまたなければ行けない。書類書きに着手してから完了するまでを最短で何時間か、という問題。

初日に窓口が開いたときに書類を出して、受け取った書類を書いて、もし窓口が閉まっていたら次の窓口が開く時間まで時計を進めて、という風に書いたらダメだった。例えば窓口が開いているのが1時間で、初日に受け取る書類が書くのに2時間かかるものだったら、窓口が開いたときに提出しても閉まるときに提出しても結果が変わらないから閉まるぎりぎりに出す方が時間が短い。むぅ。

↓いかにもあがいている感じのエレガントじゃないコード

  int visaApplication(vector <int> forms, int dayLength, int openTime) {
    vector<int> start;
    int t = -forms[0];
    start.push_back(t);
    t += forms[0];

    size_t N = forms.size();
    for(size_t i=1; i<N; i++){
      // wait
      if(t % dayLength > openTime){
	t = (t / dayLength + 1) * dayLength;
      }
      // submit
      start += t; // got another
      t += forms[i];
    }
    if(t % dayLength > openTime){
      t = (t / dayLength + 1) * dayLength;
    }
    // submit last one
    int head = t;
    // packing phase
    //DP(start);
    for(size_t i=N-1; i!=-1; i--){
      if(start[i] + forms[i] == head){
	head = start[i];
      }else{
	// pack?
	int lasttime = openTime - (start[i] % dayLength);
	int gap = head - start[i] - forms[i];
	if(gap < lasttime){
	  start[i] += gap;
	  head = start[i];
	}else{
	  start[i] += lasttime;
	  head = start[i];
	}
      }
    }

    return t - start[0];
  }

mediumの問題は簡単に言うとacd, be, efgって文字列が与えられたときに、abcdeefgを作れってもの。

a_cd
_b__e
_____efg

ソースコードはこんな感じ。sliceってのは細かなユーティリティ関数を書きためている僕のtoolbox.hppから挿入されたもの。文字列の操作をPythonのslice風にするやつで、x[1:]がslice(x, 1, "")になる。アルゴリズムは読んでの通り、番兵をつけてからソートして順に一番上のものの頭の1文字を取るだけ。シンプル。

string slice(const string &s, int start, int end){
  if(end < 0) end += s.size();
  if(start < 0) start += s.size();
  if(start > end) return "";
  return s.substr(start, end - start);
}
string slice(const string &s, int start, const string&){
  return slice(s, start, s.size());
}

class StringInterspersal {
public:
  string minimum(vector <string> W) {
    string result = "";
    for(size_t i=0; i<W.size(); i++){
      W[i] += ('Z' + 1);
    }
    while(1){
      sort(W.begin(), W.end());
      if(W[0][0] > 'Z') break;
      result += W[0][0];
      W[0] = slice(W[0], 1, "");
      if(W[0].empty()){
	W.erase(W.begin());
      }
    }
    return result;
  }

レーティングはなんとか上がった。1489。
MacBookのバッテリーがもうなくなる。