と戦う

区分アルゴリズムぶんかつアルゴリズム:ダイナミックプログラミングダイナミックプログラミング

質問する

かつて格闘家として知られたアームストロングさんは「力比べ」という試合を主催し、全国に宣伝した.求人広告を見て、全国各地に人が集まったのは、求人広告が「力」を定義していないためだ.
ジムでは、3対500の人が筋肉おじさんから有名なRPGゲームのパワー(STR)が高い人まで、いろいろな力で集まっています.
ヒムストロングさんはふと「知っていることは力だ」という名言を思い出した.予選では、常識問答で参加者の力を数値化し、その数値で本参加者を選出する.
こうして、出場者数N人が決勝戦に進出した.しかし予想に反して決勝は赤と青の2チームに分かれて行われた.
N人の参加者が並んで立っている.ヒム・ストロングさんは、1からN∮1の数のボールを含む抽選箱からランダムに1つを抽出して基準線を選択します.例えば、3番と書かれたボールを選択すると、3番と4番の参加者の間が基準線になります.基準線より左が赤、右が青.
1セットで勝負を決める.各チームの一番強い人が出てきた後、二人は力を比べた.もっと力のある人が勝って、ゲームは終わります.力の大きさが同じで,勝つ人はいない.
ギャンブラーの金某氏(以下、金ギャンブラー)は試合開始前に参加者リストを手に入れた.基準線の位置によって、どのチームが勝つかを事前に知っていた金賭博会社は、すべての財産を勝率の高い側に置く見通しだ.金賭博師は全財産をどのチームに預けなければならないのか.
基準線は選手と選手の間にしかありません.チームは1人以上でなければなりません.
入力
1行目にはn人います.Nは1000000以下の偶数である.
2行目には、1番からN番までの力を表す整数が与えられています.一人一人の力は10000以下の自然数である.
しゅつりょく
金賭博師はレッドカードを打つべきで、R、青札を打つべきで、Bを印刷します.両チームが勝つ確率が同じなら、Xを出力する.
入力例1
6
9 15 18 7 13 11
サンプル出力1
R
例入力1では、赤チームが勝つ確率は60%、青チームが勝つ確率は40%である.
入力例2
10
26 25 9 27 7 30 15 20 8 16
サンプル出力2
B

問題を解く

1人に1～5の標準点を指定するとき、ゲームを勝ち取るための核心は最大の数字がどこにあるかです.最大数は右、青チーム勝利、最大数は左、赤チーム勝利.このように実施すればよいのではないか,少し考えなければならない.
最大の数が複数ある場合です.ある基準点を対象として,左,右に最大数が同一であれば,問題に勝つ者は存在しない.つまり、これは考える必要のない場合の数です.したがって、最大の数字がいくら出ても、最終的には最大の数字の中で両端の位置だけを考慮すればよいことを考慮しなければならない.
例
3 2 5 10 6 8 10 9 1 10
上記の場合、最大数の位置は4,7,10である.
各人間のインデックスを1-9として指定すると、4-9番目の標準点には両方に10が存在するため、勝者がいない場合は数字になります.そのため、最大数の中で一番左の4番と一番右の10番だけを考えて、勝つかどうか考えることができます.

ソースコード

#include <bits/stdc++.h>

using namespace std;

int n, maxNum;
int strength[1000001];
vector<int> locate;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 1; i < n + 1; i++) {
		int input;
		cin >> input;
		strength[i] = input;
		if(input == maxNum) {
			locate.push_back(i);
		}
		else if(input > maxNum) {
			maxNum = input;
			locate.clear();
			locate.push_back(i);
		}
	}
	
	solve();
	
	return 0;
}


void solve() {
	int rCnt, bCnt;
	
	bCnt = locate[0] - 1;
	rCnt = n - locate[locate.size() - 1];

	if(rCnt > bCnt) {
		cout << 'R' << endl;
	}
	else if(rCnt == bCnt) {
		cout << 'X' << endl;
	}
	else if(rCnt < bCnt) {
		cout << 'B' << endl;
	}
}

題出所:https://www.acmicpc.net/problem/172512

カイドウ草が白駿で「そうだ!!」判定を受けた