Codeforces ラウンド #280 (ディビジョン 2) ソリューション レポート A.B.C.D.E._html/css_WEB-ITnose

私のレベルが上がったからなのか、CFの質問が少なくなったからなのかはわかりません。 。 。 。 。 。

A - ワーニャとキューブ

水の質問。 。暴力的な列挙でも構いません。 。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int s[100], sum[100];int main(){        int n, i;        s[1]=1;        sum[i]=1;        scanf("%d",&n);        for(i=2;i<=10000;i++){                s[i]=s[i-1]+i;                sum[i]=sum[i-1]+s[i];                if(sum[i]>=n)break;        }        printf("%d\n",i-1);        return 0;}

B - Vanya and Lanterns

水の質問。 。隣接する 2 つの間の最短距離 /2 を激しく見つけ、それを境界と比較して最長距離を見つけます。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int a[2000];int main(){        int n, l, i, j;        double d, max1=-1;        scanf("%d%d",&n,&l);        a[0]=0;        a[n+1]=l;        for(i=1;i<=n;i++){                scanf("%d",&a[i]);        }        sort(a,a+n+2);        for(i=2;i<=n;i++){                max1=max(max1,(a[i]-a[i-1])/2.0);        }        max1=max(max1,a[1]-0.0);        max1=max(max1,l*1.0-a[n]);        printf("%.10lf\n",max1);        return 0;}

C - Vanya and Exams

貪欲。

必要な書類が少ないものから始めて合計してください。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;struct node{        LL f, e;}fei[110000];int cmp(node x, node y){        return x.e<y.e;}int main(){        int i;        LL n, r, ave, s, sum, ss, ans=0;        scanf("%I64d%I64d%I64d",&n,&r,&ave);        sum=n*ave;        s=0;        for(i=0;i<n;i++){                scanf("%I64d%I64d",&fei[i].f,&fei[i].e);                s+=fei[i].f;        }        ss=sum-s;        if(ss<=0)        {                printf("0\n");                return 0;        }        sort(fei,fei+n,cmp);        //printf("%d\n",ss);        for(i=0;i<n;i++){                if(fei[i].f>=r) continue ;                if(ss-(r-fei[i].f)<=0){                        ans+=ss*fei[i].e;                        break;                }                else{                        ss-=r-fei[i].f;                        ans+=fei[i].e*(r-fei[i].f);                }                //printf("%d\n",ss);        }        printf("%I64d\n",ans);        return 0;}

D - Vanya and Computer Game

ゲーム中に2点のタイムについて考えましたが、求めた後に誰のタイムであるかを判断する方法がわかりませんでした。時間。 。翌日、そのことに気づきました。 。割り切れるかどうかだけ判断してください。 。 。 。どうしてあの時思いつかなかったんだろう？ 。 。押し下げられた。 。

まず時間軸を拡大し、1/x 秒と 1/y 秒を y と x に拡大し、時間を見つけたら、割り切れるかどうかを判断します。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int main(){        LL n, x, y, i, z, low, high, mid, ans;        scanf("%I64d%I64d%I64d",&n, &x, &y);        while(n--) {                scanf("%I64d",&z);                low=1;                high=1e16;                while(low<=high) {                        mid=low+high>>1;                        if(mid/x+mid/y>=z) {                                high=mid-1;                                ans=mid;                        }                        else low=mid+1;                }                if(ans%x==0&&ans%y==0) puts("Both");                else if(ans%x==0) puts("Vova");                else puts("Vanya");        }        return 0;}

E - Vanya and Field

今回のEの質問は良い気がします。 。 。まず、gcd が 1 であるため、n 個の数値すべてにアクセスでき、繰り返されないことが保証されます。したがって、デフォルトで横座標 0 の特定の点から開始させることができます。次に、縦座標が 0 のとき、x 座標と y 座標の間のマッピング関係を見つけて保存できます。その後、座標を入力するたびに、数式を使用して座標が開始する点を決定できます。次に、最も出発点を見つけるだけです。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int _hash[1100000], a[1100000];int main(){        int n, m, dx, dy, i, j, x, y, pos, max1;        scanf("%d%d%d%d",&n,&m,&dx,&dy);        x=y=0;        for(i=0;i<n;i++){                a[x]=y;                x=(x+dx)%n;                y=(y+dy)%n;        }        memset(_hash,0,sizeof(_hash));        while(m--){                scanf("%d%d",&x,&y);                _hash[(y+n-a[x])%n]++;        }        max1=-1;        for(i=0;i<n;i++){                if(max1<_hash[i]){                        max1=_hash[i];                        pos=i;                }        }        printf("0 %d\n",pos);        return 0;}