NYPC 예선 후기

세줄요약

1. 머리나쁘고

2. 게을러서

3. 조짐

 이번 NYPC 예선은 내가 공부를 엄청 게을리 하고 있다는 증거를 잔뜩 남겨두고 떠났다. 전체적으로 맞는 풀이인데 구현을 못하거나/반례가 있는 줄 알고 해결하지 못한 문제들이 너무 많았다. 해결하지 못한 문제는 16번 쉴드 생성기, 19번 종이접기, 21번 금 줄 게임, 22번 보라색 영역이다.

 점수를 계산해보면 2,135점으로 본선 가기는 그른듯.

 다음은 내가 해결한 문제들에 대한 간단한 해설과 소스코드이다.

3. 아이템 구매

간단한 일차방정식을 해결하는 문제이다. Naive하게 코딩할 경우 시간복잡도는 선형으로 나온다. 확장 유클리드 알고리즘을 이용해서 로그 시간복잡도로 해결할 수 있을 것 같다는 느낌이 들긴 하는데 그렇게 코딩할 이유는 없으니까 ^^7

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int p,q,w;
    scanf("%d %d %d",&p,&q,&w);
    for(int i=0;;i++)
    {
        int left=w-p*i;
        if(left<0) return -1;
        if(left%q==0)
        {
            printf("%d %d",i,left/q);
            return 0;
        }
    }
    return -1;
}
 

4. 승리팀 찾기

문제에서 요구하는 대로 그대로 코딩해주면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef tuple<int,int,int> tp;
typedef pair<tp,int> player;
const int score[]={10,8,6,5,4,3,2,1};
 
bool tenSec(tp a, tp b)
{
    int ta=get<0>(b)-get<0>(a);
    int tb=get<1>(b)-get<1>(a);
    int tc=get<2>(b)-get<2>(a);
    if(tc<0) tb--;
    if(tb<0) tb+=60,ta--;
 
    if(ta>0) return false;
    if(tb>=10) return false;
    return true;
}
 
void solve()
{
    char sel[10];
 
    scanf("%s",sel);
 
    vector<player> V;
    for(int i=0;i<8;i++)
    {
        char team[10];
        int m,s,ms;
        scanf(" %s %d:%d.%d",team,&m,&s,&ms);
        V.push_back(make_pair(tie(m,s,ms),strcmp("red",team)!=0));
    }
 
    sort(V.begin(),V.end());
 
    if(strcmp("speed",sel)==0)
    {
        int sc[2]={};
        for(int i=0;i<8;i++)
            if(tenSec(V[0].first,V[i].first))
                sc[V[i].second]+=score[i];
        if(sc[0]==sc[1])
            printf("%s\n",V[0].second==0?"red":"blue");
        else
            printf("%s\n",sc[0]>sc[1]?"red":"blue");
    }
    else
    {
        printf("%s\n",V[0].second==0?"red":"blue");
    }
}
 
int main()
{
    int tc;
    scanf("%d",&tc);
    while(tc--) solve();
    return 0;
}
 

5. 줄임말

단어에서 맨 앞글자만 따 주는 프로그램을 만드는 것인데, UTF-8 인코딩은 문자열 한글 처리가 굉장히 번거롭다. 유일한 아웃풋 only 문제라는 것을 잘 이용해서 그냥 상용 프로그램으로 유니코드로 바꿔준 다음(그럼 한글이 항상 2바이트) 그대로 코딩하면 된다. 제발 이런문제좀 안나왔으면 좋겠다. 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n;
    freopen("input_test.txt","r",stdin);
    freopen("output_test.txt","w",stdout);
    scanf("%d\n",&n);
    char str[3000];
    while(n--)
    {
        bool pr=true;
        fgets(str,sizeof(str),stdin);
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
            if(str[i]==' ')
            {
                pr=true;
                continue;
            }
            if(!pr) continue;
            if(('A'<=str[i] && str[i]<='Z') || ('a'<=str[i] && str[i]<='z'))
                printf("%c",str[i]);
            else
            {
                printf("%c%c",str[i],str[i+1]);
                i++;
            }
 
            pr=false;
        }
        printf("\n");
    }
    return 0;
}
 

6. 우물왕 김배찌

x좌표와 y좌표의 분산을 각각 최소화하는 문제이다. 분산을 최소화하는 값은 모든 값의 평균이라는 사실이 매우 잘 알려져 있다. 끝!

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main()
{
    int n;
    ll xs=0, ys=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        ll t1,t2;
        scanf("%lld %lld",&t1,&t2);
        xs+=t1;
        ys+=t2;
    }
    printf("%f %f",(double)xs/(double)n,(double)ys/(double)n);
    return 0;
}
 

7. 최고의 동접 구간을 찾아라!

사람들이 접속할 수 있는 시간이 최대 1440분밖에 안된다는 것을 이용해서 Prefix Sum 비슷하게 해결하면 된다. 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    vector<int> v(1440);
    vector<int> pn(1440);
 
    int n,ma=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int t1,t2;
        scanf("%d:%d",&t1,&t2);
        v[t1*60+t2]++;
        scanf("%d:%d",&t1,&t2);
        v[t1*60+t2]--;
    }
    partial_sum(v.begin(),v.end(),pn.begin());
    int bf=-1,st,en,mst,men;
    for(int i=0;i<1440;i++)
    {
        if(bf!=pn[i])
        {
            en=i-1;
            if(ma<bf)
            {
                ma=bf;
                mst=st;
                men=en;
            }
            st=i;
        }
        bf=pn[i];
    }
 
    men++;
    printf("%d\n%02d:%02d %02d:%02d",ma,mst/60,mst%60,men/60,men%60);
    return 0;
}
 

8. 버튼 게임

유클리드 알고리즘을 그대로 번형시킨 문제이다. a!=0이어야 한다는 사실에 주의하자.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    if(__gcd(a,b)==1 && a!=0) printf("POSSIBLE");
    else printf("IMPOSSIBLE");
    return 0;
}
 

9. 이진 트리

$DP(n,k)$를 $n$개의 노드로 높이가 $k$ 이하인 만들 수 있는 이진 트리 개수라고 정하자. 그러면 왼쪽 서브트리와 오른쪽 서브트리의 높이를 달리 하며 계산해줄 수 있다. 시간복잡도는 $O(nk^2)$. 답은 당연히 $DP(n,k)-DP(n,k-1)$이 된다. 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const ll MOD=1e9+7;
 
ll cache[505][505];
ll n,k;
 
ll dp(ll re, ll h)
{
    if(h<0) return 0;
    if(re==0) return 1;
    ll& ret=cache[re][h];
    if(ret!=-1) return ret;
 
    ll s=0;
    for(ll i=0;i<=re-1;i++)
        s=(s+(dp(i,h-1)*dp(re-i-1,h-1))%MOD)%MOD;
    return ret=s;
}
 
int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%lld %lld",&n,&k);
    ll ans=dp(n,k)-dp(n,k-1);
    if(ans<0) ans+=MOD;
    printf("%lld",ans);
    return 0;
}
 

10. 캐릭터 경험치

역추적을 해야 하는 냅색이다. 더 이상의 설명이 필요한지?

#include <bits/stdc++.h>
 
using namespace std;
 
int s,n;
int cache[1005][10005];
int cost[1005];
int expt[1005];
 
int dp(int idx, int stm)
{
    if(idx==n) return 0;
    int& ret=cache[idx][stm];
    if(ret!=-1) return ret;
 
    if(stm-cost[idx]<0) return ret=dp(idx+1,stm);
    else return ret=max(dp(idx+1,stm),dp(idx+1,stm-cost[idx])+expt[idx]);
}
 
vector<int> ans;
void track(int idx, int stm)
{
    if(idx==n) return;
    if(dp(idx+1,stm-cost[idx])+expt[idx]==dp(idx,stm) && stm-cost[idx]>=0)
    {
        ans.push_back(idx);
        track(idx+1,stm-cost[idx]);
    }
    else
        track(idx+1,stm);
}
 
int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&s,&n);
    for(int i=0;i<n;i++)
        scanf("%d %d",&cost[i],&expt[i]);
    printf("%d\n",dp(0,s));
    track(0,s);
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
        printf("%d ",ans[i]+1);
    return 0;
}
 

11. 전염병 역학 조사

시간의 범위가 $10^6$으로 비교적 짧으니 매 시간마다 간선을 추가하고 지우는 것을 반복하면서 BFS를 돌려주면 된다. 감염되는 사람만을 큐에 넣으면 모든 인간은 단 한번 큐에 들어가므로 시간복잡도는 $O(10^6+V+E)$ 인것 같다. 아마도?

#include <bits/stdc++.h>
 
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
vector<vector<pii> > meet(1000005,vector<pii>());
vi virus;
vector<vi> adj;
 
void add_edge(queue<int> &Q, int ti)
{
    for(int i=0;i<meet[ti].size();i++)
    {
        pii here=meet[ti][i];
        adj[here.first].push_back(here.second);
        adj[here.second].push_back(here.first);
        if(virus[here.first] && !virus[here.second])
        {
            virus[here.second]=1;
            Q.push(here.second);
        }
        if(virus[here.second] && !virus[here.first])
        {
            virus[here.first]=1;
            Q.push(here.first);
        }
    }
}
 
void erase_edge(int ti)
{
    for(int i=0;i<meet[ti].size();i++)
    {
        pii here=meet[ti][i];
        adj[here.first].pop_back();
        adj[here.second].pop_back();
    }
}
 
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    adj.assign(n+1,vi());
    virus.assign(n+1,0);
    for(int i=0;i<m;i++)
    {
        int t1,t2,tt;
        scanf("%d %d %d",&t1,&t2,&tt);
        meet[tt].push_back(make_pair(t1,t2));
    }
    virus[1]=1;
    for(int i=1;i<=1e6;i++)
    {
        if(meet[i].size()==0) continue;
        queue<int> Q;
        add_edge(Q,i);
        while(!Q.empty())
        {
            int here=Q.front(); Q.pop();
            for(int j=0;j<adj[here].size();j++)
            {
                int there=adj[here][j];
                if(virus[there]) continue;
                virus[there]=1;
                Q.push(there);
            }
        }
        erase_edge(i);
    }
    for(int i=1;i<=n;i++)
        if(virus[i]) printf("%d ",i);
    return 0;
}
 

12. 강력한 한방, 필살기

강한필 조교님 사랑합니다

#include <bits/stdc++.h>
 
using namespace std;
 
typedef struct square
{
    char checker;
    int atk, def;
 
    void init_square(char _checker, int _atk, int _def)
    {
        checker=_checker;
        atk=_atk;
        def=_def;
    }
}Square;
 
Square board[5][5];
Square temp[5][5];
Square remain[15];
 
int cal_score()
{
    int s=0;
    for(int i=1;i<=4;i++)
    {
        bool check=true;
        for(int j=1;j<=3;j++)
            if(temp[i][j].checker!='M')
                check=false;
        if(check)
        {
            for(int j=1;j<=3;j++)
                s+=temp[i][j].atk;
        }
    }
 
    for(int j=1;j<=3;j++)
    {
        bool check=true;
        for(int i=1;i<=3;i++)
            if(temp[i][j].checker!='M')
                check=false;
        if(check)
        {
            for(int i=1;i<=3;i++)
                s+=temp[i][j].atk;
        }
        check=true;
        for(int i=2;i<=4;i++)
            if(temp[i][j].checker!='M')
                check=false;
        if(check)
        {
            for(int i=2;i<=4;i++)
                s+=temp[i][j].atk;
        }
    }
 
    for(int i=0;i<=1;i++)
    {
        bool check=true;
        for(int j=1;j<=3;j++)
        {
            if(temp[i+j][j].checker!='M')
                check=false;
        }
        if(check)
        {
            for(int j=1;j<=3;j++)
                s+=temp[i+j][j].atk;
        }
    }
 
    for(int i=0;i<=1;i++)
    {
        bool check=true;
        for(int j=1;j<=3;j++)
        {
            if(temp[i+j][4-j].checker!='M')
                check=false;
        }
        if(check)
        {
            for(int j=1;j<=3;j++)
                s+=temp[i+j][4-j].atk;
        }
    }
 
    return s;
}
 
bool canMove(Square a, Square b)
{
    if(b.checker=='X') return true;
    if(b.checker=='M') return false;
    return (a.atk>b.def) && (a.def>b.atk);
}
 
int main()
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=3;j++)
        {
            char sel;
            int t1=0,t2=0;
            scanf(" %c",&sel);
            if(sel!='X')
                scanf("%d/%d",&t1,&t2);
            board[i][j].init_square(sel,t1,t2);
            temp[i][j].init_square(sel,t1,t2);
        }
    }
 
 
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        char sel;
        int t1=0,t2=0;
        scanf(" %c",&sel);
        if(sel!='X')
            scanf("%d/%d",&t1,&t2);
        remain[i].init_square(sel,t1,t2);
    }
    int ma=0;
    for(int x=1;x<=4;x++)
    {
        for(int y=1;y<=3;y++)
        {
            if(board[x][y].checker=='O') continue;
            if(board[x][y].checker=='X')
            {
                for(int i=0;i<n;i++)
                {
                    temp[x][y]=remain[i];
                    ma=max(ma,cal_score());
                    temp[x][y]=board[x][y];
                }
            }
            if(board[x][y].checker=='M')
            {
                for(int i=-1;i<=1;i++)
                {
                    for(int j=-1;j<=1;j++)
                    {
                        int nx=x+i;
                        int ny=y+j;
                        if(nx<1 || nx>4) continue;
                        if(ny<1 || ny>3) continue;
 
                        if(!canMove(board[x][y],board[nx][ny]) && !(x==nx && y==ny)) continue;
                        temp[x][y].init_square('X',0,0);
                        temp[nx][ny]=board[x][y];
                        ma=max(ma,cal_score());
                        temp[x][y]=board[x][y];
                        temp[nx][ny]=board[nx][ny];
                    }
                }
            }
        }
    }
    printf("%d",ma);
    return 0;
}
 

13. 회전 격자판

버블 정렬 비슷한걸 돌아가는 격자판에서 하는 문제다. 이유는 잘 모르겠는데 한번 정렬이 되면 4번 주기로 변하지 않는 상태가 되는것 같았다. 그래서 냈더니 맞았다. 덕분에 코드가 개판

#include <bits/stdc++.h>
 
using namespace std;
typedef vector<int> vi;
 
int n,k;
vector<vi> arr;
 
void print()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",arr[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
void modify()
{
    vector<vi> a=arr;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n-1;j++)
            if(a[i][j] > a[i][j+1])
                swap(a[i][j],a[i][j+1]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            arr[i][j]=a[j][n-i+1];
}
 
int main()
{
    scanf("%d %d",&n,&k);
    arr.assign(n+1,vi(n+1));
 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&arr[i][j]);
 
    //freopen("output.txt","w",stdout);
 
    //print();
    for(int i=1;i<=310;i++)
    {
        //printf("%d\n",i);
        modify();
        if(k<304 && i==k)
        {
            print();
            return 0;
        }
        if(k%4==i%4 && i>=304)
        {
            print();
            return 0;
        }
    }
    return 0;
}
 

14. 블록 숫자

BFS를 돌려주면 된다. 어떤 숫자가 결정되었을 때 새롭게 결정될 수 있는 숫자의 위치는 몇가지 되지 않는다. 모든 숫자는 최대 한번 결정되므로 시간복잡도는 $O(N^2)$.

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
int n;
int arr[1005][1005];
 
int da[]={1,1,-1,0,-1,0};
int db[]={0,1,-1,-1,0,1};
 
int mod(int x)
{
    if(x>=0) return x%100;
    else return (x%100)+100;
}
 
bool update(int a, int b)
{
    if(a<1 || a>n) return false;
    if(b<1 || b>a) return false;
 
    if(arr[a][b]!=-1) return false;
    if(arr[a][b-1]!=-1 && arr[a-1][b-1]!=-1)
    {
        if(a!=1 && b!=1)
        {
            arr[a][b]=mod(arr[a-1][b-1]-arr[a][b-1]);
            return true;
        }
    }
    if(arr[a][b+1]!=-1 && arr[a-1][b]!=-1)
    {
        if((b+1)<=a && a!=1)
        {
            arr[a][b]=mod(arr[a-1][b]-arr[a][b+1]);
            return true;
        }
    }
    if(arr[a+1][b]!=-1 && arr[a+1][b+1]!=-1)
    {
        if((a+1)<=n)
        {
            arr[a][b]=mod(arr[a+1][b]+arr[a+1][b+1]);
            return true;
        }
    }
    return false;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&arr[i][j]);
 
    queue<pii> Q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(update(i,j))
                Q.push(make_pair(i,j));
    while(!Q.empty())
    {
        pii here=Q.front(); Q.pop();
        for(int i=0;i<6;i++)
            if(update(here.first+da[i],here.second+db[i]))
                Q.push(make_pair(here.first+da[i],here.second+db[i]));
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            printf("%d%c",arr[i][j]," \n"[i==j]);
    return 0;
}
 

15. Flood-It

결국은 맨 마지막의 상태만 확인해 주면 되므로 그냥 다익스트라를 돌리면 된다. 가중치를 내가 지금 수행한 쿼리의 번호로부터 지금 내가 앞으로 이동할 위치에 있는 숫자의 가장 빠른 쿼리 번호가 뭔지 생각해주면서 설정하면 된다. 코드를 보자.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
 
const int INF=100000;
 
int arr[1005][1005];
int query[1005];
int idx[1005][10];
int dist[1005][1005];
 
int n,k;
 
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
 
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;i++)
        scanf("%d",&query[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&arr[i][j]);
    query[0]=arr[1][1];
 
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++)
            dist[i][j]=INF;
 
    memset(idx,-1,sizeof(idx));
    for(int i=0;i<=k;i++)
    {
        idx[i][query[i]]=i;
        for(int j=i-1;j>=0;j--)
        {
            if(query[j]==query[i]) break;
            idx[j][query[i]]=i;
        }
    }
 
    priority_queue<piii,vector<piii>,greater<piii> > Q;
    Q.push(make_pair(0,make_pair(1,1)));
    dist[1][1]=0;
    while(!Q.empty())
    {
        piii temp=Q.top(); Q.pop();
        int hidx=temp.first;
        int x=temp.second.first;
        int y=temp.second.second;
 
        if(hidx>dist[x][y]) continue;
 
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n) continue;
            if(ny<1 || ny>n) continue;
 
            int tidx=idx[hidx][arr[nx][ny]];
            if(tidx==-1) continue;
            if(tidx>=dist[nx][ny]) continue;
            Q.push(make_pair(tidx,make_pair(nx,ny)));
            dist[nx][ny]=tidx;
        }
    }
    int s=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(dist[i][j]!=INF)
                s++;
    printf("%d",s);
    return 0;
}
 

16. 실드 생성기

미리 전처리를 해 놓으면 $O(N^3)$에 된다는 듯 하다. 추후에 풀이 이해하고 다시 올리겠음.

17. 퍼즐 콤보

문자열을 (문자, 문자 개수) 형태로 나타낸 리스트로 바꾼 다음 잘 지워주면 된다. 리스트에서 원소를 삭제할 때 순서를 잘 지켜줘야 한다. 근데 이것보다 더 쉽게 코딩하는 방법이 분명 있을듯

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<char,int> block;
typedef list<block>::iterator b_it;
 
int n;
char str[1000005];
 
int main()
{
    scanf("%d",&n);
    scanf("%s",str);
 
    list<block> L;
    vector<b_it> V;
 
    L.push_back(make_pair('@',0));
    char bf=str[0]; int sz=1;
    for(int i=1;i<=n;i++)
    {
        if(i<n && bf==str[i])
            sz++;
        else
        {
            L.push_back(make_pair(bf,sz));
            auto lb=L.end(); lb--;
            if(sz>=3) V.push_back(lb);
            sz=1;
        }
        bf=str[i];
    }
    L.push_back(make_pair('@',0));
 
    int combo=0;
    while(true)
    {
        if(V.empty()) break;
        vector<b_it> temp;
        vector<b_it> nextBlock;
 
        for(int i=0;i<V.size();i++)
        {
            b_it here=V[i];
            b_it l_here=V[i]; l_here--;
            L.erase(here);
            if(!temp.empty() && temp.back()==l_here) continue;
            temp.push_back(l_here);
        }
 
        for(int i=0;i<temp.size();i++)
        {
            b_it left=temp[i];
            b_it right=temp[i]; right++;
 
            if(left->first=='@' || right->first=='@')
                continue;
 
            if(left->first==right->first)
            {
                assert(right->second<3);
                if(left->second<3 && left->second+right->second>=3)
                    nextBlock.push_back(right);
                else if(left->second>=3)
                {
                    nextBlock.pop_back();
                    nextBlock.push_back(right);
                }
                right->second+=left->second;
                L.erase(left);
            }
        }
        V=nextBlock;
        combo++;
    }
 
    printf("%d\n",combo);
    if(L.size()==2)
        printf("PERFECT!!!");
    else
    {
        for(b_it it=L.begin();it!=L.end();it++)
            for(int j=0;j<it->second;j++)
                printf("%c",it->first);
    }
    return 0;
}
 

18. 피파 온라인 드리블 튜토리얼

공은 사실 언제든지 찰 수 있으니 그냥 장애물이랑 만났을 때 뚫고 지나가면서 공으로 장애물을 부순다고 생각해도 상관이 없다. 단 오른쪽이나 왼쪽으로 이동하면서 부수진 못한다. 그러면 간단하게 동적계획법으로 해결할 수 있다. 그러면 $O(NM)$이 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF=100000;
 
int n,m,k;
char arr[505][55];
int cache[505][55];
 
int dp(int a,int b)
{
    if(b<1 || b>m) return INF;
    if(a==k) return 0;
 
    int &ret=cache[a][b];
    if(ret!=-1) return ret;
 
    int mi=INF;
    for(int i=-1;i<=1;i++)
    {
        int temp=dp(a-1,b+i)+(arr[a-1][b+i]=='#'?1:0);
        if(i!=0 && arr[a][b+i]=='#') continue;
        mi=min(mi,temp);
    }
 
    return ret=mi;
}
 
int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf(" %c",&arr[i][j]);
 
    printf("%d",dp(n,1));
    return 0;
}
 

19. 종이접기

풀기 싫어서 안풀었다. 풀걸

20. 봇 탐지

아무래도 내가 푼 풀이가 정해가 아닌 것 같다. 단순히 해싱을 하면 시간이 모자라고, 길이에 대해서 map을 따로 선언해 주면 $N=2950$정도까지는 뚫을 수 있다. 여기서 최적화하려고 hash_map도 써보고 롤링 해시 곱하는 수도 바꿔보고 17 곱하는거 비트쉬프트로 최적화 한다고 뻘짓하고 반복문 변수 밖으로 빼고 맵 순회하는것도 그때그때 저장하는걸로 바꾸고 변수 접근시간도 줄이고 별별짓을 다했는데 그냥 메모리가 터지기 직전까지 map을 추가로 선언해 주고 해싱을 한번 더 해주면 바로 됐다. 가장 고생한 문제고, 정해를 진짜 알고싶다. 댓글로 제발 달아주세요

#include <bits/stdc++.h>
#include <hash_map>
 
using namespace std;
using namespace __gnu_cxx;
typedef pair<int,int> pii;
 
char str[3005];
int arr[3005];
int t[300];
hash_map<int,pii> M[1505][50];
 
int main()
{
    t['L']=1; t['R']=2; t['U']=3; t['D']=4;
 
    int n;
    int a,b;
    int i,j;
 
    scanf("%d %d %d",&n,&a,&b);
    scanf(" %s",str);
 
    for(i=0;i<n;i++)
        arr[i+1]=t[str[i]];
 
    int ma=0,tp,hv;
    for(i=1;i<=n;i++)
    {
        hv=0;
        for(j=i;j<=n;j++)
        {
            if((j-i+1)>=(n/2+1)) break;
            hv=((hv<<4)+hv+arr[j]);
            pii& p=M[j-i+1][abs(hv)%47][hv];
            if(p.first==0 || (p.first+j-i)<i)
            {
                p.first=i;
                tp=++p.second;
                if(tp>=2 && ma<(j-i+1)*tp) ma=(j-i+1)*tp;
            }
        }
    }
 
    if(ma>b) printf("1");
    else if(a<=ma && ma<=b) printf("2");
    else if(ma<a) printf("3");
    return 0;
}
 

21. 금줄 게임

민컷인줄 알고 바로 손절했는데 처음 생각한 그리디 풀이가 맞았다는 이야기를 들었다. 빠른 자살

22. 보라색 영역

화성 지도에 포배하면 되겠지 하고 바로 시도했는데 코딩이 안돼서 실패했다. 이건 그냥 연습 부족... ㅠㅠ

총평)

 전체적으로 4~5회차에 시간이 부족하고 체력이 딸려서 시도를 많이 못해본게 아쉽다. 다음에 NYPC에 또 참가하게 되면 조금 더 열심히 해볼것 같음. 사실 NYPC를 하면서 원샷 엔딩을 봤다는 것부터가 그냥 열심히 안했다는 것을 증명하고 있다. 문제를 푸는 법을 알아도 실제로 문제를 많이 풀어보지 않아도 코딩에서 막히거나 안될거라고 생각하고 지레짐작해서 틀리는 경우가 4문제중 3문제였다. (실드 빼고) 본선은 못갈거같긴 한데, 티셔츠정도는 기대해도 좋을거라고 행복회로를 빡세게 돌리고 있다. 다음엔 진짜 진짜 열심히 해야지.