제 2회 곰곰컵 후기

질문은 언제나 환영입니다.

어제 제 2회 곰곰컵에 참가했다.

 

치킨댄스를 추는 곰곰이를 본 임스 2

문제 링크

매번 D-?에서 ?만 따내서 90 이하인지 판단하여 총 개수를 구하면 된다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define siz(x) int((x).size())

int main() {
    int n, c = 0; cin >> n;
    rep(i,1,n) {
        string s; cin >> s;
        s = s.substr(2,siz(s)-2);
        if (stoi(s) <= 90) c++;
    }
    cout << c;
}

붙임성 좋은 총총이

문제 링크

춤이 전이된 친구들을 std::set에 관리하면서 풀면 된다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define siz(x) int((x).size())

set<string> st;

int main() {
    int n; cin >> n;
    st.insert("ChongChong");
    rep(i,1,n) {
        string s, t;
        cin >> s >> t;
        if (st.count(s) or st.count(t)) {
            st.insert(s), st.insert(t);
        }
    }
    cout << siz(st);
}

곰곰이와 학식

문제 링크

일단 직접 낼 수 있을 만큼 내본다.

그 다음에는 3장으로 거쳐서 낼 수 있을 만큼 내본다.

마지막으로 9장으로 거쳐서 낼 수 있을 만큼 내본다.

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

ll ans;

int main() {
    int a, b, c, x, y, z, t;
    cin >> a >> b >> c >> x >> y >> z;
    
    t = min(a,x);
    a -= t, x -= t;
    ans += t;
    t = min(b,y);
    b -= t, y -= t;
    ans += t;
    t = min(c,z);
    c -= t, z -= t;
    ans += t;
    
    t = min(a,z/3);
    a -= t, z -= t*3;
    ans += t;
    t = min(b,x/3);
    b -= t, x -= t*3;
    ans += t;
    t = min(c,y/3);
    c -= t, y -= t*3;
    ans += t;
    
    t = min(a,y/9);
    a -= t, y -= t*9;
    ans += t;
    t = min(b,z/9);
    b -= t, z -= t*9;
    ans += t;
    t = min(c,x/9);
    c -= t, x -= t*9;
    ans += t;
    
    cout << ans;
}

오락실에 간 총총이

문제 링크

딱 1명 있는 경우에는 0번만에 가능하다.

하나의 행 또는 하나의 열 위에 모두 모여 있는 경우에는 한 방향으로만 밀면 된다.

둘 다 아닌 대부분의 경우는 두 방향으로 밀어서 꼭짓점으로 옮기는 네 가지 경우를 고려해주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define Mup(x,y) x = max(x,y)

const int N = 1503;
int n, cnt;
int a[N][N];
int x, y, z, w;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i,1,n) rep(j,1,n) {
        char c; cin >> c;
        if (c == 'G') {
            a[i][j] = 1, cnt++;
            Mup(x, i-1);
            Mup(y, n-i);
            Mup(z, j-1);
            Mup(w, n-j);
        }
    }
    if (cnt == 1) {
        cout << 0;
        return 0;
    }
    rep(i,1,n) {
        int d = 0;
        rep(j,1,n) d += a[i][j];
        if (cnt == d) {
            cout << min(z,w);
            return 0;
        }
    }
    rep(j,1,n) {
        int d = 0;
        rep(i,1,n) d += a[i][j];
        if (cnt == d) {
            cout << min(x,y);
            return 0;
        }
    }
    cout << min({x+z,x+w,y+z,y+w});
}

곰곰이와 시소

문제 링크

문제에 주어진 식을 그대로 이진 탐색에 적용해서 풀면 된다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 1e5+3;
int n, l;
int x[N], w[N];

double torque(double X) {
    double s = 0;
    rep(i,1,n) {
        s += w[i] * (X-x[i]);
    }
    return s;
}

int main() {
    cin >> n >> l;
    rep(i,1,n) cin >> x[i];
    rep(i,1,n) cin >> w[i];
    
    double a = 0, b = l;
    while (b-a > 1e-7) {
        double m = (a+b)/2;
        if (torque(m) > 0) b = m;
        else a = m;
    }
    cout << setprecision(10) << fixed << a;
}

외로운 곰곰이는 친구가 있어요

문제 링크

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 1e5+3;
int n;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i,1,n) {
        int x, y;
        cin >> x >> y;
        int k, g = 0;
        cin >> k;
        rep(j,1,k) {
            int a; cin >> a;
            g = gcd(g,a);
        }
        if (x%g == 0 and y%g == 0) {
            cout << "Ta-da\n";
        } else cout << "Gave up\n";
    }
}

곰곰이와 테트리스

문제 링크

재밌는 문제다.

Mirroring 전략을 이용하여 풀면 1×2, 2×1 빼고는 전부 이길 수 있다는 걸 알 수 있다.

a, b = map(int,input().split())
if a == 1 and b == 2:
    print("ChongChong")
elif a == 2 and b == 1:
    print("ChongChong")
else:
    print("GomGom")

곰곰아 선 넘지마

문제 링크

그리디하게 exchange argument로 생각하면 순서에 맞게 0끼리 이어서 거리의 총합을 내는게 맞다는 결론이 나온다.

이걸 산술 기하 평균 부등식에 따라 최대한 절반으로 만들어 답을 구하면 된다.

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    int a = 0, b = 0, c = 0;
    ll d = 0;
    while (c < n) {
        while (s[a] != '0') a++;
        while (t[b] != '0') b++;
        d += abs(a-b), a++, b++, c++;
    }
    cout << (d/2)*(d/2)+(d-d/2)*(d-d/2);
}

곰곰이의 식단 관리 2

문제 링크

최대 2이다.

0인 경우는 단순히 flood fill을 진행하면 된다.

1인 경우는 dfs로 열심히 구현하면 된다.... 화이팅

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 2003, M = 2003;
int n, m, dp[N][M], c;
bool a[N][M], v[N][M], v1[N][M], v2[N][M];

const ii d4[] {{0,1},{1,0},{0,-1},{-1,0}};
const ii d8[] {{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
bool out(int x, int y) {return 1 > x or x > n or 1 > y or y > m;}

void dfs(int x, int y) {
    if (out(x,y)) return;
    if (v[x][y] or !a[x][y]) {
        v[x][y] = a[x][y] = 1;
        return;
    }
    v[x][y] = true;
    for (auto [i,j] : d8) {
        dfs(x+i,y+j);
    }
}

void dfs1(int x, int y) {
    if (out(x,y)) return;
    if (v1[x][y] or a[x][y]) return;
    v1[x][y] = true;
    for (auto [i,j] : d4) {
        dfs1(x+i,y+j);
    }
}

void dfs2(int x, int y) {
    if (out(x,y)) return;
    if (v2[x][y] or !a[x][y]) return;
    v2[x][y] = true;
    for (auto [i,j] : d8) {
        dfs2(x+i,y+j);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    rep(i,1,n) rep(j,1,m) {
        cin >> a[i][j];
        if (a[i][j]) c++;
    }
    if (n == 1 or m == 1) {
        if (c > 0) cout << 0;
        else cout << 1;
        return 0;
    }
    dfs1(1,1);
    if (!v1[n][m]) {
        cout << 0;
        return 0;
    }
    rep(j,2,m) dfs(1,j);
    rep(i,2,n-1) dfs(i,m);
    dfs2(1,2);
    rep(i,2,n) if (v2[i][1]) {
        cout << 1;
        return 0;
    }
    rep(j,1,m-1) if (v2[n][j]) {
        cout << 1;
        return 0;
    }
    cout << 2;
}

서커스 나이트

문제 링크

"약수의 관점보다, 수를 고정하고 그 배수를 둘러보는 관점이 더 효율적이다"라는 아이디어를 사용하면 된다.

sieve와 비슷한 꼴로 둘러보면서 DSU를 이용하여 잘 처리하면 된다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define Mup(x,y) x = max(x,y)

template <const int N>
struct disjoint_set {
    int p[N], s[N];
    disjoint_set() { clear(); }
    void clear() {
        iota(p,p+N,0);
        fill(s,s+N,1);
    }
    int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }
    void merge(int a, int b) {
        a = find(a), b = find(b);
        if (s[a] > s[b]) swap(a,b);
        s[b] += s[a], p[a] = b;
    }
    int size(int x) {
        return s[find(x)];
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

const int N = 1e6+3;
int n;
int idx[N];
disjoint_set<N> ds;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i,1,n) {
        int a; cin >> a;
        if (idx[a]) ds.merge(idx[a],i);
        else idx[a] = i;
    }
    rep(i,2,1'000'000) {
        int x = 0;
        bool first = idx[i] == 0;
        if (idx[i]) x = idx[i];
        for (int j = i; j <= 1'000'000; j += i) if (idx[j]) {
            if (first) {
                x = idx[j];
                first = false;
            } else {
                if (not ds.same(x,idx[j]))
                    ds.merge(x,idx[j]);
            }
        }
    }
    int ans = 0;
    rep(i,1,n) {
        Mup(ans,ds.size(i));
    }
    cout << ans;
}

곰곰이와 토너먼트

문제 링크

기댓값의 선형성을 생각해서 높이별로 기댓값을 나눠 구한 뒤 더하자.

각 기댓값은 조합을 이용하여 쉽게 구할 수 있다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

#pragma region modnum template from ecnerwala/cp-book
// https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp
template <typename T> T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}
template <typename T> T mod_inv(T a, T m) {
    a %= m;
    a = a < 0 ? a + m : a;
    return mod_inv_in_range(a, m);
}
template <int MOD_> struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");

private:
    int v;

public:

    modnum() : v(0) {}
    modnum(int64_t v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
    friend std::istream& operator >> (std::istream& in, modnum& n) { int64_t v_; in >> v_; n = modnum(v_); return in; }

    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }
    friend modnum inv(const modnum& m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD-v : 0;
        return res;
    }
    friend modnum neg(const modnum& m) { return m.neg(); }

    modnum operator- () const {
        return neg();
    }
    modnum operator+ () const {
        return modnum(*this);
    }

    modnum& operator ++ () {
        v ++;
        if (v == MOD) v = 0;
        return *this;
    }
    modnum& operator -- () {
        if (v == 0) v = MOD;
        v --;
        return *this;
    }
    modnum& operator += (const modnum& o) {
        v -= MOD-o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator -= (const modnum& o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator *= (const modnum& o) {
        v = int(int64_t(v) * int64_t(o.v) % MOD);
        return *this;
    }
    modnum& operator /= (const modnum& o) {
        return *this *= o.inv();
    }

    friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
    friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
#pragma endregion modnum template
using mint = modnum<998244353>;
const int N = ( 1<<18)+3, K = 20;
int k, n, a[N], c;
mint r[K];

const int F = N;
mint fac[F+1] {1}, caf[F+1];
void precalc() {
    int i = 1;
    for (; i <= F; ++i) fac[i] = fac[i-1]*i;
    caf[F] = inv(fac[F]);
    for (i = F; i; --i) caf[i-1] = i*caf[i];
}
mint C(int n, int k) {
    if (k < 0 or n < k) return 0;
    return fac[n]*caf[k]*caf[n-k];
}

int main() {
    precalc();
    cin.tie(0)->sync_with_stdio(0);
    cin >> k;
    n = 1<<k;
    rep(i,1,n) {
        cin >> a[i];
        if (a[i] < a[1]) c++;
    }
    rep(i,1,k) cin >> r[i];
    mint ans = 0;
    rep(i,1,k) if ((1<<i)-1 <= c) {
        ans += C(c,(1<<i)-1) / C(n-1,(1<<i)-1) * r[i];
    }
    cout << ans;
}

곰곰이의 벼락치기

문제 링크

고등학교 때 배우는 "같은 것이 있는 순열"을 트리 DP에 잘 적용해주면 된다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

#pragma region modnum template from ecnerwala/cp-book
// https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp
template <typename T> T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}
template <typename T> T mod_inv(T a, T m) {
    a %= m;
    a = a < 0 ? a + m : a;
    return mod_inv_in_range(a, m);
}
template <int MOD_> struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");

private:
    int v;

public:

    modnum() : v(0) {}
    modnum(int64_t v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
    friend std::istream& operator >> (std::istream& in, modnum& n) { int64_t v_; in >> v_; n = modnum(v_); return in; }

    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }
    friend modnum inv(const modnum& m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD-v : 0;
        return res;
    }
    friend modnum neg(const modnum& m) { return m.neg(); }

    modnum operator- () const {
        return neg();
    }
    modnum operator+ () const {
        return modnum(*this);
    }

    modnum& operator ++ () {
        v ++;
        if (v == MOD) v = 0;
        return *this;
    }
    modnum& operator -- () {
        if (v == 0) v = MOD;
        v --;
        return *this;
    }
    modnum& operator += (const modnum& o) {
        v -= MOD-o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator -= (const modnum& o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator *= (const modnum& o) {
        v = int(int64_t(v) * int64_t(o.v) % MOD);
        return *this;
    }
    modnum& operator /= (const modnum& o) {
        return *this *= o.inv();
    }

    friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
    friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
#pragma endregion modnum template
using mint = modnum<1'000'000'007>;
const int N = 2e5+3;
int n, m, ind[N], sub[N];
vector<int> adj[N];

const int F = N;
mint fac[F+1] {1}, caf[F+1];
void precalc() {
    int i = 1;
    for (; i <= F; ++i) fac[i] = fac[i-1]*i;
    caf[F] = inv(fac[F]);
    for (i = F; i; --i) caf[i-1] = i*caf[i];
}
mint C(int n, int k) {
    if (k < 0 or n < k) return 0;
    return fac[n]*caf[k]*caf[n-k];
}

mint dfs(int s) {
    mint r = 1;
    sub[s] = 1;
    for (auto u : adj[s]) {
        r *= dfs(u), sub[s] += sub[u];
    }
    r *= fac[sub[s]-1];
    for (auto u : adj[s]) {
        r /= fac[sub[u]];
    }
    // cerr << s << ' ' << r << endl;
    return r;
}

int main() {
    precalc();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    rep(_,1,m) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        ind[b]++;
    }
    rep(i,1,n) if (ind[i] == 0) adj[0].push_back(i);
    cout << dfs(0);
}

곰곰이와 하카타

문제 링크

못 풀었다...

곰곰이와 GGANALi

문제 링크

풀고 싶지 않다...