kojingharangの日記

Google code jam 2017 Round1C B. Parenting Partnering

21:14 |

• C,Jが1日のうち半分ずつ子守をする。C,Jそれぞれ子守できない予定(時間帯)が決まっている。
• 子守役を入れ替える回数の最小値を求めよ。

• 半分ずつ子守をしなくていいとしたときの最低交換回数 + 半分制約ありで隙間時間を割り当てた時の追加交換回数 でいいだろう
• 予定と予定の間の隙間時間は、「前 or 次」の予定が「C or J」の 4 種類に分類できる。
• 前と次の予定がどっちも C である隙間時間(★)に C が子守すると往復で 2 回の追加交換が必要。追加コストを払ってしまえば C, J どちらにどちらでも割り当てられるので、その隙間時間についてコストはそれ以上増えない。
• J も同じ。
• それ以外は追加コスト 0
• なので
• どちらに割り当てても良い時間の残り RestC, RestJ から
• ★なものを追加コストがかからないように優先して割り当てる(あとで回数が問題になるので短い順に見る)
• どちらに割り当ててもよい時間を割り当てる
• 残りをしかたなく追加コストを払って★から割り当てる

• という方針でいいだろう
• ここまではわりとすぐ

• 隙間を列挙する、最低交換回数を求めるあたりで大ハマリ。
• sample 実行したら、日の最初と最後が違う人なら交換回数に含めなきゃいけないのに気づく
• →隙間列挙が場合分けコードでどんどん汚くなりバグりまくって焦る

• 残り30分であきらめて C に移動
• small は、掛け算だし最小のやつに fill してけばよかろう→これ以下ならfillするという値で二分探索→ 一発OK

• 残り15分で戻ってくるがバグバグでだめ

• (あとで)

• すっきり再実装、終了15分後にB small+large AC

• 実装ゲーは相当落ち着いてやらないといかん。
• 🤔🤔

// 予定
struct Entry {
	ll s, e, type;
};

int main() {
	int test_cases;
	cin>>test_cases;
	ll A,B, s, e;
	REP(ttt, test_cases) {
		cin>>A>>B;
		ll ra = 720, rb = 720; // のこり割当時間
		ll fr = 1440; // どっちに割り当ててもノーペナな枠
		vector<Entry> es;
		REP(i, A) {
			cin>>s>>e;
			ra -= e-s;
			fr -= e-s;
			es.push_back(Entry{s, e, 1});
		}
		REP(i, B) {
			cin>>s>>e;
			rb -= e-s;
			fr -= e-s;
			es.push_back(Entry{s, e, -1});
		}
		VI pa, pb; // dur
		ll N = 1440;
		sort(ALL(es), [](const Entry& a, const Entry& b){return a.s<b.s;});

		ll ans = 0;
		ll M = es.size();
		REP(i, M) {
			ll ni = (i+1)%M;
			if(es[i].e%N != es[ni].s%N) {
				// すきまはっけん
				if(es[i].type == es[ni].type) {
					ll dur = (es[ni].s-es[i].e+N)%N;
					if(es[i].type==1) pa.PB(dur);
					if(es[i].type==-1) pb.PB(dur);
				}
			}
			if(es[i].type!=es[ni].type) ans++;
		}
		
		sort(ALL(pa));
		sort(ALL(pb));

		REP(i, pa.size()) fr -= pa[i];
		REP(i, pb.size()) fr -= pb[i];

		// ペナルティ回避
		REP(i, pa.size()) {
			ll use = min(ra, pa[i]);
			ra -= use;
			pa[i]-=use;
		}
		REP(i, pb.size()) {
			ll use = min(rb, pb[i]);
			rb -= use;
			pb[i]-=use;
		}

		// ノーペナ消費
		{
			ll use = min(ra, fr);
			ra -= use;
			fr -= use;
		}
		{
			ll use = min(rb, fr);
			rb -= use;
			fr -= use;
		}

		// ペナルティ
		REP(i, pb.size()) {
			ll use = min(ra, pb[i]);
			if(use) ans+=2;
			ra -= use;
		}
		REP(i, pa.size()) {
			ll use = min(rb, pa[i]);
			if(use) ans+=2;
			rb -= use;
		}
		assert(ra==0);
		assert(rb==0);

		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする