トップ > AtCoder > AtCoder Begginer Contest 032

AtCoder Begginer Contest 032

AtCoder

最近、ABCの難易度の低下が激しいと思ったけど、前回よりは難しくなった？

A - 高橋君と青木君の好きな数

問題概要

n以上の整数で、aでもbでも割れる最小の整数を答えよ。
http://abc032.contest.atcoder.jp/tasks/abc032_a

解説

取り敢えずaでもbでも割れるってことは求める整数はaとbの最小公倍数の倍数。

自分は互除法を使ってLCM(a,b)=a*b/GCD(a,b)で出しましたが、aとbの制限が緩いので1から順に試して、aでもbでも割り切れた時、でもOKです。

x×LCM≧nとなるxはx=ceil(n/LCM)ですが、それさえも面倒だと思ったのか、x=1から順に試していって、x×LCMがn以上になった時点でそれを出力するという初心者なコードを書きました。

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(a>b)    swap(a,b);
    while(a%b!=0){
        a=a%b;  swap(a,b);
    }
    return b;
}
int main(){
    int a,b;   cin>>a>>b;
    int n; cin>>n;
    int ans=a*b/gcd(a,b);
    for(int i=1;;i++){
        if(i*ans>=n){
            cout<<i*ans<<endl;
            return 0;
        }
    }
}

B - 高橋君とパスワード

問題概要

文字列s中のk文字の部分文字列の種類を答えよ。
http://abc032.contest.atcoder.jp/tasks/abc032_b

解説

文字数≦300と小さいので、最初の地点を全通り試して、setに1つずつ入れていく。最終的なsetの大きさが答え。

今回は大丈夫だが、10万文字など文字数が大きくなると、毎回文を作りなおしているとTLEするので、その時は尺取り法を用いる。k文字を越えた時点で、新しい文は左端1文字を削除してから右端1文字を追加した文字列になる。この方法でk文字の文字列を作ってもいいけど、やや面倒です。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;   cin>>s;
    int k; cin>>k;
    set<string> ls;
    for(int i=0;i+k<=s.size();i++){
        ls.insert(s.substr(i,k));
    }
    cout<<ls.size()<<endl;
    return 0;
}

C - 列

問題概要

数列a1,a2,...,anの中で、連続する部分列の積がkを超えないように部分列を選んだ時の長さの最大値を求めよ。
http://abc032.contest.atcoder.jp/tasks/abc032_c

解説

B問題で少し触れた尺取り法を用いる問題です。a1から順にかけていき、aiでkを越えたとします。その時、aiを含む部分列にa1がいると積がkを越えるわけですから、a1は取り除いてしまいましょう。同様に左から取り除いていって、積がk以下になるまで続けます。

このとき、ai+1を含む部分列にa1はあってはいけません。a1〜aiまでの積を含むことになるので絶対にkを越えます。このように、

  • 左から順にかけていく（部分列に追加する）
  • 積がkを越えている間、左から順に割っていく（部分列から取り除く）

という操作をループで回せばOKです。

ただし、数列内に0があった場合はコーナーケース。全部かけてしまえば積は0になってkの値に関わらず答えはnです。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,k; cin>>n>>k;
    vector<ll> s(n);
    for(int i=0;i<n;i++){
        cin>>s[i];
        if(s[i]==0){
            cout<<n<<endl;
            return 0;
        }
    }
    int end=0,ans=0,cnt=0;
    ll sum=1;
    for(int i=0;i<n;i++){
        sum*=s[i];  cnt++;
        while(sum>k&&cnt>0){
            sum/=s[end];    end++;  cnt--;
        }
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}

D - ナップサック問題

問題概要

0-1ナップサック問題を解け。ただし、3パターンの制限のうち少なくとも1つは満たされる。
http://abc032.contest.atcoder.jp/tasks/abc032_d

解説

この問題、3つのアルゴリズムを使い分ける問題です。具体的には、

  • N≦30のとき、半分全列挙
  • N≦200 かつ全ての i(1≦i≦N) について 1≦wi≦1000のとき、DPの添字に重さを用いる
  • N≦200 かつ全ての i(1≦i≦N) について 1≦vi≦1000のとき、DPの添字に価値を用いる

と使い分けます。因みにそれぞれの解法は全て蟻本に載っています。

半分全列挙は、全て列挙するとO(2N)でTLEしますが、O(2N/2)ならN/2≦15で間に合います。荷物を2グループに分けてその中で荷物の選び方（選ばないという選択肢もあり）を全列挙して価値の総和と重さの総和を記録しておきます（ただし、その選び方がWを越えるなら記録しなくてOK)。その後、1つ目のグループを価値の高い順、2つ目のグループを重さの軽い順に並べ、軽い方から、 * 1つ目のグループの先頭の重さ＋2つ目のグループの先頭>Wである限り1つ目のグループの先頭を削除。 * 答えを1つ目のグループの先頭の価値＋2つ目のグループの先頭の価値で更新できるなら更新。 * 2つ目のグループの先頭を削除。 という操作を2つ目のグループが無くなるまで実行すればOKです。 因みに自分はdeque使ってますね…（1手間無駄な気がする）

DPの添字に重さを用いる場合は重さiでの価値の最大値、価値を用いる場合は価値iでの重さの最小値を記録していきます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll v[210],w[210];
map<ll,ll> ls[2];
ll N,W;
void brute(int i,int end,ll wsum,ll vsum,int op){
    if(i==end){
        if(wsum<=W)    ls[op][wsum]=max(ls[op][wsum],vsum);
        return;
    }
    brute(i+1,end,wsum+w[i],vsum+v[i],op);
    brute(i+1,end,wsum,vsum,op);
}

int main(){
    cin>>N>>W;
    bool flag=true;//trueでwベースのDP
    for(int i=0;i<N;i++){
        cin>>v[i]>>w[i];
        if(w[i]>1000) flag=false;//vベースのDP
    }
    if(N<=30){//半列挙
        brute(0,N/2,0,0,0);
        brute(N/2,N,0,0,1);
        ll ans=0;
        deque<pair<ll,ll>> dq;
        vector<pair<ll,ll>> vec;
        for(auto it:ls[1])  vec.push_back(it);
        reverse(vec.begin(),vec.end());//重い順に並び替え
        //重い順にdequeに突っ込んでいって価値順に並べる
        for(auto it:vec){
            while(!dq.empty()&&dq.back().second<it.second){
                dq.pop_back();
            }
            dq.push_back(it);
        }
        for(auto i:ls[0]){//ls[0]は軽い順に見る
            ll curw=i.first,curv=i.second;
            while(!dq.empty()&&curw+dq.front().first>W)    dq.pop_front();
            ans=max(ans,curv+dq.front().second);
        }
        cout<<ans<<endl;
        return 0;
    }
    else if(flag){//wベースのDP
        ll dp[N][W+1]; memset(dp,0,sizeof(dp));
        dp[0][w[0]]=v[0];
        for(int i=1;i<N;i++){
            for(int j=0;j<=W;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=w[i])    dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
            }
        }
        ll ans=0;
        for(int i=0;i<=W;i++)    ans=max(ans,dp[N-1][i]);
        cout<<ans<<endl;
        return 0;
    }
    else{//vベースのDP
        ll dp[200010];
        for(int i=0;i<200010;i++)   dp[i]=LLONG_MAX;
        dp[0]=0;
        ll usemax=0;
        for(int i=0;i<N;i++){
            ll tmp=usemax;
            for(int j=tmp;j>=0;j--){
                if(dp[j]==LLONG_MAX) continue;
                if(dp[j]+w[i]<=W){
                    dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i]);
                    usemax=max(usemax,j+v[i]);
                }
            }
        }
        cout<<usemax<<endl;
        return 0;
    }
}

感想

D問題面倒だった。過去に解いててそのコードが残っていればコピペで一瞬だったのに…
でも久しぶりの半分全列挙で結構戸惑ったので練習になった。