알고리즘 블로그
article thumbnail
Published 2022. 11. 27. 13:02
제 2회 곰곰컵 후기 PS 기록들

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

어제 제 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

문제 링크

풀고 싶지 않다...

저작자표시 비영리 동일조건

'PS 기록들' 카테고리의 다른 글

Codeforces Round #848 (Div. 2)  (0) 2023.02.02
Codeforces Round #846 (Div. 2)  (0) 2023.01.26
알고리즘 {먼데이} 챌린지 3주차  (0) 2022.11.02
Codeforces Round #829 (Div.2)  (0) 2022.10.23
AtCoder Regular Contest 151  (1) 2022.10.23
profile

알고리즘 블로그

@도훈.

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

profile on loading

Loading...

검색 태그

동적 계획법
Segment Tree
Codeforces
백준
AtCoder Regular Contest
알고리즘
BOJ
JOISC
DP
NYPC
티스토리챌린지
출제
KTSC
USACO
ABC 272
알고리즘 대회
greedy
elice
트리
국제정보올림피아드 선발고사
2023
오블완
Koi
coci
coder's high
1328
atcoder
IOI
dfs
KSAAC

티스토리툴바