トップ > Codeforces > Codeforces Round #339 (Div. 2)

Codeforces Round #339 (Div. 2)

Codeforces

誤読が酷い。

A. Link/Cut Tree

問題概要

l〜rの間のk^n(nは整数)を満たすものを全て出力せよ。

Problem - A - Codeforces

解法

普通に実装すればいいんじゃ？と思って提出→WA。

JavaのBigintegerやPython使えば普通に通る。

C++で通すなら、普通に解くのではなく、lとrを割っていき、l≦1≦rを満たすものを数える。 最初に1度も割らずにチェックして、以降は割りながら配列に何回割ったのかを記録。 その後、k^a[i]を出力すればOK。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main(){
    ld l,r,k;   cin>>l>>r>>k;
    ll cnt=0;
    vector<ll> ans;
    while(1<=r){
        if(l<=1)  ans.push_back(cnt);
        cnt++;
        l/=k;   r/=k;
    }
    ll out=1;
    cnt=0;
    if(ans.size()==0){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0;i<(int)ans.size();i++){
        while(cnt<ans[i]){
            out*=k; cnt++;
        }
        cout<<(i?" ":"")<<out;
    }
    cout<<endl;
    return 0;
}

B. Gena's Code

問題概要

n個の数字の積を出力せよ。しかし、少なくともn-1個は各桁が1つ以下のの1と0で出来ていて、leading-0は無い。 数字の桁数の指定はないが、数字の桁数は合計で10万桁以下である。

Problem - B - Codeforces

解法

そのよくわからない条件は何？と思ったので、例を上げると、0,1,10,100,1000,...となります。

これってlog10とればいいですよね？ということで0の数を数えてあげて、残りの条件を合わない1個を先に出力してから合わせて出力します。

ただし、0の数字があった瞬間、積は0というコーナーケースに気を付けてください。

因みに自分は条件を満たすものは必ずn-1個と誤読して、n個全て条件を満たすものに対して0の羅列を出力する結果に。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    int lg10=0;
    string nobea="1";
    for(int i=0;i<n;i++){
        string s;   cin>>s;
        if(s=="0"){
            cout<<0<<endl;
            return 0;
        }
        int onecount=0;
        for(int i=0;i<(int)s.size();i++){
            if(s[i]-'0'==1) onecount++;
            else if(s[i]-'0'!=0){
                nobea=s;
                goto next;
            }
        }
        if(onecount==1)  lg10+=s.size()-1;
        else if(onecount>=2){
            nobea=s;
        }
        next:;
    }
    cout<<nobea;
    for(int i=0;i<lg10;i++)  cout<<0;
    cout<<endl;
    return 0;
}

C. Peter and Snow Blower

問題概要

ある点を中心にn頂点からなる多角形（凸包である保証はない）を1回転させた面積を求めよ。

2≦i≦nでa[i-1]とa[i]は直線で結ばれていて、a[n]とa[1]も直線で結ばれている。

Problem - C - Codeforces

解法

各頂点と中心の距離の最大値をr1,各線分と中心の距離の最小値をr2とした時の(r1^2-r2^2)π。

r2が線分なのは中心(0,0)、2点(1,1)(-1,1)を結ぶ線を考えると交点が(0,1)の時に距離が最短になるから。

r2を求める際の交点は線分を作る2点をa,bとして、中心をoとしたとき、a+(b-a)(o-a)/(b-a)2と表せます。（掛け算部分は内積）

よく分からない人はベクトルを考えて、oからabに下ろした垂線の足をhとした時、ah=nabと定義すれば内積=0で解けます。

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld PI=3.14159265358979;
class P{
    public:
    ll x,y;
    P(){
        x=0;   y=0;
    }
    P(ll a,ll b){
        x=a;    y=b;
    }
    P operator+(P a){
        return P(x+a.x,y+a.y);
    }
    P operator-(P a){
        return P(x-a.x,y-a.y);
    }
    P& operator=(P a){
        x=a.x;  y=a.y;
        return *this;
    }
    bool operator<(P a){
        if(x!=a.x)    return x<a.x?true:false;
        else return y<a.y?true:false;
    }
    bool operator>(P a){
        if(x!=a.x)    return x>a.x?true:false;
        else return y>a.y?true:false;
    }
    bool operator==(P a){
        return (x==a.x&&y==a.y)?true:false;
    }
};
ll dot(P a,P b){
    return a.x*b.x+a.y*b.y;
}
ll det(P a,P b){
    return a.x*b.y-a.y*b.x;
}
ll dist(P a,P b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ld linedist(P a,P b,P c){
    if(dot(b-a,c-a)<0)    return dist(a,c);
    if(dot(a-b,c-b)<0)    return dist(b,c);
    ld n=(ld)dot(b-a,c-a)/dot(b-a,b-a);
    ld x=n*(b.x-a.x)+a.x,y=n*(b.y-a.y)+a.y;
    return (x-c.x)*(x-c.x)+(y-c.y)*(y-c.y);
}

int main(){
    ll n;   cin>>n;
    P c;    cin>>c.x>>c.y;//center
    vector<P> p(n);
    for(ll i=0;i<n;i++)   cin>>p[i].x>>p[i].y;
    p.push_back(p[0]);
    ld shortest=1e18;
    for(ll i=1;i<=n;i++){
        shortest=min(shortest,linedist(p[i],p[i-1],c));
    }
    ll longest=0;
    for(ll i=0;i<n;i++){
        longest=max(longest,dist(c,p[i]));
    }
    cout<<setprecision(15)<<(longest-shortest)*PI<<endl;
    return 0;
}

cmathのM_PIは無くて困って自分で定義し、オーバーフローされたのでllとldを入れ、long doubleをprintfしたら謎の挙動を示すのでcoutで出力させられる、と悲惨な問題でした。

しかし1番悲惨なのはこの問題が凸包だと思ったこと。解けるわけ無い…

まあ、凸包実装したこと無いのでグラハムスキャン実装できただけで満足するべきなのでしょう。

感想

0完。事故が酷い。

0完と3〜4完をウロチョロしてるけど、ratingが1400切って悲惨。

いくらTopCoderの問題文に比べてCodeforcesの問題文難しいとはいえ、読めないの何とかしたい…

先にyukiの解き残しやってからD解きます。