Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-06-20TCO2010 Round1

TCO2010 Round1 250 EqualizeStrings

| 16:24 | TCO2010 Round1 250 EqualizeStrings - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round1 250 EqualizeStrings - SRM diary(Sigmar) TCO2010 Round1 250 EqualizeStrings - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→1文字ずつGreedyで良さそう

→とりあえずs[i]とt[i]で小さい方を使えば良いのでは

→違う、サンプルを見るとs[i]とt[i]が遠いときは'a'にすべきみたい

→条件を考える・・・s[i]とt[i]の距離が13未満なら2つのうち小さい方を使う、13以上なら'a'を使う、で良いようだ

→書く→サンプル通る

→簡単すぎる・・・本当に大丈夫か?

→例外ケースは・・・ありそうにない・・

→提出!500へ


チャレンジフェーズ

→あまり落とせそうなパターンが思いつかない

→落とされてる人もいるけど・・明らかに間違った書き方をしてる人みたいだ


システムテスト

→Passed


以下、ソースです

class EqualizeStrings { 
public: 
  string getEq(string s, string t) { 
    string res; 

    for(int i=0; i<(int)s.size(); i++) { 
      int a=s[i]-'a', b=t[i]-'a';
      if(max(a, b)-min(a, b)<13) res.push_back(min(s[i], t[i])); 
      else res.push_back('a'); 
    } 
    return res; 
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100620