読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 9/10/11

yukicoder

- 9 モンスターのレベル上げ

  • 問題概要

モンスターのレベル上げをする。
手持ちのモンスターの一番弱いもの(レベルが一番低い、複数いるなら一番戦闘回数が少ない)を戦闘に参加させます。
敵モンスターが円上に並んでいて、どこから戦闘を始めてもいいとき、最も戦闘回数が多くなるモンスターの最小の戦闘回数を求めよという問題です。

  • 解説

全ての戦闘開始位置を試して、実際に戦闘シミュレーションしましょう。
このとき、一番弱いものをどうやって決めるかですが戦闘ごとにO(N)で求めていてはO(N^3)となり間に合いません。
そこでヒープを使ってやれば最小値取りだし、要素の追加がO(\log N)でできるので計算量がO(N^2 \log N)となり計算が間に合います。
pairを使うと辞書順比較を自動で行ってくれるので実装が楽になると思います。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

int a[1500], b[1500];
typedef pair<int, int> P;
const int inf = 1e9;
int main(void){
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < N; i++)
	{
		cin >> b[i];
		b[i] >>= 1;
	}

	int res = inf;
	for (int i = 0; i < N; i++)
	{
		int maxim = 0;
		priority_queue< P ,vector<P>,greater<P>> que;
		for (int j = 0; j < N; j++)
		{
			que.push(make_pair(a[j], 0));
		}
		for (int j = 0; j < N; j++){
			int now = i + j;
			now = (now < N) ? now : now - N;
			auto p = que.top(); que.pop();
			//printf("(%d,%d)-%d\n", p.first, p.second,b[now]);
			p.first += b[now];
			p.second++;
			maxim = max(maxim, p.second);
			
			que.push(p);
		}
		res = min(res, maxim);
		
	}
	cout << res << endl;

	return 0;
}

- 10 +か×か

  • 問題概要

{tex:p_i}を演算子とし、T_n=A_n (p) T_{n-1},T_1=A_1という式があります。
p_i={+,*}としたとき、T_N=Totalとなるような辞書順最小のp_1,p_2,p_Nを求めよという問題です。

  • 解説

順番に演算子をどうするか決めていくと計算量がO(2^N)となってしまいます。
開始位置が[tex:A_1,終了時の値がTotalと一意に定まっているので両側探索を使えばO(2^\frac{N}{2})で押さえられます。
使った演算子の集合はbitで管理すれば衝突判定のO(\frac{N}{2})だけで必要コストはすみます。
計算量はO(\frac{N}{2}2^\frac{N}{2}),結構バックトラックの枝刈りをしてますがテストケース次第では落ちるかもです。

別解というか想定解というか普通にDPすれば50*10^5で計算できます。
dp(n,v)が存在するならばdp(n+1,v*a[n]),dp(n+1,v+a[n])が存在、というようにして配列の存在する箇所に状態としてbitで管理してやればできます。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
#define LL long long
int N, M;
LL Total;
LL exist[100001];
LL a[100];

LL res1, res2;
inline int check(int a, int b){
	while (a != 0 || b != 0){
		if ((a & 1) != (b & 1))break;
		a >>= 1;
		b >>= 1;
	}
	return (a & 1) < (b & 1);


}
void prev(int n,LL val,int bit){
	if (n == M){
		if (exist[val] == -1 || check(bit, exist[val]))
		exist[val] = bit;
		return;
	}
	if (val%a[n] == 0)prev(n - 1, val / a[n], bit + (1 << (n - M - 1)));
	if (val - a[n]>0)prev(n - 1, val - a[n], bit);
	return;
}


bool next(int n, LL val, int bit){

	//cout << "next:" << n << endl;
	if (n == M){
	//	cout << val << endl;
		if (exist[val] != -1){
			res1 = bit; res2 = exist[val];
			//cout << val << endl;
			return true;
		}
		return false;
	}
	if (val + a[n+1] <= Total)if (next(n + 1, val+a[n+1], bit))return true;
	if (val*a[n+1] <= Total)if (next(n + 1, val*a[n+1], bit + (1 << n)))return true;

	return false;

}
int main(void){
	cin >> N >> Total;
	for (int i = 0; i <= 100000; i++)exist[i] = -1;
	for (int i = 0; i < N; i++)cin >> a[i];
	M = N / 2;
	prev(N - 1, Total, 0);
	next(0, a[0], 0);
	for (int i = 0; i < N/2; i++)
	{
		if (res1&(1 << i))cout << '*'; else cout << '+';
	}
	for (int i = 0; i < (N - 1) / 2; i++){

		if (res2&(1 << i))cout << '*'; else cout << '+';

	}
	cout << endl;

	return 0;
}

- 11 カードマッチ

  • 問題概要

マークがW種類,数字がH種類のカードが1枚ずつ計H*W枚あります。
手持ちにN枚持っているとき,手持ちのカード1枚とマークもしくは数字が一致するカードが手持ち以外のカードの中に何枚あるか答えよという問題です。

  • 解説

まず手持ちに存在するマークがw種類、手持ちに存在する数字をh種類とします。
全カードのうち、手持ちに存在する数字と同じ数字を持つカードはh*W枚です。
同様に全カードのうち手持ちに存在するマークと同じマークを持つカードはw*H枚です。
上の二つのカードのうち、重複するカードの枚数はh*w枚です。
したがって全カードのうち手持ちに存在する数字もしくはマークと一致するカードの枚数はw*H+h*W-h*w枚です。
このカードには手持ちのカードが全て含まれているので、Nを引けば目的のカードの枚数となります。

このくらい簡単な方除定理なら思いつくんですけどね、、、

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
bool mark[1000001],num[1000001];
#define LL long long
int main(void){
	LL H, W, h = 0, w = 0;int  N;
	cin >> H >> W >> N;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		if (mark[a] == false)h++;
		if (mark[b] == false)w++;
		mark[a] = mark[b] = true;
	}
	cout << h*W + w*H - h*w - N << endl;;
	return 0;
}