Codeforces Good Bye 2015 ABCDE

역시 연말이 되면 아이큐 잔액이 부족해 무한히 붕괴된다.
A New Year and Days
새해 달력을 보고 여러 가지 상황을 분류하여 출력하면 된다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main(){
    int n;
    cin>>n;
    string q;
    string str;
    cin>>q;
    cin>>str;

    if(str=="week"){
        if(n<=4||n==7){
            cout<<52<<endl;
        }else{
            cout<<53<<endl;
        }
    }else{
        if(n<=29){
            cout<<12<<endl;
        }else if(n<=30){
            cout<<11<<endl;
        }else{
            cout<<7<<endl;
        }
    }
    return 0;
}

B New Year and Old Property
조건에 부합되는 수를 비트 연산으로 미리 처리한 후에 계산한다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll tab[5555];

int main(){
    ll a,b;
    cin>>a>>b;
    int k=0;
    for(ll i=2;i<61;i++){
        ll tmp = (1LL<<i) - 1;
        for(int j=0;j<i-1;j++){
            ll m = 1LL<<j;
            ll cur = tmp^m;
            tab[k++]=cur;
        }
    }
    ll ans = 0;
    for(int i=0;i<k;i++){
        if(tab[i]>= a && tab[i]<=b){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

C New Year and Domino
접두사와 왼쪽 상단에서 각 칸까지 몇 가지 방법이 있는지 계산한다.그리고 용척 원리를 이용하여 4개의 직사각형을 계산하고 경계를 주의하여 처리한다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

char mp[555][555];
int cnt1[555][555];
int cnt2[555][555];
int ans[555][555];

int main(){
    int h,w;
    cin>>h>>w;

    for(int i=1;i<=h;i++){
        scanf("%s",mp[i]+1);
    }

    for(int i=2;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(mp[i][j]=='.' && mp[i-1][j]=='.'){
                cnt1[i][j]=cnt1[i-1][j]+1;
            }else{
                cnt1[i][j]=cnt1[i-1][j];
            }
        }
    }

    for(int i=2;i<=w;i++){
        for(int j=1;j<=h;j++){
            if(mp[j][i]=='.' && mp[j][i-1]=='.'){
                cnt2[j][i]=cnt2[j][i-1]+1;
            }else{
                cnt2[j][i]=cnt2[j][i-1];
            }
        }
    }
    ////////
    for(int i=1;i<=h;i++){
        for(int j=2;j<=w;j++){
            cnt1[i][j]+=cnt1[i][j-1];
        }
    }

    for(int i=1;i<=w;i++){
        for(int j=2;j<=h;j++){
            cnt2[j][i]+=cnt2[j-1][i];
        }
    }

    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            ans[i][j] = cnt1[i][j] + cnt2[i][j];
        }
    }

    int q;
    cin>>q;
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int res = ans[x2][y2]-ans[x1-1][y2]-ans[x2][y1-1]+ans[x1-1][y1-1];
        for(int i=x1;i<=x2;i++){
            if(mp[i][y1]=='.'&&mp[i][y1-1]=='.')res--;
        }
        for(int i=y1;i<=y2;i++){
            if(mp[x1][i]=='.'&&mp[x1-1][i]=='.')res--;
        }
        printf("%d
",res);
    }

    return 0;
}

D New Year and Ancient Prophecy
dp.dp(i, j)는 i번째 문자를 고찰하고 마지막 단락의 길이가 j인 방안 수를 나타낸다.dp(i, j)는 분명히 dp(i-j, k)에서 옮겨온 것이다. k는 몇 개의 값을 얻을 수 있기 때문에 중복 계산을 피하기 위해 최적화해야 한다.또한 뒷수의 수요는 앞의 수보다 엄격하게 크다. 즉, 마지막 두 수의 크기 비교와 관련되기 때문에 똑같이 최적화가 필요하고 원리가 유사하다.상세한 것은 코드를 보십시오.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = 1e9+7;

char num[5010];

int dp[5010][5010]; 
int sum[5010][5010];
pair<int,int> cmp[5010][5010];

int isLE(int a,int b,int c,int d){
    int len = b-a+1;

    int i=0;
    if(a>0){
        pair<int,int> pre = cmp[a-1][len];
        if(pre.second){ 
            if(pre.first){  
                cmp[a][len].first = pre.first;
                cmp[a][len].second = pre.second - 1;
                return pre.first;
            }else{          
                i= len-1 ;
            }
        }else{
            i=0;
        }
    }

    for(;i<len;i++){
        if(num[a+i]>num[c+i]){
            cmp[a][len].first = 1;
            cmp[a][len].second = i;
            return 1;
        }else if(num[a+i]<num[c+i]){
            cmp[a][len].first = -1;
            cmp[a][len].second = i;
            return -1;
        }
    }
    cmp[a][len].first = 0;
    cmp[a][len].second = len-1;
    return 0;
}

int main(){
    int n;
    cin>>n;
    scanf("%s",num);
    for(int i=0;i<n;i++){
        for(int j=i;j>=1;j--){  
            if(num[j]=='0'){
                dp[i][i-j+1]=0;
            }else{
                int start = j-1 - (i-j);
                if(start<0)start=0;
                if(j-1 - start == i-j){
                    if(isLE(start,j-1,j,i) >=0){
                        start++;
                    }
                }
                int tmp = sum[j-1][j-start];
                dp[i][i-j+1]+=tmp;
                dp[i][i-j+1]%=mod;
            }
            sum[i][i-j+1]=sum[i][i-j]+dp[i][i-j+1];
            sum[i][i-j+1]%=mod;
        }
        dp[i][i+1]=1;
        sum[i][i+1]=sum[i][i]+dp[i][i+1];
        sum[i][i+1]%=mod;
    }
    int ans = 0;
    for(int i=0;i<=n;i++){
        ans+=dp[n-1][i];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

E New Year and Three Musketeers
2점 답안+욕심으로 답안이 가능한지 판단한다.2분 부분은 말할 것도 없고, 해는 틀림없이 [n/3,n]이라는 구간에 있다.욕심이 많아 화승총수와 적에게 순서를 정해 큰 것부터 작은 것까지 순서대로 처리해야 한다는 게 난점이다.적 배분 원칙은 약한 총잡이에게 우선 배분하고, 더 적은 총잡이에게 우선 배분하는 것이다.또 한 개의 구덩이를 주의해야 한다. 답은 세 명의 총잡이의 최장 근무시간이 아니다. 누군가가 기다릴 수 있기 때문에 협동작전의 시간이 초과되었는지도 고려해야 한다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int m[10];
int t[200010];
int n;

bool judge(int x){
    int cnt[3]={0,0,0};
    int share = 0;
    for(int i=n-1;i>=0;i--){
        if(t[i]<=m[0]){
            if(cnt[0]<x){
                cnt[0]++;
            }else if(cnt[1]<x){
                cnt[1]++;
            }else if(cnt[2]<x){
                cnt[2]++;
            }else{
                return 0;
            }
        }else if(t[i]<=m[1]){
            if(cnt[1]<x){
                cnt[1]++;
            }else if(cnt[2]<x){
                cnt[2]++;
            }else{
                return 0;
            }
        }else if(t[i]<=m[2]){
            if(cnt[2]<x){
                cnt[2]++;
            }else if(t[i]<=m[0]+m[1] && cnt[0]<x && cnt[1]<x){
                cnt[0]++;
                cnt[1]++;
                share++;
            }else{
                return 0;
            }
        }else if(t[i]<=m[0]+m[1]){
            if(cnt[0]<x && cnt[1]<x){
                cnt[0]++;
                cnt[1]++;
                share++;
            }else if(cnt[0]<x && cnt[2]<x){
                cnt[0]++;
                cnt[2]++;
                share++;
            }else if(cnt[1]<x && cnt[2]<x){
                cnt[1]++;
                cnt[2]++;
                share++;
            }else{
                return 0;
            }
        }else if(t[i]<=m[0]+m[2]){
            if(cnt[0]<x && cnt[2]<x){
                cnt[0]++;
                cnt[2]++;
                share++;
            }else if(cnt[1]<x && cnt[2]<x){
                cnt[1]++;
                cnt[2]++;
                share++;
            }else{
                return 0;
            }
        }else if(t[i]<=m[1]+m[2]){
            if(cnt[1]<x && cnt[2]<x){
                cnt[1]++;
                cnt[2]++;
                share++;
            }else{
                return 0;
            }
        }else{
            if(cnt[0]<x && cnt[1]<x && cnt[2]<x){
                cnt[0]++;
                cnt[1]++;
                cnt[2]++;
                share++;
            }else{
                return 0;
            }
        }
    }
    if(share>x)return 0;
    return 1;
}

int bs(int l,int r){
    int mid;
    int ans = 200000;
    while(l<=r){
        mid = (l+r)>>1;
        if(judge(mid)){
            r=mid-1;
            ans = min(ans,mid);
        }else{
            l=mid+1;
        }
    }   
    return ans;
}

int main(){

    cin>>n;
    for(int i=0;i<3;i++){
        cin>>m[i];
    }
    sort(m,m+3);
    int sum = m[0]+m[1]+m[2];
    for(int i=0;i<n;i++){
        scanf("%d",&t[i]);
    }
    sort(t,t+n);
    if(t[n-1]>sum){
        cout<<-1<<endl;
    }else{
        int ans = bs(n/3,n);
        cout<<ans<<endl;
    }
    return 0;
}