KOI地区公式戦2015小学校部分解答

2020. 7. 5筆
第一題
https://www.acmicpc.net/problem/10797
[問題の概要]
1行目に1つの数字、2行目に5つの数字が与えられると、
2番目に受信した5つの数字のうち、出力1番目に受信した1つの数字にはいくつかが含まれています.
パスが簡単すぎる
第二題
https://www.acmicpc.net/problem/10798
[問題の概要]
文字列を5行目に入力し、1行として出力します.
[コード]

#include <iostream>
#include <string>

using namespace std;

int main() {
	string words[5];
	for (int i = 0; i < 5; i++) {
		cin >> words[i];
	}

	for (int i = 0; i < 15; i++) {
		for (int j = 0; j < 5; j++) {
			if (words[j].length() > i) cout << words[j][i];
		}
	}

	return 0;
}

第三題
https://www.acmicpc.net/problem/10799
[問題の概要]
「(」と「)」からなるstringを入力すると、鉄棒の位置、長さ、レーザ光が発する位置がわかります.
このとき、レーザーで切断された鉄棒の破片の個数を求める.
[回答]
最終的な鉄条数がcount、括弧深さがdeptの場合、
countが上昇した場合,レーザ光を放出した場合(レーザ光に対応するロッド数が等しい)と終了した場合(1本のロッド長が終了した後+1)である.

parenthesis string을 처음부터 끝까지 순회하며,

 

'(' 이면, depth += 1

 

')' 이면, depth -= 1 하고

    바로 앞이 ')' 일 경우(레이져를 쏘는 경우), count += depth

    바로 앞이 '(' 일 경우(막대기가 끝나는 경우), count += 1

[コード]

#include <iostream>
#include <string>

using namespace std;

int main() {
	string p;
	cin >> p;
	
	int count = 0, depth = 0;

	for (int i = 0; i < p.length(); i++) {
		if (p[i] == '(') depth += 1;
		else {
			depth -= 1;
			if (p[i - 1] == '(')
				count += depth;
			else 
				count += 1;
		}
	}
	cout << count;
	return 0;
}

第四題
https://www.acmicpc.net/problem/10800
[問題の概要]
各プレイヤーには特定の色、特定の大きさのボールがあります.
各プレイヤーは他のプレイヤーのすべてのボールの次の特性を満たすだけで捕まえることができる.
イ)内孔寸法より小さい
ii)内孔と色が異なる
各プレイヤーにボールの色と大きさを与えると、各プレイヤーが引き付けるボールの数が出力されます.
[回答]
すべてのプレイヤーを巡回し、他のすべてのプレイヤーと比較すると、簡単に解決できますが.
そうすると時間の複雑さがO(N^2)になるので、この問題ではNの最大サイズが20万なのでタイムアウト(TLE)が発生します.
O(Nlogn)プール:
プレイヤーの球の配列をサイズ順に並べた場合、現在閲覧中の球は常に前に閲覧した球より大きいか等しい.
一つのボールを探索するときは、他のボールと比較するために、時間を無駄にしないで他のすべてのボールを探索します.
しかしサイズが同じで問題が厄介になるのでスタックを使って解決する.
変数の説明
count[n]:各色の現在の球サイズの和.
all:現在のすべてのボールのサイズの和.
結果[n]:出力する結果.(各プレイヤーが引き付けるボール数)

1. 각 player의 공에 대한 정보를 balls 벡터에 담아서 크기순으로 정렬

 

2. 크기가 작은 공부터 순회하며,

        이전 공의 크기와 달라졌으면,

                stack의 모든 ball들을 pop해서 count[]와 all에 반영

        

        현재 공을 stack에 push

        result[현재 공의 index] = all - count[현재 공의 컬러]

結果アレイ出力

[コード]

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

typedef struct ball {
	int idx, color, size;

	bool operator<(const struct ball & x) {
		return size < x.size;
	}
} ball;

using namespace std;

int n, all, result[200000], counts[200000];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	vector<ball> balls;
	stack<ball> st;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int c, s;
		cin >> c >> s;
		balls.push_back({ i, c - 1, s });
	}

	sort(balls.begin(), balls.end());
	
	int prev = -1;

	for (int i = 0; i < balls.size(); i++) {
		if (prev != balls[i].size) {
			while (!st.empty()) {
				ball b = st.top(); st.pop();
				counts[b.color] += b.size;
				all += b.size;
			}
		}
		result[balls[i].idx] = all - counts[balls[i].color];
		
		st.push(balls[i]);
		prev = balls[i].size;
	}

	for (int i = 0; i < n; i++) cout << result[i] << '\n';

	return 0;
}