Atcoder Beginner Contest 085 感想と解説

Atcoder Beginner Contest 085の感想。
B問題まではさっと解けてうれしかった。
C問題は計算量の問題でアルゴリズムをもっと勉強しないといけないなあ。

A問題

文字列の4番目の文字を変える問題。
replaceを使ったが、S[3] = '8'でできたみたい。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include<cstdio>
using namespace std;
 
int main()
{
	string S;
 
	cin >> S;
	
 
	S.replace(3, 1, "8");
	cout << S << endl;
 
	return 0;
}

B問題

下の餅より上の餅が小さいときだけ積み重さねることができる条件で
何段積み上げることができるかという問題。
配列内での同じ数字を削除すればいいので、
重複削除を行えばおけ。

uniqueで重複削除を行い、残ったゴミをeraseで削除。
Atcoderの解説ではを使えばもっと楽にできるらしい。
setが重複不可のコンテナを作ってくれる。
もっと勉強しななあ。

参考
qiita.com


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include<cstdio>
using namespace std;
 
int main()
{
	int N, x;
	vector<int> d;
 
	cin >> N;
	
	for(int i=0; i<N; i++)
	{
		cin >> x;
		d.push_back(x);
		sort(d.begin(), d.end());
		d.erase(unique(d.begin(), d.end()),
                            d.end());
	}
	cout << d.size() << endl;
	return 0;
}

C問題

計算量に気をつける問題。
本番はよくわからずにあきらめちゃったので、解説を見て
復習。
O(N3乗)だとTLEなのでO(N2乗)で実装しないといけない。

|

#include
#include
#include
#include
#include
#include
using namespace std;

int main()
{
int N, Y;
int x, y, z;
x = y = z = 0;

cin >> N >> Y;
for (x = 0; x <= N; x++) {
for (y = 0; y <= N - x; y++) {
z = N - x - y;
if (x + y + z == N && 10000 * x + 5000 * y + 1000 * z == Y) {
cout << x << " " << y << " " << z << endl;
return 0;
}
}
}

cout << "-1 -1 -1" << endl;
return 0;
}

C問題まで解けるようになりたい。