Educational Codeforces Round 144 Editorial
| 기한 |
2023-02-28 |
| solving |
3/6 |
| abstract |
 |
| 등수 |
936등 |
| 소회 |
D번 문제를 풀지 못한 것이 통한 |
[Problem - A - Codeforces
codeforces.com](https://codeforces.com/contest/1796/problem/A)
- 3과 5의 최소 공배수인 15부터 정답이 반복된다. 총 8개의 문자
- k의 최대값이 10이기 때문에 10개의 슬라이딩 윈도우 했을 때 모든 경우의 수가 나올 수 있도록 사전에 string을 세팅하면 된다. (8개 문자 3번 반복)
- 멍청하게 2번만 반복했다가(16문자), 두번 틀리고 분노의 4번 반복으로 통과하였다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>
#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;
const int MAX_N = 101010;
int A[MAX_N];
void solve() {
int k;
cin >> k;
string pattern = "FBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFB";
string s;
cin >> s;
int left = 0;
int right = s.size();
bool success;
while (right <= pattern.size()) {
success = true;
for (int i = left; i < right; i++) {
if (pattern[i] != s[i - left]) success = false;
}
if (success) {
cout << "YES\n";
return;
}
right++, left++;
}
cout << "NO\n";
return;
}
int main() {
fastio;
int testCase = 1;
cin >> testCase;
for (int i = 1; i <= testCase; i++) {
solve();
}
}
[Problem - B - Codeforces
codeforces.com](https://codeforces.com/contest/1796/problem/B)
구성적 알고리즘을 통해 풀었다.
-
만약 2개의 연속된 문자가 a, b 문자열에서 공통으로 존재하고, 그 길이가 2인 스트링을 s라고 한다면 정답은 *s*가 된다.
-
만약 2개의 연속된 문자가 없다면, 하나씩 잡아봤자 어쩌피 *는 잡은 문자의 수 +1개 필요하다. 그래서 왠만해선 불가
-
잡은 문자가 외곽에 있는 경우, *가 필요하지 않기 때문에 이 경우에만 가능.
깔끔하게 풀었다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>
#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;
const int MAX_N = 101010;
int A[MAX_N];
void solve() {
string a,b;
cin >> a >> b;
for (int i = 0; i < a.size()-1; i++) {
for (int j = 0; j < b.size()-1; j++) {
if (a[i] == b[j] && a[i + 1] == b[j + 1]) {
cout << "YES\n";
cout << "*" << a[i] << a[i+1] << "*\n";
return;
}
}
}
if (a[0] == b[0]) {
cout << "YES\n" << a[0] << "*\n";
}
else if (a.back() == b.back()) {
cout << "YES\n*" << a.back() <<"\n";
}
else {
cout << "NO\n";
}
return;
}
int main() {
fastio;
int testCase = 1;
cin >> testCase;
for (int i = 1; i <= testCase; i++) {
solve();
}
}
[Problem - C - Codeforces
codeforces.com](https://codeforces.com/contest/1799/problem/C)
갑작스러운 문제 유형에 당황; 보다보니 빽트래킹으로 가능할 것 같아서 빽트래킹으로 풀었다. 다른 사람들도 나랑 똑같이 당황했나보다. 이 문제를 빨리 풀어서 등수 방어가 그나마 가능했다.
풀이
어떤 set에서 두 개를 잡았을 때 둘 중 하나가 나머지 하나로 나누어 떨어져야 한다. 다음과 같은 경우에만 위 조건이 만족한다.
{ a1, a1 * a2, a1 * a2 * a3, a1 * a2 * a3 * a4 }
즉, set 데이터를 정렬했을 때, 이전 값에 어떤 값을 곱하는 식으로 set이 구성되어야 한다. 어떤 값을 잡아도 모든 값을 포함하고 있기 때문에 무조건 나누어 떨어진다.
그럼 위 주장이 필요충분조건인가? 다음과 같은 경우를 상상해 봤다.
{a1, a1 * a2, a1 * k * a3} (오름차순으로 정렬되어있음)
3번째 데이터에 a2가 아닌 어떤 k가 곱해졌다고 생각해보자. 이 경우 2번째 요소와 나누어 떨어지려면 k가 a2의 어떤 약수를 가지고 있어야 한다. 만약 k * a3이 a2보다 작다면, 오름차순 기준에 위배되므로 k*a3은 a2보다 크다. k가 a2의 약수의 일부만 가지고 있다면 2번과 3번 요소가 나누어 떨어지지 않는다. 나누어 떨어지는 경우는 k가 a2의 모든 약수를 가지고 있을 때(i.g., k=a2일 때) 밖에 없다.
그렇다면, 문제에서 요구하는 가장 긴 set의 크기는? 가장 작은 값으로 증가하면 된다. 아래처럼
{L, L*2, L*2*2...., L * 2^i} where L = left 값, L*2^i <= r
시작지점 부터 가장 작은 값 만큼 증가시켰기 때문에 이 set 보다 큰 set은 존재하지 않는다.
이제 위에서 얻은 set과 같은 크기의 set이 L과 R 사이에 몇개 존재하는지 세면된다. L에서 시작했을 때 됐으면, L+1일때도 되지 않을까?
{(L+1), (L+1)*2, (L+1)*2*2....}
일반화하면,
{(L+j), (L+j)*2, (L+j)*2*2...}
어느 순간 (L+j) * 2^i 이 r을 넘어갈 것이다. 그럼 다음 방정식에서 j를 구하면 된다.
(L+j) * 2^i <= r
L로 시작해서 최대 2^i 곱했을 때 나올 수 있는 경우의 수는 (r / (2^i)) - L + 1개가 된다.
위에서는 가장 작은 경우를 찾기 위해 2로만 곱했는데, 사실 2,3,4.... 다 곱할 수 있다.
이를 빽트래킹으로 문제 해결
다만, branch and bound 할 때 처럼 미리 미래의 하한을 먼저 계산해서 불가능한 경우 return 해줘야 된다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>
#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
const ll MOD = 998244353ll;
const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;
const int MAX_N = 101010;
int A[MAX_N];
ll l, r;
int maximumNum;
ll backtracking(int step, ll curval) {
if (step == maximumNum) {
return (r / curval) - l + 1;
}
int t = maximumNum - step;
ll answer = 0ll;
for (ll i = 2;; i++) {
ll tempval = (curval * i * l) << (t - 1);
if (tempval > r) return answer;
if (curval * i * l > r) return answer;
answer = (answer + backtracking(step + 1, curval * i)) % MOD;
}
return answer;
}
void solve() {
cin >> l >> r;
maximumNum = 0;
ll temp = l;
while (temp <= r) {
maximumNum++;
temp *= 2;
}
cout << maximumNum << " " << backtracking(1, 1) << "\n";
return;
}
int main() {
fastio;
int testCase = 1;
cin >> testCase;
for (int i = 1; i <= testCase; i++) {
solve();
}
}
Upsolving
소름; 4씩 증가하는 경우는 볼 필요가 없었다. 4는 결국 2 두개로 쪼개질 수 있으니까, 더 큰 set을 만들어 낼 것이다..
즉 다음과 같은 경우는 존재할 수 없다.
{ L, L*4 }
왜냐면 아래와 같이 쪼개질 수 있으니까
{ L, L*2, L*2*2 } (크기가 더 작다!)
3씩 증가하는 경우는 2개 이상인 경우에 불가능
{L, L*3, L*3*3 } 일 경우,
{L, L*2, L*2*2, L*2*2*2} 인 경우가 존재할 거니까(9보다 8이 작으니까!)
결국 첫번째 값이 3일 때만 고려해서 다 처리하면 된다, 와우
Educational Codeforces Round 144 Editorial
A. Typical Interview Problem Problem - A - Codeforces
[Problem - A - Codeforces
codeforces.com](https://codeforces.com/contest/1796/problem/A)
B. Asterisk-Minor Template Problem - B - Codeforces
[Problem - B - Codeforces
codeforces.com](https://codeforces.com/contest/1796/problem/B)
구성적 알고리즘을 통해 풀었다.
만약 2개의 연속된 문자가 a, b 문자열에서 공통으로 존재하고, 그 길이가 2인 스트링을 s라고 한다면 정답은 *s*가 된다.
만약 2개의 연속된 문자가 없다면, 하나씩 잡아봤자 어쩌피 *는 잡은 문자의 수 +1개 필요하다. 그래서 왠만해선 불가
잡은 문자가 외곽에 있는 경우, *가 필요하지 않기 때문에 이 경우에만 가능.
깔끔하게 풀었다.
C. Maximum Set Problem - C - Codeforces
[Problem - C - Codeforces
codeforces.com](https://codeforces.com/contest/1799/problem/C)
갑작스러운 문제 유형에 당황; 보다보니 빽트래킹으로 가능할 것 같아서 빽트래킹으로 풀었다. 다른 사람들도 나랑 똑같이 당황했나보다. 이 문제를 빨리 풀어서 등수 방어가 그나마 가능했다.
풀이
어떤 set에서 두 개를 잡았을 때 둘 중 하나가 나머지 하나로 나누어 떨어져야 한다. 다음과 같은 경우에만 위 조건이 만족한다.
{ a1, a1 * a2, a1 * a2 * a3, a1 * a2 * a3 * a4 }
즉, set 데이터를 정렬했을 때, 이전 값에 어떤 값을 곱하는 식으로 set이 구성되어야 한다. 어떤 값을 잡아도 모든 값을 포함하고 있기 때문에 무조건 나누어 떨어진다.
그럼 위 주장이 필요충분조건인가? 다음과 같은 경우를 상상해 봤다.
{a1, a1 * a2, a1 * k * a3} (오름차순으로 정렬되어있음)
3번째 데이터에 a2가 아닌 어떤 k가 곱해졌다고 생각해보자. 이 경우 2번째 요소와 나누어 떨어지려면 k가 a2의 어떤 약수를 가지고 있어야 한다. 만약 k * a3이 a2보다 작다면, 오름차순 기준에 위배되므로 k*a3은 a2보다 크다. k가 a2의 약수의 일부만 가지고 있다면 2번과 3번 요소가 나누어 떨어지지 않는다. 나누어 떨어지는 경우는 k가 a2의 모든 약수를 가지고 있을 때(i.g., k=a2일 때) 밖에 없다.
그렇다면, 문제에서 요구하는 가장 긴 set의 크기는? 가장 작은 값으로 증가하면 된다. 아래처럼
{L, L*2, L*2*2...., L * 2^i} where L = left 값, L*2^i <= r
시작지점 부터 가장 작은 값 만큼 증가시켰기 때문에 이 set 보다 큰 set은 존재하지 않는다.
이제 위에서 얻은 set과 같은 크기의 set이 L과 R 사이에 몇개 존재하는지 세면된다. L에서 시작했을 때 됐으면, L+1일때도 되지 않을까?
{(L+1), (L+1)*2, (L+1)*2*2....}
일반화하면,
{(L+j), (L+j)*2, (L+j)*2*2...}
어느 순간 (L+j) * 2^i 이 r을 넘어갈 것이다. 그럼 다음 방정식에서 j를 구하면 된다.
(L+j) * 2^i <= r
L로 시작해서 최대 2^i 곱했을 때 나올 수 있는 경우의 수는 (r / (2^i)) - L + 1개가 된다.
위에서는 가장 작은 경우를 찾기 위해 2로만 곱했는데, 사실 2,3,4.... 다 곱할 수 있다.
이를 빽트래킹으로 문제 해결
다만, branch and bound 할 때 처럼 미리 미래의 하한을 먼저 계산해서 불가능한 경우 return 해줘야 된다.
Upsolving
소름; 4씩 증가하는 경우는 볼 필요가 없었다. 4는 결국 2 두개로 쪼개질 수 있으니까, 더 큰 set을 만들어 낼 것이다..
즉 다음과 같은 경우는 존재할 수 없다.
{ L, L*4 }
왜냐면 아래와 같이 쪼개질 수 있으니까
{ L, L*2, L*2*2 } (크기가 더 작다!)
3씩 증가하는 경우는 2개 이상인 경우에 불가능
{L, L*3, L*3*3 } 일 경우,
{L, L*2, L*2*2, L*2*2*2} 인 경우가 존재할 거니까(9보다 8이 작으니까!)
결국 첫번째 값이 3일 때만 고려해서 다 처리하면 된다, 와우