トップ > AtCoder > square869120Contest #1(A〜D)

square869120Contest #1(A〜D)

AtCoder プロコン

現在FとH以外は解いたけど、１つの記事にするとえげつない長さになるので2〜3回に分割します。

今回はA〜D問題。比較的簡単で、自分もコンテスト中（夕飯食べたり風呂入ったりで参加したのは実質1時間）でDまでは解きました。

A - E869120列車 (E869120 Trains)

問題概要

5:00から23:00までの間に電車がN本等間隔で走ったそうです。最初の1本が5:00丁度、最後の1本が23:00丁度に通った時、何分間隔で電車が通ったか求めよ。

A: E869120列車 (E869120 Trains) - square869120Contest #1 | AtCoder

解法

5:00〜23:00は18時間=18×60分。その間にN本走ったので、18×60/(N-1)を出力するだけです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    printf("%.15lf\n",18*60.0/(n-1));
    return 0;
}

B - ケーキ・カッティング (Cake Cutting)

問題概要

長方形の座標の格子点上にイチゴがいくつかあります。(0,0)と座標の端の格子点のを結ぶ直線で長方形を分割し、イチゴを等分してください。

B: ケーキ・カッティング (Cake Cutting) - square869120Contest #1 | AtCoder

解法

H,W,N≦10と数がかなり小さいので普通に全探索。(0,0)以外の交点を2重ループで回しながら（最初にその格子点が端か判定）、各イチゴが直線のどちら側にあるか判定するのですが、自分は座標を用いました。

(0,0)、(a,b)を通る直線はay=bxです。イチゴの座標を(i,j)とした時、

  1. イチゴが直線より上にあるならay＞bx
  2. イチゴが直線上にあるならay＝bx
  3. イチゴが直線より下にあるならay＜bx

2.は問題文より該当するイチゴがあった時点で不適。1と3のイチゴの数が一致すればその格子点は条件を満たします。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int h,w,n; cin>>h>>w>>n;
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
    bool unuse=true;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            if(i!=w&&j!=h)    continue;
            //(i,j)でカット。iy=jx。
            int left=0,right=0;
            for(int k=0;k<n;k++){
                int x=j*a[k].first,y=i*a[k].second;
                if(x==y){
                    left=0;    right=-1;
                    break;
                }
                else if(x>y) left++;
                else  right++;
            }
            if(left==right){
                unuse=false;
                cout<<"("<<i<<","<<j<<")"<<endl;
            }
        }
    }
    if(unuse) cout<<-1<<endl;
    return 0;
}

C - お金の街 (The Money Town)

問題概要

各街にお金がおいてあり、それを回収しながら散歩する。始点は自由で同じ街を通らずに散歩するとき、最大いくらお金を集められるか。

C: お金の街 (The Money Town) - square869120Contest #1 | AtCoder

解法

散策可能な通り数が200万通り以下なので全探索して1億回。ギリギリ間に合いました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
vector<ll> d;
vector<int> e[55];
bool visited[55];
ll dfs(int cur){
    visited[cur]=true;
    ll ret=0;
    for(int i=0;i<(int)e[cur].size();i++){
        if(!visited[e[cur][i]])   ret=max(ret,dfs(e[cur][i]));
    }
    visited[cur]=false;
    return ret+d[cur];
}
    
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        ll id;  cin>>id;
        d.push_back(id);
    }
    for(int i=0;i<k;i++){
        int x,y;   cin>>x>>y;  x--;    y--;
        e[x].push_back(y);  e[y].push_back(x);
    }
    ll ans=0;
    for(int i=0;i<n;i++){//start point
        ans=max(ans,dfs(i));
    }
    cout<<ans<<endl;
    return 0;
}

D - square1001の通学経路 (square1001's School Road)

問題概要

座標上で(1,1)から(W,H)まで格子点を最短距離で進むが、(i,j)(i+1,j)(i+1,j+1)(i,j+1)のいづれかを通らなければならない。

この条件を満たす移動方法は何通りあるか。

D: square1001の通学経路 (square1001's School Road) - square869120Contest #1 | AtCoder

解法

最短距離で進む＝戻れない、です。ここで、上に挙げた頂点が通れなくなるのは(i-1,j+2)含む左上、もしくは(i+2,j-1)を含む右下を通ってしまった時です。これらを通ってはいけないので予め-1とでも値を初期化しておけばあとは見慣れたDPでOKです。

（今気が付きましたが、この処理は累積和使うと更に早くなるんですかね…）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll dp[1200][1200];
int main(){
    int h,w,k; cin>>h>>w>>k;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<k;i++){
        int x,y;   cin>>x>>y;
        //(x+2,y-1)より右下と(x-1,y+2)より左上を0に。
        for(int a=x+2;a<=w;a++){
            for(int b=y-1;b>=0;b--) dp[b][a]=-1;
        }
        for(int b=y+2;b<=h;b++){
            for(int a=x-1;a>=0;a--) dp[b][a]=-1;
        }
    }
    dp[1][1]=1;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(dp[i][j]==-1) continue;
            dp[i][j]%=mod;
            if(i+1<=h&&dp[i+1][j]!=-1){
                dp[i+1][j]+=dp[i][j];
            }
            if(j+1<=w&&dp[i][j+1]!=-1){
                dp[i][j+1]+=dp[i][j];
            }
        }
    }
    cout<<dp[h][w]<<endl;
    return 0;
}

続きは週末にでも。（F問題だけがサッパリ分からない）