Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-09-25KISSの原則 その3

KISSの原則 その3

| 22:27 | KISSの原則 その3 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 その3 - SRM diary(Sigmar) KISSの原則 その3 - SRM diary(Sigmar) のブックマークコメント

の続き。考え方をシンプルにすることで楽に解くための考察。


少し趣向を変えますがコーディング時間を短くする工夫について。


SRM421 Div2 1000 FloorIndicator

Problem Statement

1階から10^N-1階までの階があるビルがある。エレベータ内の階の表示は丁度N桁の数で表される。(0で始まる表示でも良い)

各数字は5×3のランプで表示される。0~9の表示を以下に示す。(#が点灯)

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

数字の境界は1列の消灯ランプで表される。

なお、いくつかのランプが壊れており、常に消灯されている。(どれが壊れているか分からない)

あるランプ表示のパターンが与えられるので、可能性のある全ての階の平均を取ったものがいくつになるか答えよ。

可能な階が一つもない場合は-1を返せ。

double averageFloor(int N, vector <string> indicator);

1<=N<=9

indicator.size()=5

indicatorの要素は4*N-1文字

indicatorの要素は'#'と'.'のみで構成される

indicatorの中で各数字の区切り線となるはずの列の要素は全て'.'


indicatorの例は以下のようなの。

{"###.###",
 "#.#.#.#",
 "#.#.###",
 "#.#...#",
 "###.###"}

この場合、1文字目は0もしくは8、2文字目は9もしくは8となる。

解は09,08,89,88の平均を取って48.5


以下、僕の考える解答例です。


解法自体は比較的ストレートフォワード。

各数字を表す3*5のランプがどの数字となりうるかを調べる。

つまり、0~9を表すパターンに対して、indicatorが'#'となっているところが全て'#'であればその数字となりうる。

逆に言えば、indicatorが'#'で、数字パターンが'.'であるところが一つでもあれば、その数字にはならない。

各桁は独立に考えられるので、各桁の平均値を取って足し合わせれば良い。

候補となる数字が1つもない桁があれば、解は-1になる。


では何が大変かというと、実は数字のパターンを作るのが一番面倒な気がします。

手動で作ると、それだけでかなり時間を食います。やってみてください。

各行について、3文字分ずつコピーして、貼りつけて、コピーして、貼りつけて、・・・、1数字につき5行で10数字分、合計50回もコピペしていられません。

(AA用エディタを使えば長方形領域をコピーできるので10回で済みますが・・・)

問題文に与えられた文字列をそのまま使うのが楽だと思います。

文字列の整形は人間でなく機械にやらせるということです。


ということで、以下ソースコード例です。

Topcoderでは仮引数名を勝手に変えても問題ないのでindicatorはindに変えてます。


class FloorIndicator {
public:
	double averageFloor(int N, vector <string> ind) {
		double res=0;
		vector <vector <string> > dig(10, vector <string>(5));
		string org[5]={
			"###...#.###.###.#.#.###.###.###.###.###", 
			"#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
			"#.#...#.###.###.###.###.###...#.###.###", 
			"#.#...#.#.....#...#...#.#.#...#.#.#...#", 
			"###...#.###.###...#.###.###...#.###.###"
		};
		
		//数字パターンのparse
		//dig[j]に数字jの3*5のパターンを格納する
		for(int i=0; i<5; i++) {
			int idx=0;
			for(int j=0; j<10; j++) {
				for(int k=0; k<3; k++) {
					dig[j][i].push_back(org[i][idx]);
					idx++;
				}
				idx++;
			}
		}

		//各桁について候補として可能な数字をcandに格納
		vector <vector <int> > cand(N);
		for(int i=0; i<N; i++) {
			for(int j=0; j<10; j++) {
				bool ok=true;
				for(int k=0; k<5; k++) {
					for(int l=0; l<3; l++) {
						if(ind[k][i*4+l]=='#' && dig[j][k][l]=='.') {
							ok=false;
							break;
						}
					}
				}
				if(ok) cand[i].push_back(j);
			}
		}

		//candから各桁の平均を算出し、解を出す
		res=0;
		for(int i=0; i<N; i++) {
			if(cand[i].empty()) return -1;
			double sum=accumulate(cand[i].begin(), cand[i].end(), 0);
			double ave=sum/cand[i].size();
			res*=10;
			res+=ave;
		}
		return res;
	}
};

ところでこのプログラム、書いてから思いましたがすごく勿体無いことをしています。

indicatorのparseと、問題文で与えられる数字のパターンのparseは本質的に同じことをしているはずなのに、違うコードを書いています。

同じことをするプログラムは関数化して再利用すべきですね。

逆に言うと、この問題を見たときに、同じparseのプログラムが使えることに気づかなければならないんだと思います。そうすれば、そもそも数字パターンを手動入力しようなどとは思わないでしょう。


結構、こういう文字列パターンが問題文で与えられる問題はあります。

手動でパターンを分解したりすると意外と大変だったりするので、こういうテクニックが役立つときがあります。


  • 文字列等の整形はなるべくプログラムでやる。

 手動でやるよりはるかに早い場合があります。


続きがあるかも

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