Codeforces Round #689 (Div. 2)

A - String Generation

Problem - A - Codeforces

\(n, k\)가 주어진다.

a, b, c 3개의 문자로만 이루어져 있으면서, 최대 길이인 팰린드롬 부분문자열의 길이가 \(k\)이하인 길이 \(n\)의 문자열을 출력하면 된다.

 

"abc"를 \(n\)길이만큼 출력하면 답이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n, k; cin >> n >> k;
        for (int i = 0; i < n; i++)
            cout << (char)(i % 3 + 'a');
        cout << '\n';
    }
}

---

B - Find the Spruce

Problem - B - Codeforces

\(n \times m\)크기의 격자가 주어진다.

이 격자에서 문제에서 말하는 "spruse tree"의 개수를 구해야 한다.

 

\(n, m\)이 최대 500이므로, \(O(n^3)\)도 충분히 돌아간다는 사실을 알 수 있다.

각 칸에 대해서 좌우로 퍼질 수 있는 최대 길이를 \(O(n^2)\) 또는 \(O(n^3)\)으로 구해 놓으면,

spurse tree의 개수를 \(O(n^3)\)에 쉽게 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
string board[501];
int lsum[501][501];
int rsum[501][501];
int asum[501][501];
 
int mx[501][501];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            cin >> board[i];
 
        for (int i = 0; i < n; i++)
        {
            int cur = 0;
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] == '*') cur++;
                else cur = 0;
                lsum[i][j] = cur;
            }
 
            cur = 0;
            for (int j = m - 1; j >= 0; j--)
            {
                if (board[i][j] == '*') cur++;
                else cur = 0;
                rsum[i][j] = cur;
            }
 
            for (int j = 0; j < m; j++)
            {
                asum[i][j] = min(lsum[i][j], rsum[i][j]);
            }
        }
 
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int ci = i;
                int cur = 1;
                while (ci < n)
                {
                    if (asum[ci][j] < cur) break;
                    ans++;
                    ci++;
                    cur++;
                }
            }
        }
 
        cout << ans << '\n';
    }
}

---

C - Random Events

Problem - C - Codeforces

\(n\) 길이의 순열이 주어진다.

\(m\)번의 쿼리가 주어지는데,

각 쿼리는 \((r, p)\)의 형태로 이루어져 있고, 앞에서부터 \(r\)개의 수가 \(p\)확률로 정렬이 됨을 뜻한다.

 

모든 쿼리를 수행한 뒤에 이 순열이 정렬되어 있을 확률을 구해야 한다.

 

 

가장 마지막으로 정렬 안된 원소가 \(x\)번째 원소라고 하자.

그러면 \(r \ge x\)인 쿼리가 모두 실행되지 않았다면 이 순열은 정렬되지 않고, 한번이라도 실행되었다면 정렬됨을 알 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
int a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
 
        int last = n;
        while (a[last] == last && last > 0) last--;
 
        bool isOne = false;
 
        if (last == 0) isOne = true;
 
        double ans = 0.0;
        for (int i = 0; i < m; i++)
        {
            int r; double p; cin >> r >> p;
            if (r >= last)
            {
                if (p == 1.0)
                {
                    isOne = true;
                    break;
                }
                else
                    ans += log(1.0 - p);
            }
        }
 
        if (isOne)
        {
            cout << "1.000000\n";
            continue;
        }
 
        ans = exp(ans);
        ans = 1.0 - ans;
        cout.precision(6);
        cout << fixed << ans << '\n';
    }
}

---

D - Divide and Summarize

Problem - D - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

이 배열의 최소값과 최대값의 평균을 floor한 값을 \(mid\)라고 했을 때,

원래 배열을 \(mid\)보다 작거나 같은 원소만으로 이루어진 배열과 \(mid\)보다 큰 원소만으로 이루어진 배열로 나눌 수 있다.

 

\(q\)번의 쿼리가 주어지는데, 각 쿼리마다 \(s\)가 주어지면 위의 연산으로 만든 어떤 배열의 원소의 합이 \(s\)가 될 수 있는지 여부를 출력하면 된다.

 

단순히 완전탐색으로 가능한 모든 배열의 상태를 만들어 보면 된다.

한번 연산 할 때마다 배열에 들어있을 수 있는 수의 범위가 반으로 나눠지므로,

원 배열의 수의 범위를 \(k\)라고 했을 때 많아도 \(O(n\log k)\)개의 배열만이 생길 수 있기 때문이다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, q;
map <ll, ll> mp;
vector <pll> vec;
vector <ll> psum;
 
set <ll> res;
 
void solve(int l, int r)
{
    if (l > r) return;
 
    ll csum = psum[r] - (l == 0 ? 0 : psum[l - 1]);
    res.insert(csum);
 
    if (l == r) return;
 
    ll mid = (vec[l].first + vec[r].first) / 2;
    int idx = lower_bound(vec.begin(), vec.end(), pll(mid + 1, 0)) - vec.begin();
 
    solve(l, idx - 1);
    solve(idx, r);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        mp.clear();
        res.clear();
        psum.clear();
 
        cin >> n >> q;
        for (int i = 0; i < n; i++)
        {
            ll a; cin >> a;
            mp[a]++;
        }
 
        vec = vector<pll>(mp.begin(), mp.end());
        for (int i = 0; i < vec.size(); i++)
        {
            ll res = vec[i].first * vec[i].second + (psum.empty() ? 0 : psum.back());
            psum.push_back(res);
        }
 
        solve(0, vec.size() - 1);
 
        for (int i = 0; i < q; i++)
        {
            ll s; cin >> s;
            if (res.find(s) != res.end()) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

---

E - Water Level

Problem - E - Codeforces

정수기에 현재 \(k\)리터의 물이 있다.

매일 아침에 정수기에 물을 \(y\)리터를 넣거나 넣지 않을 수 있고, 하루동안 \(x\)리터의 물이 소비된다.

이 정수기에 있는 물을 항상 \(l\)리터 이상, \(r\)리터 이하로 \(t\)일간 유지시키는 것이 가능한지 알아내야 한다.

 

일단 문제의 간략화를 위해 \(k\)에서 \(l\)을 빼고, 물을 0리터 이상 \(r-l\)이하로 유지시키는 것으로 생각하자.

 

먼저, \(x > y\)라면, 물을 다 쓰는데 며칠이 걸리는지 \(O(1)\)에 알아낼 수 있다.

그렇지 않다면, 직접 시뮬레이션 해보자.

만약 매일 아침 \(y\)리터의 물을 넣어도 물이 \(r-l\)리터를 넘어가지 않는다면, 무조건 붓는것이 이득임을 알 수 있다.

물을 붓거나 붓지 않은 후, 다음으로 물을 넣을 수 있을 때까지 며칠이 지나야 하는지 \(O(1)\)에 알 수 있다.

 

각각의 "아침에 물을 부을 수 있는 날"에, 물을 부은 직후 물의 양 \(w\)에 대해서 생각해보자.

하루에 소비 될 수 있는 양 (\(x)\)가 많아도 \(10^6\)이므로, \(w\)가 될 수 있는 경우의 수도 그와 같음을 알 수 있다.

 

따라서 \(w\)의 값을 계속 저장해 나가다가, 이전에 나왔던 \(w\)의 값이 또 등장한다면 이 작업을 무한히 할 수 있음을 알 수 있다.

그렇지 않다면, 물을 조건에 맞게 유지시킬 수 있는 최대 시간을 구할 수 있으므로, \(t\)와 비교하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    ll k, l, r, t, x, y;
    cin >> k >> l >> r >> t >> x >> y;
    r -= l;
    k -= l;
 
    if (x > y)
    {
        if (k + y <= r) k += y;
        ll res = (k - x) / (x - y) + 1;
 
        if (res >= t) cout << "Yes";
        else cout << "No";
 
        return 0;
    }
 
    bool hasAns = false;
    set <ll> st;
 
    ll ct = 0;
    while (ct < t)
    {
        if (st.find(k) != st.end())
        {
            hasAns = true;
            break;
        }
 
        st.insert(k);
 
        if (k + y <= r) k += y;
 
        ll canUse = k / x; // times
        ll toPour = (k - (r - y)) / x;
        if ((k - (r - y)) % x) toPour++; // times
        toPour = max(toPour, 1ll);
 
        if (toPour <= canUse)
        {
            ct += toPour;
            k -= toPour * x;
        }
        else
        {
            ct += canUse;
            k -= canUse * x;
            break;
        }
    }
 
    if (ct >= t) hasAns = true;
 
    if (hasAns) cout << "Yes";
    else cout << "No";
}

---

F - Mathematical Expression

Problem - F - Codeforces

추가 예정