SRM 373 250pt: StringFragmentation

TopCoder

問題概要

H*W(H,W<10000)のサイズのディスプレイがある。単語が複数あるので、単語を行からはみ出さないように配置する。フォントのサイズを最大いくつにできるか求める問題。

考えたこと

  • 二分探索っぽいけどこれくらいなら全探索で通る。
  • フォントのサイズを固定したときの判定部分を書くだけだし、特に難しい所もなさそう。でも場合分けが出てきてしまう。
  • ちょっと考えたけど場合分けが回避できない。
  • 書けたけどキレイじゃなくて自信無い。投げたらちゃんと通ってた。

practiceで通ったコード

#include <string>
#include <vector>
#include <sstream>
using namespace std;


struct StringFragmentation {

	int largestFontSize(string text, int width, int height) {

		//数値に変換
		vector<int> nums;
		stringstream ss(text);
		string buf;
		while(ss>>buf){
			nums.push_back( (int)buf.size() );
		}
		const int N = nums.size();

		for(int sz=10009; sz>7; sz--){
			int row_count = 1;
			bool ok = true;

			for(int i=0, cur=0; i<N; i++){
				int w = (sz + 2)*nums[i];
				if(cur==0){
					if(w > width){
						ok = false;
						break;
					}
					else{
						cur += w;
					}
				}
				else{
					if(cur + w + sz + 2 > width){
						cur = 0;
						row_count++;
						i--;
					}
					else{
						cur += w + sz + 2;
					}
				}
			}

			if(ok && row_count * 2*sz <= height){
				return sz;
			}
		}

		return -1;
	}

};

バグを減らす工夫

  • 場合分けが出てきたらとにかくコメント書くようにしよう。意識しないと間違えやすいしデバッグもしにくくなる。