SRM 369 250pt: BeautifulString

TopCoder

問題概要

AとBの文字をつなげてできるだけ長い文字を作りたい。ただしA,Bの使用回数は上限countA, countB(<10^6)で、A,BはそれぞれmaxA, maxB(<10^6)回より多く連続してはならない。最大の長さを求める問題。

考えたこと

  • サンプル弱すぎて不安だ。
  • ABAB...ABみたいな感じに並べて、後から追加できるだけ追加すれば良さそう。
  • Aから始まる場合とBから始まる場合、みたいに場合分けするのはイヤだ。
  • Aのブロックの数を固定したらBのブロックの数は±1に収まる。
  • サンプル通った。提出する。
  • 落ちた。maxAやmaxBが0のときは前提が崩れている。流石にこれは場合分けするか…。
  • 通った。

practiceで通ったコード

計算量O(countA)。

#include <algorithm>
using namespace std;

typedef long long int64;

struct BeautifulString {

	int maximumLength(int64 countA, int64 countB, int64 maxA, int64 maxB) {

		//maxA=0とmaxB=0は特別処理
		if(maxA==0 || maxB==0){
			return max(min(countA, maxA), min(countB, maxB));
		}

		int64 ret = 0;

		for(int x=0; x<=countA; x++){
			for(int y=x-1; y<=x+1; y++)	if(0<=y && y<=countB){
				ret = max(ret, min(x*maxA, countA) + min(y*maxB, countB) );
			}
		}

		return (int)ret;
	}

};

他の人の解法

Petr先生のコードがワンライナーのO(1)解法だった。内容はよく把握していないけど、O(1)はあってしかるべきという気がする。
上位陣を見てもmaxA=0の場合分けをしている人が多かったし、そもそも正答率がそんなに高くなかったようだ。