BottomCoder SRM 380 div2

TopCoder

SRM 380 div2

points result time
250 AC 3.5m
500 AC 10m
1000 WA 30m+2h?

むずいでーす

250

lucky ticketとは、2n文字の数字列で、前半のn文字と後半のn文字の数字の和が等しいものをいう。数字列s(||<=50)の連続した部分文字列でlucky ticketになるもののうち最大のものの長さを求めよ。存在しない場合は0を答えよ。

n=|s|/2→1の順に全探索。最初に見つかったlucky ticketのnが答え。

public class LuckyTicketSubstring {

	public int maxLength(String s) {
		int n = s.length();
		for(int i = n / 2;i >= 1;i--){
			for(int j = 0;j <= n - i * 2;j++){
				int sum = 0;
				for(int k = j;k < j + i;k++){
					sum += s.charAt(k)-'0';
				}
				for(int k = j + i;k < j + 2*i;k++){
					sum -= s.charAt(k)-'0';
				}
				if(sum == 0){
					return i*2;
				}
			}
		}
		return 0;
	}

}

500

右方向の動きしかできないknightがある。これがn*m(たてnよこm)のチェス盤で動くとき、1連の動きの中で最大何状態とれるか。ただし、5状態(4ステップ)以上とれるときは、knightのとれる4通りの動きすべてが最低1回ずつ含まれていなければならない。

ひどい場合分け問題。knightの動きの制限から、knightは左端の列から動かせば良い。
n=1のときは動けないのでret=1.
n=2のときは、(+2,-1),(+2,+1)を繰り返す動きしかできない。5状態制限があるので、4状態までしかとれない。ret=min([(m+1)/2],4).
n>=3のときは、隅からはじめて、(+1,+2),(+1,-2),(+2,-1),(+2,+1)の順に動くことで4通りの動きを実現できる。なるべく多く動きたいので、5状態以降は(+1,+2),(+1,-2)を繰り返せば良い。ret=m-2 (m>=7)
5状態制限が掛からない範囲では(+1,+2),(+1,-2)を繰り返せば良い。m<=4ではret=m.
m=5,6ではどうやっても4状態までしかとれない。ret=4.

public class LameKnight {

	public int maxCells(int height, int width) {
		if(height == 1){
			return 1;
		}else if(height == 2){
			return Math.min(1 + (width-1) / 2, 4);
		}else{
			if(width <= 6){
				return Math.min(width, 4);
			}else{
				return width - 2;
			}
		}
//		return 0;
	}

}

1000

n(<=50)種類のカードの各々の枚数(<=5*10^8)と、Jokerの枚数(<=5*10^8)が与えられる。これらから次の条件のいずれかを満たすデッキを作るときの作れるデッキの最大数を求めよ。

  • n種類のカードをどれも1枚ずつ使ったデッキ
  • n-1種類のカードを1枚ずつ使い、残った1種類をJokerで埋めたデッキ

最初勘違いしててJokerいくらでも使っていいのかと思ってたけど直しても駄目だった。
自分なりの考え方。まずn種類のカードを枚数で昇順ソートする。これを、横-種類,縦-枚数でヒストグラムのようにブロックを積み上げた形にする。条件1を満たすデッキは横1列にすべての種類のブロックが揃っているもの、条件2を満たすデッキは横1列で1個だけ穴が空いててそこにjokerを入れるようにするもの、と解釈できる。
まず最小の種類のカードをX、枚数をc[0]とする。Xを使った条件2のデッキは、X以外の種類のカードのブロックが1個欠けることになる。1種類での全体の枚数を保つために、欠いたブロックを上の方に積み上げる。こうすると、上に積み上げるブロックの数は、「Xを使った条件2のデッキ」の個数に等しい。また、上に積み上げるカードの種類はX以外なら任意だが、積み上げた結果「Xを抜いた条件2のデッキ」の個数ができるだけ多くなればいいので、その時々で高さが一番低いところのカード種類をみつけて上に積み上げる。
今最大化したいのは、条件1を満たすデッキの個数+「Xを使った条件2のデッキ」の個数+「Xを抜いた条件2のデッキ」の個数。この和をSとおき最大値を2分探索で見つける。あるSで、これを満たすデッキ構成が存在するかどうかを考えればよい。
条件1を満たすデッキの個数をpとすると、「Xを使った条件2のデッキ」は最大c[0]-p個できる。このとき、「Xを抜いた条件2のデッキ」の個数はS-(c[0]-p)-p=S-c[0]個以上できなければならない。さらに、jokerは条件2のデッキすべてに1枚ずつ使われるので、jokers>=c[0]+(c[0]-p)でなければならない。前者は(足りない枚数的な意味で)\sum_i max(S-c[i], 0)<=c[0]-pと定式化できる。どちらの式もpの不等式に簡単に変換できる。

p>=2*c[0]-jokers (joker)
p<=c[0]-\sum_i max(S-c[i], 0) (needed)

あとはこれらを満たすpが、[0,c[0] ]の範囲に存在すれば良い。具体的には(joker)<=(needed)かつ(needed)>=0が成り立てば良い。((needed)<=c[0]だから)

コード掲載はちょっとあとで。