Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-07

SRM340 div2(過去問)

23:06

Easy - CssPropertyConverter

"-"と小文字のアルファベットから成る文字列が与えられる。"-"を消去し、直後の文字を大文字にする(camel記法にする)という問題。

以前作ったsplitという関数を使ってみました。

  vector <string> split(const string _s, const string del)
  {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
	size_t pos = s.find(del);
	string sub = "";
	sub = s.substr(0, pos);
	ret.push_back(sub);
	if (pos != string::npos)
	  pos += del.size();
	s.erase(0, pos);
      }

    return ret;
  }

  string getCamelized(string cssPropertyName)
  {
    string ret;
    vector <string> s = split(cssPropertyName, "-");
    for (int i=1; i<s.size(); i++)
      s[i][0] = s[i][0] - 'a' + 'A';
    for (int i=0; i<s.size(); i++)
      ret += s[i];
    return ret;
  }

SRM341 div2(過去問)

18:33

Easy - ChangingString

2つの文字間の距離を、文字の差の絶対値と定義する。2つの同じ長さの文字列の距離を、同じインデックスの文字の距離の総和とする。("abc"と"cba"の場合4)。K個の文字を変更した場合の、文字列間の最小距離を計算する問題。

戦略:2つの文字列の各文字の距離をそれぞれ計算し、降順に並べる。距離が大きいものからK個、距離を0にする。もし距離が0だった場合、距離を1にする。


  int distance(string A, string B, int K)
  {
    vector <int> gap;
    int ret = 0;

    for (int i=0; i<A.size(); i++)
      gap.push_back(abs(A[i] - B[i]));

    sort(gap.rbegin(), gap.rend());

    for (int i=0; i<K; i++)
      if (gap[i] == 0)
	gap[i] = 1;
      else
	gap[i] = 0;

    for (int i=0; i<gap.size(); i++)
      ret += gap[i];

    return ret;
  }

Medium - KLastNonZeroDigits

引数Nの階乗を計算する。値の右側に0があれば削除する(202000の場合202となる)。位の低い方からK文字を返すという問題。

階乗を計算し、0を除き、部分文字列を返すという、ストレートな方法で問題ありませんでした。

  string getKDigits(int N, int K)
  {
    double d = 1;
    char c[30];
    string str;
    string ret;

    for (int i=1; i<=N; i++)
      d *= i;

    sprintf(c, "%.0f", d);
    str = c;

    reverse(str.begin(), str.end());

    while (str[0] == '0')
      str.erase(0, 1);

    if (K <= str.size())
      for (int i=0; i<K; i++)
	ret += str[i];
    else
      ret = str;

    reverse(ret.begin(), ret.end());

    return ret;
  }

SRM420 div2(過去問)

16:46

Easy - DeckRearranging

文字列を並び替える問題。stringのメソッドの使い方がわかれば、すぐに解ける問題でした。

  string rearrange(string deck, vector <int> above)
  {
    string ret;

    for (int i=0; i<deck.size(); i++)
      ret.insert(above[i], deck.substr(i, 1));

    return ret;
  }

Medium - YearProgressbar

日付と時刻が与えられ、その年のうち何%が経過したかを計算する問題。

戦略は、一年間のトータルの時間と、与えられた時刻までの経過時間の両方を分に変換し、パーセンテージを計算するという方法です。ストレートに考えました。

うるう年の判定法も問題文中に明記されていたため、素早く実装するのみの問題でした。しかし、細かいミスなどで結構時間がとれれてしまいました。

  double percentage(string currentDate)
  {
    // 月ごとの経過日数
    map <string, int> month;
    month["January"] = 0;
    month["February"] = 31;
    month["March"] = 59;
    month["April"] = 90;
    month["May"] = 120;
    month["June"] = 151;
    month["July"] = 181;
    month["August"] = 212;
    month["September"] = 243;
    month["October"] = 273;
    month["November"] = 304;
    month["December"] = 334;

    char monc[10];
    string mon;
    int day;
    int year;
    int hour;
    int min;

    // 引数を読み込む
    sscanf(currentDate.c_str(), "%s %02d, %d %02d:%02d", monc, &day, &year, &hour, &min);
    mon = monc;

    // うるう年の判定
    bool isLeap = false;
    if (year % 400 == 0 || year % 4 == 0 && year % 100 != 0)
      isLeap = true;

    double md = 0, my = 0;

    // 一年間の分を計算
    if (isLeap)
      my = 366 * 24 * 60;
    else
      my = 365 * 24 * 60;

    // うるう年で3月以降の場合一日増やす
    if (isLeap && (mon != "January" && mon != "February"))
      day++;

    // その日付までの経過日数が欲しいので、デクリメントする
    day--;

    // 現在時刻の分を計算
    md += month[mon] * 24 * 60;
    md += day * 24 * 60;
    md += hour * 60;
    md += min;

    return (md / my) * 100;
  }