ABC143 参加記録

少し日が空いてしまいました。
公式の解説を見る前に記述しています。

AtCoder Beginner Contest 143

A - Curtain

問題

Curtain.cpp

int main(void) {

	int A, B;

	cin >> A >> B;

	cout << (A > B * 2 ? A - (B * 2) : 0) << endl;

	return 0;
}

カーテン2枚分の長さを窓の長さから引けばヨシ。

B - TAKOYAKI FESTIVAL 2019

問題

TAKOYAKI_FESTIVAL_2019.cpp

int main(void) {

	int N;
	long long int sum = 0;

	cin >> N;

	vector<int> d(N);

	REP(i, N) cin >> d[i];

	REP(i, N){
		REPA(j, i + 1, N){
			sum += d[i] * d[j];
		}
	}

	cout << sum << endl;

	return 0;
}

ご丁寧に総和の数まで出してくれているので全パターン調べればOK。

C - Slimes

問題

Slimes.cpp

int main(void) {

	int N, sum = 1;
	string S;

	cin >> N >> S;

	char c = S[0];

	REPA(i, 1, N){
		if(c != S[i]){
			sum++;
		}
		c = S[i];
	}

	cout << sum << endl;

	return 0;
}

頭から順に調べていき、直前に調べた文字と違う文字が出てきたら総数を+1する。O(N)。

D - Triangles

問題
ACできなかった…悔しい

解けなかった.cpp

int main(void) {

	int N, a, b, c, sum = 0;
	vector<int> l(2001);

	cin >> N;

	vector<int> len(N);

	REP(i, N) {
		cin >> len[i];
		l[len[i]]++;
	}

	sort(ALL(len));

	REP(i, N){
		a = len[i];
		REPA(j, i + 1, N){
			b = len[j];
			int temp_sum = sum;
			for(int k = a + b - 1; k >= b ; k--){
				sum += l[k];
			}
			if(temp_sum != sum) sum -= l[a];
			j += b;
		}
	}

	cout << sum << endl;
	return 0;
}

Nが2 * 10^3だったせいか工夫しなければならないという強迫観念に囚われすぎたかもしれない。

最も小さい2本を先に決めておけば残り一本に使える棒の長さが決まるので、
入力を昇順に並び替える→小さい順に1本目を決める→次に小さい棒から一番長い棒の長さ-1本目の棒の長さまでを2本目として選ぶ→1本目＋2本目の長さより小さく、2本目の長さ以上の棒の長さを数える→1本目の棒が一番大きな棒を選ぶまで繰り返す
こんな感じで解けるはずだったが、3本目の棒を数えやすいようにバケットソートしていたら全部同じ長さの棒のときを失念していて、書きづらいコードになり最終的にうまくコードに起こせず時間切れ。。。

初めてレートが下がりました。精進します。

補足

載せているコードにREPとか出てくるけどC++にそんなものはなく、自作の競プロ用テンプレートを載せてなかったので一応

my_template

# include <iostream>
# include <cstdio>
# include <string>
# include <vector>
# include <algorithm>
# include <cmath>
# include <map>

# define INF 2e9

# define REP(i,n) for(int i = 0; i < n;++i)
# define REPA(i,a,n) for(int i = a; i < n; ++i)
# define ALL(a) a.begin(), a.end()

using namespace std;