Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-04

SRM342 div2(過去問)

02:57

Easy - DegreesToRadians

degreeをradianに変換する問題。計算式が問題文に書かれているので、ほんとうにやるだけの問題。

  double convertToRadians(int degrees, int minutes, int seconds)
  {
    double pi = 3.141592653589793;
    double min = (double)minutes + (double)seconds / 60.0;
    double deg = min / 60.0 + (double)degrees;
    return deg * pi / 180.0;
  }

Medium - TagalogDictionary

tagalog語という言語の単語順を用いて、単語をソートする問題。

意外とストレートに解くことができた。tagalogのアルファベットをうまく変換するところがポイントだと思う。また、pairのソートは、第一要素で比較。第一要素が同じだった場合、第二要素で比較という風に行われる。便利。

解説ページに色々面白そうなことが書いてあったので、後で読んでみよう。

  vector <string> dic;
  TagalogDictionary(void)
  {
    dic.push_back("a");
    dic.push_back("b");
    dic.push_back("k");
    dic.push_back("d");
    dic.push_back("e");
    dic.push_back("g");
    dic.push_back("h");
    dic.push_back("i");
    dic.push_back("l");
    dic.push_back("m");
    dic.push_back("n");
    dic.push_back("ng");
    dic.push_back("o");
    dic.push_back("p");
    dic.push_back("r");
    dic.push_back("s");
    dic.push_back("t");
    dic.push_back("u");
    dic.push_back("w");
    dic.push_back("y");
  }

  int toVar(string s)
  {
    int ret = 0;
    for (int i=0; i<dic.size(); i++)
      if (s == dic[i])
	ret = i;

    return ret;
  }

  char toChar(int n)
  {
    return 'a' + n;
  }

  vector <string> sortWords(vector <string> words)
  {
    vector <string> ret;
    vector <pair<string, int> > v;

    for (int i=0; i<words.size(); i++)
      {
	string enc = "";
	for (int j=0; j<words[i].size(); j++)
	  {
	    string tmp = "";
	    if (j < words[i].size()-1 && words[i][j] == 'n' && words[i][j+1] == 'g')
	      {
		tmp = "ng";
		j++;
	      }
	    else
	      tmp = words[i][j];

	    enc += toChar(toVar(tmp));
	  }
	pair <string, int> t(enc, i);
	v.push_back(t);
      }

    sort(v.begin(), v.end());

    for (int i=0; i<v.size(); i++)
      ret.push_back(words[v[i].second]);

    return ret;
  }

SRM343 div2(過去問)

02:00

Easy - PersistentNumber

Persistent Number という数に関する問題。Persistent Numberの数学的意味は無視して、アルゴリズムの側面からのみ考えると、ただやるだけの簡単な問題でした。

  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  int getPersistence(int n)
  {
    int ret = 0;
    int d = n;

    while (d > 9)
      {
	string s = toStr(d);
	int tmp = 1;
	for (int i=0; i<s.size(); i++)
	  tmp *= s[i] - '0';
	d = tmp;
	ret++;
      }
    return ret;
  }

Medium - CDPlayer

CDプレイヤーのランダム再生を考える。数曲再生し、きちんとランダム再生されているかをしらべる問題。

特にひねることなく、ストレートに攻めれば解ける問題でした。

  bool ok(string s)
  {
    map <char, int> m;
    map <char, int>::iterator it;
    for (int i=0; i<s.size(); i++)
      m[s[i]]++;

    for (it=m.begin(); it!=m.end(); it++)
      if (it->second > 1)
	return false;

    return true;
  }

  int isRandom(vector <string> songlist, int n)
  {
    string s = "";

    for (int i=0; i<songlist.size(); i++)
      s += songlist[i];

    for (int i=0; i<n; i++)
      {
	string sub = s.substr(0, i);
	if (!ok(sub))
	  continue;

	int pos = i;
	bool notFound = false;
	while (pos < s.size())
	  {
	    sub = s.substr(pos, n);
	    if (!ok(sub))
	      {
		notFound = true;
		break;
	      }
	    pos += n;
	  }
	if (!notFound)
	  return i;
      }

    return -1;
  }

SRM344 div2(過去問)

19:06

Easy - Chessboard

チェスボードの記法を変換する問題。少し時間がかかったが、特に問題はなかった。

  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  string changeNotation(string cell)
  {
    string ret = "";

    if ('0' <= cell[0] && cell[0] <= '9')
      {
	int c;
	sscanf(cell.c_str(), "%d", &c);
	int n = (double)c / 8 + 0.9;
	int a = c % 8;
	if (a == 0)
	  a = 8;
	a--;

	ret += 'a' + a;
	ret += '0' + n;
      }
    else
      {
	char c;
	int n;
	sscanf(cell.c_str(), "%c%d", &c, &n);
	int r = (c - 'a' + 1) + 8 * (n - 1);
	ret = toStr(r);
      }
    return ret;
  }

Medium - SimpleRotationDecoder

暗号デコードする問題。この問題では、アルゴリズム的な難しさよりも、落ち着いて、正確に、素早くコーディングする力が求められているようだった。解くことはできたけど、本番だったら焦っていて間に合わなかったかもしれない。

一応、僕のとった戦略は、全ての可能なパスワードをしらみつぶしに調べるというものです。全ての可能なパスワードは26*26*26通りなので、実行時間は問題ないと考えました。

  int toVar(char c)
  {
    int ret = 0;
    if (c != ' ')
      ret = c - 'a' + 1;
      
    return ret;
  }

  char toChar(int d)
  {
    char ret = ' ';
    if (d > 0)
      ret = 'a' + d - 1;
      
    return ret;
  }

  vector <string> getWords(string s)
  {
    size_t pos;
    vector <string> ret;

    while (!s.empty())
      {
	pos = s.find(' ');
	if (pos == string::npos)
	  {
	    ret.push_back(s.substr(0));
	    s.erase(0);
	  }
	else
	  {
	    ret.push_back(s.substr(0, pos));
	    s.erase(0, pos+1);
	  }
      }
    return ret;
  }

  bool isValid(string s)
  {
    vector <string> words;
    char vow[5] = {'a', 'i', 'u', 'e', 'o'};

    if (s[0] == ' ' || s[s.size()-1] == ' ')
      return false;

    words = getWords(s);

    for (int i=0; i<words.size(); i++)
      {
	if (words[i].size() < 2 || 8 < words[i].size())
	  return false;

	bool ok = false;
	for (int j=0; j<5; j++)
	  if (words[i].find(vow[j]) != string::npos)
	    {
	      ok = true;
	      break;
	    }

	if (!ok)
	  return false;
      }

    return true;
  }

  string decode(string cipherText)
  {
    string ret = "";
    string pass = "";

    for (int a=0; a<26; a++)
      for (int b=0; b<26; b++)
	for (int c=0; c<26; c++)
	  {
	    pass = "";
	    pass += 'a' + a;
	    pass += 'a' + b;
	    pass += 'a' + c;

	    string tmp = "";
	    for (int i=0; i<cipherText.size(); i++)
	      tmp += toChar((27 + toVar(cipherText[i]) - toVar(pass[i%3])) % 27);

	    if (isValid(tmp))
	      {
		ret = tmp;
		break;
	      }
	  }

    return ret;
  }

SRM345 div2(過去問)

19:06

Easy - Trekking

特に問題はなかった。

  int findCamps(string trail, vector <string> plans)
  {
    int mini = 100;

    for (int i=0; i<plans.size(); i++)
      {
	bool ok = true;
	int c = 0;
	for (int j=0; j<trail.size(); j++)
	  {
	    if (plans[i][j] == 'C')
	      {
		c++;
		if (trail[j] == '^') 
		  {
		    ok = false;
		    break;
		  }
	      }
	  }
	if (ok)
	  mini = min(mini, c);
      }

    if (mini == 100)
      mini = -1;

    return mini;
  }

Medium - Pathfinding

2次元座標系の上で、原点から目標地点(x, y)への最短距離を求める問題。ただし、yが奇数の地点では、xが正の方向へ。逆にyが偶数の地点では、xが負の方向へしか進むことができない。同様に、xが奇数ならyは負、xが偶数ならyは正の方向へしか進めない。

一見簡単そうだったが、やってみると非常に難しい問題でした。まず考えたのは、全ての場合について、最短経路がどうなるか手で計算するという方法です。x, yの正負と奇偶より16通り + x, yのいずれかが0かつそれぞれの奇偶より8通り + x, yの両方が0という1通りで、全部で25通りの場合があります。このそれぞれについて調べます。abs(x)+abs(y)の最短のケースか、それに2か4を足すケースのいずれかになります。他の人のコードを見てみたところ、この戦略で解いている人がほとんどでした。

解説記事によると、25通りのケースは15通りまで減らすことができるそうです。理由は、xとyの対称性らしいのですが、ここはうまく理解できませんでした。また他のアプローチとして、ある範囲内の全ての経路をbfsで探索する方法。ゴールと現在地とのユークリッド距離が最小になるよう、一歩ずつ進んでいく方法が紹介されていました。そこで練習のため、bfsのアプローチを実装してみました。

かなり時間がかかってしまったのですが、なんとかできたと思います。しかし、入力が大きくなると、uncaught exceptionという例外が発生し、システムテストに落ちてしまいます。ローカルだと少し時間がかかっているようなのですが、解は出ています。疲れたので、原因究明は保留とします。

class Pathfinding {
public:
  set <pair<int, int> > visited;
  queue <pair <pair<int, int>, int> > q;
  int lx, ux, ly, uy;
  pair <int, int> goal;

  int bfs(int a, int b)
  {
    pair <pair <int, int>, int> cur;
    pair <int, int> t(a, b);
    pair <pair <int, int>, int> s(t, 0);
    q.push(s);
    visited.insert(t);

    while (!q.empty()) 
      {
	cur = q.front();
	q.pop();

	if (cur.first == goal)
	  break;
	
	pair <int, int> tmp;
	if (cur.first.second % 2 == 0)
	  {
	    tmp.first = cur.first.first+1;
	    tmp.second = cur.first.second;
	  }
	else
	  {
	    tmp.first = cur.first.first-1;
	    tmp.second = cur.first.second;
	  }

	if (lx <= tmp.first && tmp.first <= ux && ly <= tmp.second && tmp.second <= uy && visited.find(tmp) == visited.end())
	  {
	    visited.insert(tmp);
	    pair<pair<int, int>, int> t(tmp, cur.second+1);
	    q.push(t);
	  }

	if (cur.first.first % 2 == 0)
	  {
	    tmp.first = cur.first.first;
	    tmp.second = cur.first.second+1;
	  }
	else
	  {
	    tmp.first = cur.first.first;
	    tmp.second = cur.first.second-1;
	  }

	if (lx <= tmp.first && tmp.first <= ux && ly <= tmp.second && tmp.second <= uy && visited.find(tmp) == visited.end())
	  {
	    visited.insert(tmp);
	    pair<pair<int, int>, int> t(tmp, cur.second+1);
	    q.push(t);
	  }
      }

    return cur.second;
  }

  int getDirections(int x, int y)
  {
    goal.first = x;
    goal.second = y;

    if (x > 0)
      {
	ux = x + 2;
	lx = -2;
      }
    else if (x < 0)
      {
	ux = 2;
	lx = x - 2;
      }
    else
      {
	ux = x + 2;
	lx = x - 2;
      }

    if (y > 0)
      {
	uy = y + 2;
	ly = -2;
      }
    else if (y < 0)
      {
	uy = 2;
	ly = y - 2;
      }
    else
      {
	uy = y + 2;
	ly = y - 2;
      }

    return bfs(0, 0);
  }
};