AtCoder ABC 242 풀이

https://atcoder.jp/contests/abc242/tasks

Tasks - AtCoder Beginner Contest 242

 

 

 

A.

간단한 확률문제입니다. 순위가 높은게 값이 작은것임에 유의합니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	double a, b, c, x;
	cin >> a >> b >> c >> x;
	cout << fixed << setprecision(10);

	if (x <= a) {
		cout << 1; 
	}
	else if (x <= b) {
		cout << c / (b - a);	
	}
	else {
		cout << 0;
	}
}

 

 

B.

문자열을 정렬하는 문제입니다. 문자열을 숫자 순번으로 바꾸고 정렬한 뒤에

다시 문자로 바꿔서 출력해주면 됩니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string s; cin >> s;
	vector<int>v;
	for (auto i : s) {
		v.push_back(i - 'a');
	}
	sort(v.begin(), v.end());
	for (auto j : v) {
		cout << char('a' + j);
	}
}

 

 

C.

이웃한 값의 차이가 1이하가 되도록 하는 수열의 개수를 찾는 문제입니다.

dp[i][j]를 i번까지 결정했고 마지막 값이 j인 수열의 개수라고 정의하면, 

(i, j)는 (i-1, j-1), (i-1, j), (i-1, j+1)에서 왔습니다. 인덱스만 잘 고려해주면 쉽게 해결됩니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll dp[1000006][10];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= 9; i++)dp[1][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= 9; j++) {
			dp[i][j] += dp[i - 1][j]; 
			if (j > 1) dp[i][j] += dp[i - 1][j - 1];
			if (j < 9) dp[i][j] += dp[i - 1][j + 1];
			dp[i][j] %= mod;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= 9; i++) {
		ans = (ans + dp[n][i]) % mod;
	}
	cout << ans << '\n';
}

 

 

D.

관찰이 필요한 문제입니다. 우선 S^t의 i번째 알파벳이 A라고 하면, 

이 알파벳은 S^t+1의 2*i번째와 2*i+1번째 알파벳을 만들어줍니다. 

ABC를 012로 치환하여 생각하면 인덱스가 짝수면 +1 차이나는 알파벳이 생성되고

홀수면 +2 차이나는 알파벳이 만들어집니다. 이제 이를 재귀적으로 구해줍시다.

go(depth, idx)를 S^d에서 idx번째 알파벳으로 정의합니다.

(depth, idx)는 (depth-1, idx/2)를 호출합니다. 그리고 idx의 홀짝성에 따라 변화하는 정도를 

계산해둡니다. 마지막에 종료는 depth가 0이거나 idx가 0일 때 base case를 만들어둡니다.

총 O(QlogK) 시간에 문제를 해결할 수 있습니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll q, t, k;
string s;

char alpha(char s, ll v) {
	return char('A' + (s - 'A' + v) % 3);
}

char go(ll depth, ll idx) {
	if (depth == 0) return s[idx];
	if (idx == 0) return alpha(s[0], depth);
	return alpha(go(depth - 1, idx / 2), idx % 2 + 1);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s >> q;
	while (q--) {
		cin >> t >> k; k--;
		cout << go(t, k) << '\n';
	}
}

 

 

E.

길이 n의 팰린드롬을 만드려면 앞부터 n/2개만 만들어주면 됩니다. 

사전순으로 작은것들의 개수는 쉽게 구할 수 있습니다. 

현재 C가 있다면 그 자리에 C미만의 알파벳을 채웠다면 다음칸부턴 26가지를 모두 채울 수 있습니다. 

문자 n/2개를 보면서 이 경우들을 계속 더해주면 됩니다. 이렇게 구하고 나면 마지막으로 

앞의 n/2개를 모두 그 문자들로 채운 경우가 남게 됩니다. 이 한가지는 나머지 n/2개 문자열에 대해

사전순으로 작다면 1을 더해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    ll ans = 0;
    ll p = 1;
    for (int i = (n - 1) / 2; i >= 0; i--) {
        ans += p * (s[i] - 'A') % mod;
        ans %= mod;
        p *= 26; p %= mod;
    }
    auto t = s;
    for (int i = 0; i < n / 2; i++) {
        t[n - i - 1] = s[i];
    }
    ans += (t <= s);
    cout << ans % mod << "\n";
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int tc; cin >> tc;
	while (tc--) {
        solve();
	}
}