トップ > AtCoder > square869120Contest #1(E、G)

square869120Contest #1(E、G)

AtCoder プロコン

忘れそうなのでEとGも。E以降は「アレ？この難易度でいいのか？」と思いながら解いてました。

E - 散歩 (E869120 and Path Length)

各街に自然数aiが設定されていて、街i-1と街iとの距離はa(i-1)aiで定められています。散歩する街の順番が与えられるので、街1から初めて街1で終わる散歩の距離の総和を求めてください。

解法

aiはものすごく大きいので普通に掛け算していると間に合わない。よってビットを用いた累乗で都市間の距離を求めます。

さらに、毎回街の移動をループ回しながらやるとO(N2)でTLEするので予め街1からの距離に変換しておきます。ここではlong long型ならオーバーフローしないのでmodは取りません。（取ったらWAしました）

後は街iから街jへ移動するときは(i<j)、（街1から街jの距離）ー（街1から街iの距離）で出せます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
ll modpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)  ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ret;
}
int main(){
    int n,q;   cin>>n>>q;
    vector<ll> a(n),c;    c.push_back(0);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<q;i++){
        int ic;    cin>>ic;
        c.push_back(ic-1);
    }
    c.push_back(0);
    vector<ll> dist;  dist.push_back(0);
    for(int i=1;i<n;i++){
        dist.push_back(modpow(a[i-1],a[i]));
    }
    //a0からの距離に変換
    for(int i=2;i<n;i++) dist[i]=dist[i-1]+dist[i];
    ll ans=0;
    for(int i=0;i<=q;i++){
        int a=max(c[i+1],c[i]),b=min(c[i+1],c[i]);
        ll add=dist[a]-dist[b];
        ans=(ans+add)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

G - Revenge of Traveling Salesman Problem

問題概要

TSPに「スタートから累計t移動した時にその辺が消失する。それまでにその辺は渡り終わっていなければならない」というルールを追加。

最短距離とその距離の通り方が何通りあるか求める問題。

G: Revenge of Traveling Salesman Problem - square869120Contest #1 | AtCoder

解法

普通にTSP。WAを連発しました。最初は「TSP→DPの復元」、次に「TSP→TSPと同じ向きで通り数のカウント」、最後は「TSPと同時に何通りあるかカウント」と遷移していきましたが、実は全部OK。最後のが1番簡潔だけど。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class edge{
    public:
    ll t,d,lim;
    edge(ll it,ll id,ll ilim){
        t=it;   d=id;   lim=ilim;
    }
};
vector<edge> e[20];
ll dp[16][1<<16];
ll cnt[16][1<<16];
int main(){
    ll n,m; cin>>n>>m;
    for(ll i=0;i<m;i++){
        ll s,t,d,ti;    cin>>s>>t>>d>>ti;   s--;    t--;
        e[s].push_back(edge(t,d,ti));
        e[t].push_back(edge(s,d,ti));
    }
    for(ll i=0;i<n;i++){
        for(ll j=(1<<n)-1;j>=0;j--){
            dp[i][j]=2e14; cnt[i][j]=0;
        }
    }
    dp[0][0]=0;  cnt[0][0]=1;
    for(ll i=0;i<(1<<n)-1;i++){
        for(ll j=0;j<n;j++){
            if(dp[j][i]==2e14)   continue;
            for(ll k=0;k<(ll)e[j].size();k++){
                if(dp[j][i]+e[j][k].d<=e[j][k].lim){
                    ll next=i|(1<<e[j][k].t);
                    if(next==i)   continue;
                    if(dp[e[j][k].t][next]>dp[j][i]+e[j][k].d){
                        dp[e[j][k].t][next]=dp[j][i]+e[j][k].d;
                        cnt[e[j][k].t][next]=cnt[j][i];
                    }
                    else if(dp[e[j][k].t][next]==dp[j][i]+e[j][k].d){
                        cnt[e[j][k].t][next]+=cnt[j][i];
                    }
                }
            }
        }
    }
    if(dp[0][(1<<n)-1]==2e14){
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
    cout<<dp[0][(1<<n)-1]<<" "<<cnt[0][(1<<n)-1]<<endl;
    return 0;
}

残りはまだ解いてません。

にしても、やはりこのコンテストは中学生主催、というのもあるのだろうけど、他のコンテストに比べて難易度が低い。

初心者向けのコンテストかな…