ABC319

대회를 3개나 쳐서 정신이 나간 모습이다.

E를 무려 7분만에 풀었지만 C를 60분만에 풀어버리면서(...) 망했다.

 

A (0:00 ~ 2:35)

노가다 문제

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
pair<string,string> s[] ={
    {"tourist", "3858"},
    {"ksun48", "3679"},
    {"Benq", "3658"},
    {"Um_nik", "3648"},
    {"apiad", "3638"},
    {"Stonefeang", "3630"},
    {"ecnerwala", "3613"},
    {"mnbvmar", "3555"},
    {"newbiedmy", "3516"},
    {"semiexp", "3481"}
};
int main(){
    fast;
    ll n,m,k;
    vector<ll> v,e;
    string t;
    cin>>t;
    for(int i = 0 ; i < 100 ; i++){
        if(t==s[i].first)return cout<<s[i].second,0;
    }
}

B (2:35 ~ 5:31)

시키는대로 합시다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
int main(){
    fast;
    cin>>n;
    for(int i = 0 ; i <= n ; i++){
        bool f=0;
        for(int j = 1 ; j <= 9 ; j++){
            if(n%j==0){
                if(i%(n/j)==0){
                    cout<<j;
                    f=1;
                    break;
                }
            }
        }
        if(!f)cout<<"-";
    }
}

 

C (5:31 ~ 66:07)

오늘 망한 이유. 분명 개인 컴퓨터에서는 5초만에 돌던데 내보니까 200ms가 나왔다. 이게 말이 되나?

저것만 아니었으면 빨리 제출하고 D, E를 봐서 빨리 풀었을 것이다.

문제 자체는 브루트포스이다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll a[4][4];
ll chk[4][4];
bool safe(ll x, ll y){
    if(x<0 or y<0 or x>2 or y>2)return 0;
    return 1;
}
ll dx[] = {1,0,1,-1}, dy[] = {0,1,1,1};
ll cnt;
ll R = 362880;
vector<vector<pair<ll,ll>>> ww;
int main(){
    fast;
    ww.push_back({{0,0},{0,1},{0,2}});
    ww.push_back({{1,0},{1,1},{1,2}});
    ww.push_back({{2,0},{2,1},{2,2}});
    ww.push_back({{0,0},{1,0},{2,0}});
    ww.push_back({{0,1},{1,1},{2,1}});
    ww.push_back({{0,2},{1,2},{2,2}});
    ww.push_back({{0,0},{1,1},{2,2}});
    ww.push_back({{0,2},{1,1},{2,0}});
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++)cin>>a[i][j];
    }
    vector<ll> v(9);
    iota(all(v),0);
    do{
        bool F=0;
        for(int i = 0 ; i < 9 ; i++){
            ll x = v[i]/3, y = v[i]%3;
            chk[x][y]=i;
        }
        for(auto A : ww){
            vector<pair<ll,ll>> V=A;
            sort(all(V));
            bool f=0;
            do{
                if(a[V[0].first][V[0].second]==a[V[1].first][V[1].second] and a[V[1].first][V[1].second] != a[V[2].first][V[2].second] and max(chk[V[0].first][V[0].second],chk[V[1].first][V[1].second]) < chk[V[2].first][V[2].second])f=1;
            }while(next_permutation(all(V)));
            if(f){
                F=1;
                goto xx;
            }
        }
        xx:;
        if(F)cnt++;
    }while(next_permutation(all(v)));
    cnt = R-cnt;
    cout.precision(11);
    cout<<fixed<<1.0*cnt/R;
}

 

D (3?:?? ~ 48:09)

C가 안풀려서 D를 잡았다. 풀이에 따라 약간 귀찮을 수 있는 파라메트릭 서치인데, 처음에 좀 더럽게 내서 2틀했다.

W의 값에 따라 possible/impossible이 단조성을 지니므로 O(N)에 W<=x를 판단해주면 O(NlogX)에 풀 수 있다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, m;
ll l[202020];
bool chk(ll x){
    ll cnt = 0;
    ll ret=1;
    for(int i = 0 ; i < n ; i++){
        if(i!=0)cnt++;
        if(cnt>x)ret++,cnt=0;
        if(cnt+l[i]>x){
            ret++;
            cnt=0;
            if(l[i]>x)return 0;
        }
        cnt += l[i];
    }
    return ret<=m;
}
int main(){
    fast;
    cin>>n>>m;
    for(int i = 0 ; i < n ; i++){
        cin>>l[i];
    }
    ll L = -1, R = 1e18;
    while(L+1<R){
        ll mid = L+R>>1;
        if(chk(mid))R = mid;
        else L = mid;
    }
    cout<<R;
}

 

E (66:07 ~ 73:59)

E를 이렇게 빨리 푼건 처음인 것 같다.

보면 p[i] <= 8이라는 무시무시한 조건이 있다. 생각해보면 시간에 따라 버스들이 도착하는 시간이 주기성을 띄게 될 것이고, 그 주기는 최대 lcm(1,2,3,4,5,6,7,8) = 840이므로 T%840의 값이 같은 T는 버스들이 움직이는 형태가 다 같다는 것을 알 수 있다. 따라서 0~839초를 싹다 전처리해준다음 바로바로 출력해줄 수 있다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll solve[844];
ll n,X,Y;
ll p[101010], t[101010];
ll get(ll x){
    ll ret = X+Y;
    x += X;
    for(int i = 0 ; i < n-1 ; i++){
        while(x%p[i]!=0)x++, ret++;
        x += t[i], ret += t[i];
    }
    return ret;
}
int main(){
    fast;
    cin>>n>>X>>Y;
    for(int i = 0 ; i < n-1 ; i++)cin>>p[i]>>t[i];
    for(int i = 0 ; i <= 840 ; i++)solve[i] = get(i);
    ll q; cin>>q;
    while(q--){
        ll a; cin>>a;
        cout<<a+solve[a%840]<<"\n";
    }
}

 

---

upsolving

G (73:59 ~ 100:00)

E 풀고 시간이 없어서 대충 봤는데, 완전그래프에서 삭제된 m개의 간선을 제외하면 구간으로 표현할 수 있을 것 같아서 세그먼트 트리로 간선을 줄이는 테크닉(https://www.acmicpc.net/problem/18193)을 이용해서 비비고 있었으나 끝났다. 정해는 dp같다.