TopCoder SRM 678 Div1 Easy ANewHope、Div2 Medium AttackOfTheClones

SRM678は不参加。Easy/Medium共にそこそこの速度で一発AC出たので、本番出ておきたかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=13585

問題

1週N日からなるカレンダーの地域で、N枚のTシャツを着まわす。
1週のうち、各Tシャツは１日ずつしか着られない。
また、一度着たTシャツは次着るまで選択が必要なため、最短D日後でないと再び着ることができない。

1週目のTシャツの割り当てと、最終週のTシャツの割り当てが与えられる。
そのような割り当てを実現するには、最短何週必要か。

なお、Div2 MediumはD=N-1固定である。

解法

S=N-Dとすると、週ごとにでTシャツは最大S日前倒しでき、逆に後ろに倒すのは何日でも可能である。
そのため、Tシャツのうち1週目と最終週で最も前に持ってきたいものの日数をA日とすると、ceil(A/S)週が解となる。

ceil(A/S)が解なのは凡そ予想はつくが、これだけだと確信は持てないかもしれない。
以下のように割り当てると実際ceil(A/S)週で割り当て可能である。

• 各Tシャツを着る日は後ろににはいくらでもずらせるので、各週において他のTシャツがS日を超えて前倒ししない範囲で、後ろから順にTシャツ順を確定させる。
• こうすると最小でも後ろから毎週S個ずつ確定できる。

class ANewHope {
	public:
	int count(vector <int> firstWeek, vector <int> lastWeek, int D) {
		int N=firstWeek.size();
		int shift=N-D;
		int ma=1;
		int x,y;
		FOR(x,N) FOR(y,N) if(firstWeek[x]==lastWeek[y] && y<x) {
			int d=x-y;
			ma=max(ma,(d+shift-1)/shift+1);
		}
		return ma;
	}
}

まとめ

ずいぶん服が乾きにくい地域だ。