search

dev-writeup-2024 / march

개발 1일 1글 스터디
2 stars 0 forks source link

[03-15] Educational Codeforces Round 144 Editorial #33

Open Longseabear opened 3 months ago

Longseabear commented 3 months ago

Educational Codeforces Round 144 Editorial

기한 2023-02-28
solving 3/6
abstract image
등수 936등
소회 D번 문제를 풀지 못한 것이 통한

A. Typical Interview Problem Problem - A - Codeforces

 [Problem - A - Codeforces

codeforces.com](https://codeforces.com/contest/1796/problem/A)

#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();
    }
}

B. Asterisk-Minor Template Problem - B - Codeforces

 [Problem - B - Codeforces

codeforces.com](https://codeforces.com/contest/1796/problem/B)

구성적 알고리즘을 통해 풀었다.

1) 만약 2개의 연속된 문자가 a, b 문자열에서 공통으로 존재하고, 그 길이가 2인 스트링을 s라고 한다면 정답은 *s*가 된다.

2) 만약 2개의 연속된 문자가 없다면, 하나씩 잡아봤자 어쩌피 *는 잡은 문자의 수 +1개 필요하다. 그래서 왠만해선 불가

3) 잡은 문자가 외곽에 있는 경우, *가 필요하지 않기 때문에 이 경우에만 가능.

깔끔하게 풀었다.

#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();
    }
}

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 해줘야 된다.

#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일 때만 고려해서 다 처리하면 된다, 와우

steammando commented 3 months ago

제목.

Kjm04175 commented 3 months ago

답글.

Longseabear commented 3 months ago

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ