티스토리 뷰

이번 Codeforces 라운드는 그래도 A~E까지 5개의 문제를 해결했다.

하지만, 여전히 한 문제를 말려서 못푸는건 마찬가지인 것 같다.

F번에 대해 $O(Q\sqrt{N} + 2^6 Q)$ 정도의 풀이를 생각했지만, 포함배제 구현 미스로 대회가 끝났고, 너무 복잡하게 생각해서 케이스를 많이 나누었던게 화근인(화끈이 아님) 것 같다.

해결한 문제에 대한 풀이를 간단히 작성하였다.

대회 문제는 다음 링크에서 풀어볼 수 있다. 링크: https://codeforces.com/contest/1207

A. There Are Two Types Of Burgers

비프 패티 버거를 최대 $p$개, 치킨 패티 버거를 최대 $f$개 만들 수 있다. $pf$개의 모든 경우에 대해 따져보면서, 실제로 만들 수 있는지(번이 모자라지 않은지) 확인해주면 답을 구할 수 있다.

시간 복잡도는 총 $O(pf)$이다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--){
    int b, p, f;
        cin >> b >> p >> f;
        int h, c;
        cin >> h >> c;
        int ans = 0;
        for (int i=0; i<=p; i++){
            for (int j=0; j<=f; j++){
                if (2*(i+j) <= b)
                    ans = max(ans, h*i+c*j);
            }
        }
        cout << ans << endl;
    }
}

B. Square Filling

A의 $2 \times 2$ 부분 격자들을 전부 살펴보며 이들이 전부 검은색이라면 B도 검은색으로 칠해주면 된다.

마지막에 B와 A가 같은지 체크해주면 된다.

시간복잡도는 총 $O(N^2M^2)$ 이다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
typedef pair<int, int> pi;
 
int N, M;
 
vector<pi> ans;
 
int A[55][55], B[55][55];
 
bool eq(){
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            if (A[i][j] != B[i][j]) return false;
        }
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            cin >> A[i][j];
        }
    }
    for (int i=1; i<N; i++){
        for (int j=1; j<M; j++){
            if (A[i][j] && A[i+1][j] && A[i][j+1] && A[i+1][j+1]){
                ans.push_back({i, j});
            }
        }
    }
    for (auto p : ans){
        int i = p.first, j = p.second;
        B[i][j] = 1;
        B[i+1][j] = 1;
        B[i][j+1] = 1;
        B[i+1][j+1] = 1;
    }
    if (eq()){
        cout << ans.size() << '\n';
        for (auto p : ans){
            cout << p.first << ' ' << p.second << '\n';
        }
    }
    else{
        cout << -1 << endl;
    }
}

C. Gas Pipeline

일단, 모든 수가 0인 경우는 쉬우므로 논외로 하자.

그러면 0으로 이루어진 구간과 1로 이루어진 구간이 반복되며, 양 끝은 0으로 이루어진 구간인 상황이 된다.

그러면, 맨 양끝 구간을 제한 나머지 구간을 먼저 높이를 2로 하여 채우자.

그리고 각각의 1로 이루어진 구간에 대해 높이를 1로 낮추는게 이득인지 살펴보면 된다.

시간 복잡도는 총 $O(N)$이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
typedef pair<int, int> pi;
 
int T;
 
int N;
lld A, B;
string S;
vector<pi> L;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--){
        lld ans = 0;
        L.clear();
        cin >> N >> A >> B;
        cin >> S;
        int st = 0, cur = 0;
        int maxidx = -1, minidx = 200005;
        for (int i=1; i<N; i++){
            if (S[i] == '1'){
                maxidx = max(maxidx, i);
                minidx = min(minidx, i);
            }
            if (S[i] - '0' != cur){
                if (cur == 0) L.push_back({st, i-1});
                st = i;
                cur = 1 - cur;
            }
        }
        L.push_back({st, N-1});
        if (maxidx == -1){
            ans = (N+1)*1LL*B + N*(1LL)*A;
            cout << ans << '\n';
            continue;
        }
        ans = (N+1)*1LL*B + (N+2)*(1LL)*A + (maxidx-minidx+2)*1LL*B;
        for (pi p : L){
            int st = p.first, ed = p.second;
            if (st == 0 || ed == N-1) continue;
            ans += min(0LL, 2*1LL*A - (ed - st)*1LL*B);
        }
        cout << ans << '\n';
    }
}

D. Number Of Permutations

$N!$에서 $a_i$들이 단조 증가하게 되는 순열의 수와 $b_i$들이 단조 증가하게 되는 순열의 수를 빼준 뒤, $a_i$와 $b_i$ 모두가 단조 증가하게 되는 순열의 수를 다시 더해주면 된다.

$N!$을 mod 998244353으로 미리 전처리해놓으면 편하고, 효율적이다.

시간복잡도는 $O(N \log N + N \log MOD)$이다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
const lld mod = 998244353;
 
typedef pair<int, int> pi;
 
int N;
pi A[300005];
lld fac[300005];
int cnt1[300005], cnt2[300005];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i].first >> A[i].second;
    fac[0] = 1;
    for (int i=1; i<=N; i++){
        fac[i] = fac[i-1] * 1LL * i;
        fac[i] %= mod;
    }
    lld c1 = 1, c2 = 1, c3 = 1;
    for (int i=0; i<N; i++) cnt1[A[i].first]++;
    for (int i=1; i<=N; i++){
        c1 = c1 * fac[cnt1[i]];
        c1 %= mod;
    }
    for (int i=0; i<N; i++) cnt2[A[i].second]++;
    for (int i=1; i<=N; i++){
        c2 = c2 * fac[cnt2[i]];
        c2 %= mod;
    }
    sort(A, A+N);
    int st = 0; pi cur = A[0];
    for (int i=1; i<N; i++){
        if (cur != A[i]){
            c3 *= fac[i-st];
            c3 %= mod;
            st = i; cur = A[i];
        }
    }
    c3 *= fac[N-st];
    c3 %= mod;
    for (int i=1; i<N; i++){
        if (A[i-1].second <= A[i].second) continue;
        c3 = 0;
        break;
    }
    lld ans = fac[N];
    ans += mod - c1;
    ans %= mod;
    ans += mod - c2;
    ans %= mod;
    ans += c3;
    ans %= mod;
    cout << ans << endl;
}

E. XOR Guessing

총 14개의 비트를 결정하면 되는데, 이를 7개씩 두 번 나누어 질의하여 결정하면 된다.

0을 두 번 질의하지 않도록 주의해야 한다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int A[150], B[150];
 
bool chk1(int x){
    for (int i=0; i<7; i++)
        if (x & (1 << i)) return false;
    return true;
}
 
bool chk2(int x){
    for (int i=7; i<14; i++)
        if (x & (1 << i)) return false;
    return true;
}
 
int main(){
    int idx1 = 0, idx2 = 0;
    for (int i=1; i<16384; i++){
        if (chk1(i)) A[idx1++] = i;
        if (chk2(i)) B[idx2++] = i;
    }
    cout << '?' << ' ';
    for (int i=0; i<100; i++) cout << A[i] << ' ';
    cout << '\n';
    cout.flush();
    int a; cin >> a;
    cout << '?' << ' ';
    for (int i=0; i<100; i++) cout << B[i] << ' ';
    cout << '\n';
    cout.flush();
    int b; cin >> b;
    int ans = 0;
    for (int i=0; i<7; i++){
        if (a & (1 << i)) ans += (1 << i);
    }
    for (int j=7; j<14; j++){
        if (b & (1 << j)) ans += (1 << j);
    }
    cout << '!' << ' ' << ans << '\n';
    cout.flush();
}

 

 

// P.S. PS 잘하고 싶다...

'정보과학 > Codeforces' 카테고리의 다른 글

Educational Codeforces Round 71  (1) 2019.08.23
Codeforces Round #580  (1) 2019.08.19
Codeforces Round #578  (0) 2019.08.12
Codeforces Round #492  (0) 2019.08.06
Codeforces Round #576  (0) 2019.08.04
Codeforces Round 526 (Div 2) 후기  (0) 2018.12.11
댓글
댓글쓰기 폼
공지사항
Total
20,231
Today
24
Yesterday
25