Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1373-8975094c
この記事にトラックバックする(FC2ブログユーザー)

Open 2010 Round 1 EASY - EqualizeStrings (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 1 EASY (250pt)
Problem Statement
Open 2010 Algorithm Round 1 自分の参加記録

問題概要

アルファベット小文字からなる2つの同じ長さの文字列sとtが与えられる.
同じ文字列に変形したい.
1回の操作で,1文字を1つ次の文字,1つ前の文字に変えれる,aの前の文字はz,zの次の文字はa.
最小回数で,同じ文字列にしたとして,その文字列を求める問題.
複数候補があるなら,辞書順最小のものを求める.

解法

1文字ずつ考えれば良い.
全部の文字への変換距離を求めて最小のもののうち,辞書順最小を求めても良いし,
aとzのつながっているループ考えずに,2つの文字の距離が13未満なら,z→aの部分を経由できないので,小さい方,そうでなければ,aにする,とかでも良い.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int ab(int x){ if(x<0) return -x; return x; }

class EqualizeStrings {
public:
string getEq(string s, string t) {
  int i,a,b;
  string res;

  rep(i,s.size()){
    a = s[i]-'a';
    b = t[i]-'a';
    if( ab(a-b)<13 ){
      if(a<b) res += (char)(a+'a');
      else res += (char)(b+'a');
    } else {
      res += 'a';
    }
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1373-8975094c
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。