Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-06-20TCO2010 Round1

250だけ解いて辛うじてRound2に進みました・・

レーティングは微減ですが1問パスしただけでも少し持ち直した気がします

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; 
  }
};

TCO2010 Round1 500 TwoRegisters

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

Problem Statement

問題を見る

DP

→状態数が、100万*100万

→無理そう

→難しい・・・・とりあえずBFSで小さい値の解を列挙してみよう

→書く→サンプル通る

→ダメだ、何の法則性も見えない・・・・でも、解はそんなには長くならないみたい。フィボナッチ数列に近いので、100万でも高々30程度かな。

→どちらにせよBFSでは解けない。どうしよう・・・グラフ?でもない・・・行列?無理だな・・何も効率化できない。何か枝刈りができるのか・・・分からない・・

→何これ。こんなの解けるの?(一時間くらい色々唸る)


→とりあえず、何となくXとYの最終値から逆順に計算するのも考えてみようかな

→あれ?なぜか枝分かれができない

→あ・・そうか・・大きいほうから小さい方を減算する以外の方法がないから、分岐しない。

→すごく不思議な感じがするけど、Treeだったんですね。。これで全探索できそう

→書いた→答えが合わない

→あ、YがXより大きいときにXとYの値をスワップしてたから何か答えの文字列がおかしくなってる

→直らない~~~

→終了


チャレンジフェーズ

→BFSしてる人はいないかな~~

→一人だけいたけど、撃墜済み・・

何もできず


終了後

とりあえずスワップのおかしかったところを直す

TLEしますね。。100万*100万だから当然ですね。

→とりあえず100万でも最大30程度の長さになると想定されるので、40を超えることはないだろう。40を超えると探索をやめることにする。

→これで40*100万で最大4000万回くらいの計算量になったけど・・・まだTLEする

→string.insertを4000万回やっているのがまずいみたい。insertしないように書き換える。

→100万で1秒以内になった。


これまでにも、逆順に計算してみるという問題は何度も出てきているのに、試さなかったのは失敗でした。逆順で意味があるか分からなくても、少し考えてみることが必要そうです。


以下、終了後に書いたソースです。一応システムテストは通ります。

長さ40以下になる確証は何もないので、他の人がやっているようにまずは長さ最小になるX,Yの値を全部求めてから文字列比較を行うのが確実のようです。

const int INF=1000000000;

class TwoRegisters {
public:
	string minProg(int r) {
		string res;
		int minl=INF;
		string tmp;

		for(int i=1; i<r; i++) {
			int a=r, b=i, cnt=0;
			tmp.assign(40, ' ');
			while(a>1 || b>1) {
				if(a==b) {
					cnt=minl+1;
					break;
				}
				if(a>b) {
					a-=b;
					tmp[cnt]='X';
				} else {
					b-=a;
					tmp[cnt]='Y';
				}
				cnt++;
				if(cnt>minl || cnt>=40) break;
			}
			string tmp2=tmp.substr(0, cnt);
			reverse(tmp2.begin(), tmp2.end());
			if(cnt<minl || (cnt==minl && tmp2<res)) {
				minl=cnt;
				res=tmp2;
			}
		}

		return res;
	}
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100620