ABC330 参加記(ABCD)

AtCoder Beginner Contest 330に参加しました。

ABCD四完です。椅子はあったまりました。

A - Counting Passes

やるだけ。普通に全探索

abc330_a.cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N, L;
	cin >> N >> L;

	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int A;
		cin >> A;

		if(A >= L)
			ans++;
	}

	cout << ans << endl;

	return 0;
}

B - Minimize Abs 1

複雑そうに見えるけど、$L \leq A_i \leq R$ なら $A_i$ 、 $A_i < L$ なら $L$ 、いずれでもないなら $R$が答え。

abc330_b.cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N, L, R;
	cin >> N >> L >> R;

	vector<int> X(N);
	for (int i = 0; i < N; ++i)
	{
		int A;
		cin >> A;

		if(L <= A && R >= A){
			X[i] = A;
		}else if(A<L){
			X[i] = L;
		}else{
			X[i] = R;
		}
	}

	for(int i = 0; i < N; ++i){
		cout << X[i] << (i != N - 1 ? " " : "\n");
	}

	return 0;
}

C - Minimize Abs 2

まず $x$ は $x^2 \leq D$ の範囲で全探索して、 $y$ は $\sqrt {D - x^2}$ の切り捨てと切り上げで最小値を探せばいい。

$\sqrt {D - x^2}$ と $\log_2 {D-x^2}$ 間違えて時間ロスした

ちなみに、uint64_tでやってるから複雑になってるけど、普通にint64_tでいけました

abc330_c.cpp

#include<bits/stdc++.h>
using namespace std;

template<typename T>
void chmin(T &a, T b){
	if(a > b){
		a = b;
	}
}

uint64_t solve(uint64_t a, uint64_t b){
	if(a > b)
		return a - b;
	else
		return b - a;
}

int main(){
	uint64_t D;
	cin >> D;

	uint64_t ans = UINT64_MAX;
	for (uint64_t i = 0; i * i <= D;++i){
		auto tmp = floor(sqrt(D - i * i));

		chmin(ans, solve(D, i * i + tmp * tmp));
		chmin(ans, solve(D, i * i + (tmp + 1) * (tmp + 1)));
	}

	cout << ans << endl;

	return 0;
}

D - Counting Ls

$i$ 列目と $j$ 行目に何個oが含まれているかを管理して、

列の個数を $A_i$ 、行の個数を $B_i$ として、
二重ループで $S_{ij}$ がoなら $(A_i-1) \times (B_i-1)$ を随時答えに足していく

abc330_d.cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N;
	cin >> N;

	vector<string> S(N);
	for(int i = 0; i < N; ++i){
		cin >> S[i];
	}

	vector<int> A(N,0), B(N,0);
	for (int i = 0; i < N; ++i){
		for(int j = 0; j < N; ++j){
			if(S[i][j] == 'o'){
				A[i]++;
				B[j]++;
			}
		}
	}

	int64_t ans = 0;
	for (int i = 0; i < N; ++i)
	{
		for(int j = 0; j < N; ++j){
			if(S[i][j] == 'o'){
				ans += (A[i] - 1) * (B[j] - 1);
			}
		}
	}

	cout << ans << endl;

	return 0;
}