yukicoder no.337/338/339/340 - アルゴリズマーの備忘録

うん。Twitterで宣言されていた通り比較的簡単だった。

No.337 P versus NP

問題概要

N,PがN=N*Pを満たすなら"="、満たさないなら"!="を出力せよ。

解説

int型で受け取ってif分岐すればOK。この程度なら三項演算子使いますね。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,p;   cin>>n>>p;
    cout<<(p==n*p?"=":"!=")<<endl;
    return 0;
}

No.338 アンケート機能

問題概要

2択のアンケートを行ったらA%とB%に別れた（A,Bは四捨五入された整数）。最小で何人が回答したか。

No.338 アンケート機能 - yukicoder

解説

多くてもA+Bは100かな…と思ってAとBをそれぞれ0〜100まで試せば通るはず。自分はそれぞれ1000まで試しても時間に間に合うということで容赦なく1000まで計算させました。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int A,B;   cin>>A>>B;
    int ans=INT_MAX;
    for(int a=0;a<=1000;a++){
        for(int b=0;b<=1000;b++){
            if(a+b==0)   continue;
            if(round((double)100*a/(a+b))!=A)   continue;
            if(round((double)100*b/(a+b))!=B)   continue;
            ans=min(ans,a+b);
        }
    }
    cout<<ans<<endl;
    return 0;
}

No.339 何人が回答したのか

問題概要

No.338の円グラフ版。

複数の選択肢があるアンケートを行ったら、選択肢iがai%(aiは丁度整数)だった。最小で何人が回答したか。

No.339 何人が回答したのか - yukicoder

解説

このアンケートは100人以下であることは明らかです（100人で回答を行えば選択肢iを選んだ人はai人になる）。

更に、全体のaiの公約数で割ってもその比率には影響を与えません。

答えは全体のgcdを求めて、gcdで割った後のaiの総和です。 (例：50%、30%、20%ならgcdの10で割った後の5人、3人、2人の計10人が回答すれば成立する）

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    return a%b==0?b:gcd(b,a%b);
}

int main(){
    int n; cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int g=a[0];
    for(int i=1;i<n;i++) g=gcd(g,a[i]);
    int ans=0;
    for(int i=0;i<n;i++) ans+=a[i]/g;
    cout<<ans<<endl;
    return 0;
}

No.340 雪の足跡

問題概要

(1,1)から(h,w)へと散歩したいが、大人が通った道しか通ることが出来ない。最短距離はいくつか。

No.340 雪の足跡 - yukicoder

解説

各格子点から何処へ行けるか分かればダイクストラに任せられます。

「まずは愚直に連結リスト」…O(nm*max(h,w))で間に合わない。

「じゃあ、boolを持たせたセグ木」…間に合わない訳では無いのかもしれないけど、実装面倒だしboolが無駄。

→imos法。（参考：いもす法 - いもす研 (imos laboratory)）

縦と横を完全に分けて考えてやれば出来る。若干実装に頭を使います。

#include <bits/stdc++.h>
using namespace std;
#define fst first
#define sec second
int dist[1000][1000];
int lr[1000][1000],ud[1000][1000];
int main(){
    int w,h,n; cin>>w>>h>>n;
    for(int i=0;i<n;i++){
        int m; cin>>m;
        vector<pair<int,int>> b;
        for(int j=0;j<m+1;j++){
            int num;   cin>>num;
            b.push_back(make_pair(num/w,num%w));//y,x
        }
        for(int j=1;j<=m;j++){
            if(b[j].fst==b[j-1].fst){//横方向の移動
                int sml=min(b[j].sec,b[j-1].sec);
                int big=max(b[j].sec,b[j-1].sec);
                lr[b[j].fst][sml]++;    lr[b[j].fst][big]--;
            }
            else{
                int sml=min(b[j].fst,b[j-1].fst);
                int big=max(b[j].fst,b[j-1].fst);
                ud[sml][b[j].sec]++;    ud[big][b[j].sec]--;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=1;j<w;j++) lr[i][j]+=lr[i][j-1];
    }
    for(int i=1;i<h;i++){
        for(int j=0;j<w;j++) ud[i][j]+=ud[i-1][j];
    }
    for(int i=0;i<h;i++) for(int j=0;j<w;j++) dist[i][j]=INT_MAX;
    dist[0][0]=0;
    priority_queue<tuple<int,int,int>> pq;
    pq.push(make_tuple(-0,0,0));
    while(!pq.empty()){
        auto it=pq.top();  pq.pop();
        int cost=-get<0>(it);
        int y=get<1>(it),x=get<2>(it);
        if(cost>dist[y][x])    continue;
        if(y==h-1&&x==w-1){
            cout<<cost<<endl;
            return 0;
        }
        cost++;
        if(lr[y][x]>0&&dist[y][x+1]>cost){
            dist[y][x+1]=cost;
            pq.push(make_tuple(-cost,y,x+1));
        }
        if(x>0&&lr[y][x-1]>0&&dist[y][x-1]>cost){
            dist[y][x-1]=cost;
            pq.push(make_tuple(-cost,y,x-1));
        }
        if(ud[y][x]>0&&dist[y+1][x]>cost){
            dist[y+1][x]=cost;
            pq.push(make_tuple(-cost,y+1,x));
        }
        if(y>0&&ud[y-1][x]>0&&dist[y-1][x]>cost){
            dist[y-1][x]=cost;
            pq.push(make_tuple(-cost,y-1,x));
        }
    }
    cout<<"Odekakedekinai.."<<endl;
    return 0;
}

感想

全体的に簡単な方でしたね（前回比）…