Codeforces#284 Div 1簡単な問題解

A. Crazy Town
タイトルリンク
http://codeforces.com/contest/498/problem/A
テーマの大意
あなたに1つの无限の大きい区域をあげて、この区域はn条の形の例えばAx+By+C=0の无限の长い直线道路に分割されていくつかの街区になって、A地とBの座標を与えて、A地からB地まで少なくともどれだけの道を通り抜けて、直线と直线の交点を通り抜けることができないことに注意します
構想
最も少ない通過回数は、線分ABの端点を含まない中間部分と交わる直線の個数であり、意識して流せばいいことを証明しているが、実際にはAB両地をどのくらいの直線で完全に分割しているかを見ることであり、これらの直線は通過しなければならないが、他の直線は通過する必要はない.
しかし、問題はどのようにこれらの直線を探すかです.私は最初は非常にnaive的に各直線と直線ABの交点を求めて、それから交点が線分ABにあるかどうかを判断して、各種の特判は言わないで、導き出しの過程も間違いやすいです.しかし、私は赤い名前のおじいさんのコードを見てから、自分のtoo simpleを発見しました.入力する直線はすべてAx+By+C=0の形式であることに気づいて、私達は1つの2元関数f(x,y)とすることができて、明らかにf(xA,yA)とf(xB,yB)の記号が反対で、やっとこの直線を線分ABの端点を含まない中間部分を通り抜けることができます!
証明も簡単です.この直線と線分ABの端点を含まない中間部分との交点座標を(xt,yt)=0とすると、明らかにf(xt,yt)=0であり、(xt,yt)から先頭に進むと、f(x’,y’)の値は負になり、反対方向の反対側に進むと、f(x’,y’)の値は正になる
赤い名前のおじいさんは巨大ですね.
コード#コード#

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <cmath>

#define MAXN 10000
#define EPS 1e-7

using namespace std;

typedef long long int LL;

LL a[MAXN],b[MAXN],c[MAXN];
int n;

int dcmp(LL x)
{
    if(x>0) return 1;
    if(x<0) return -1;
    return 0;
}

int main()
{
    LL x1,y1,x2,y2;
    scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]);
    int tot=0;
    for(int i=1;i<=n;i++)
        if(dcmp(a[i]*x1+b[i]*y1+c[i])!=dcmp(a[i]*x2+b[i]*y2+c[i]))
            tot++;
    printf("%d
",tot);
    return 0;
}

B. Name That Tune
タイトルリンク
http://codeforces.com/contest/498/problem/B
テーマの大意
「開門大吉」では司会者からn曲が与えられ、各曲に1ドアが対応し、選手が1−n番ゲートに向かってドアのベルを順番に鳴らすと、ドアのベルは音楽を流し(クラシックな流行歌を単音色のメロディーで演じる)、i番ゲートに対して選手はTi秒の時間で音楽を聴き、1秒ごとに、選手はPi%の確率でこの曲の名前を聞き出すことができ、また100−Pi%の確率で次の秒まで待たなければならないが、Ti秒で選手は必ずこの曲の名前を聞き出すことができ、前のT秒選手が聞き出すことができる曲の個数の期待を求める.
構想
DPでこの問題を解決することが考えられます.f[i][j]で現在j秒目になって、i曲目を聴いてこの曲の名前が聞こえる確率を表す.明らかにf[0][0]=1であり、以下のDP方程式を出すことができる.
f[i][j]=f[i−1][j−1](1−Pi)0Pi+f[i−1][j−2](1−Pi)1Pi+...+f[i−1][j−Ti](1−Pi)Ti−1Pi+f[i−1][j−Ti](1−Pi)Ti
すなわち
f[i][j]=Σk≦Ti−1 f[i−1][j−k](1−Pi)k−1 Pi(前k−1秒ではこの曲が聞こえず、k秒目でこの曲が聞こえた)+f[i−1][j−Ti](1−Pi)Ti(前Ti秒では聞こえなかったが、最後にTi秒目でこの曲が聴こえなければならない確率)
このDPを最適化することができ,f[i][j]はf[i][j−1]のDP方程式と高度に類似しているため,f[i][j−1]の値tmpを維持することができる.
tmp=f[i−1][j−2](1−Pi)0+f[i−1][j−3](1−Pi)1+...+f[i−1][j−Ti−1](1−Pi)Ti−1
では
f[i][j]=Pi(1−Pi)tmp+f[i−1][j−1]Pi+f[i−1][j−Ti](1−Pi)Ti
これは特殊な場合であり,tmpにはTi項が最大であるため,j−Ti−1>=0であればDPからf[i][j]までの場合,tmpにf[i−1][j−Ti−1](1−Pi)Ti−1を減算する必要がある.
コード#コード#

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <cmath>

#define MAXN 11000

using namespace std;

double f[2][MAXN],ans=0;
int n,t;
int now=1,pre=0;

int main()
{
    scanf("%d%d",&n,&t);
    f[pre][0]=1;
    for(int i=1;i<=n;i++)
    {
        memset(f[now],0,sizeof(f[now]));
        double Pi;
        int Ti;
        scanf("%lf%d",&Pi,&Ti);
        Pi/=100;
        double tmp=0;
        for(int j=i;j<=t;j++)
        {
            tmp*=(1-Pi);
            tmp+=f[pre][j-1];
            if(j-Ti-1>=0) tmp-=f[pre][j-Ti-1]*pow(1-Pi,Ti);
            f[now][j]+=tmp*Pi;
            if(j-Ti>=0) f[now][j]+=f[pre][j-Ti]*pow(1-Pi,Ti);
            ans+=f[now][j];
        }
        swap(now,pre);
    }
    printf("%.6f
",ans);
    return 0;
}

C. Array and Operations
タイトルリンク
http://codeforces.com/contest/498/problem/C
テーマの大意
n個の数a 1...anをあげて、およびm個の操作数対(i,j)をあげて、毎回操作する時あなたは1つ(i,j)を選ぶことができて、統一的にai,ajの1つの公約数で割って、あなたに最大で何回このような操作を行うことができますかを聞きます
構想
明らかに、譲歩数を最大化するために、私たちが毎回割った公約数は質数です.また、異なる除数操作については、それらの間は互いに干渉せず、同じ除数操作は互いに干渉する.
スクリーン素数を先に処理し,次に[109−−−−√]内の素数pを列挙し,最大流でpを除く動作を最大何回まで行うことができるかを求めることができる.問題面制限i+jが奇数であるため、iとjのうちの1つが偶数であり、もう1つが奇数であることは明らかである.これにより、ソース点から奇数と表記されたすべての点への接続容量がこの点でpの出現回数であり、すべての奇数と表記された点への接続容量がこの点でpの出現回数であり、各操作(i,j)に対して(iは奇数)、iからjへの連容量は、この2つの点におけるpの出現回数の小さい値であり、(i,j)に対するp除去操作の最大回数を表す.最大ストリームは、pを除いた操作が最も多く行える回数である.
次に、各aiが除去された後に、109−−−−√より大きい質量数が残る可能性があります.もう一度、ソースポイントからすべての下に奇数と表記された点への接続容量が1または0(このポイントの残りの値が1より大きい場合は1であり、そうでない場合は0)であり、すべての下に奇数と表記された点への接続容量が1または0(このポイントの残りの値が1より大きい場合は1であり、そうでない場合は0)であります.,各操作(i,j)(iが奇数)について,i,jの残りの値がいずれも1より大きい場合,iはj連容量が1であり,最大ストリームをもう一度走って答えを加えればよい.
コード#コード#

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXV 1000
#define MAXE 21000
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int,int> pr;

int S,T;
int n,m;
int a[MAXV];
pr opt[MAXV];

struct edge
{
    int u,v,cap,next;
}edges[MAXE*2];

int head[MAXV],nCount=0;

void AddEdge(int U,int V,int C)
{
    edges[++nCount].u=U;
    edges[nCount].v=V;
    edges[nCount].cap=C;
    edges[nCount].next=head[U];
    head[U]=nCount;
}

void add(int U,int V,int C)
{
    AddEdge(U,V,C);
    AddEdge(V,U,0);
}

int q[MAXE*2];
int layer[MAXV];
bool inX[MAXV],inY[MAXV];

bool CountLayer()
{
    memset(layer,-1,sizeof(layer));
    int h=0,t=1;
    q[h]=S;
    layer[S]=1;
    while(h<t)
    {
        int u=q[h++];
        for(int p=head[u];p!=-1;p=edges[p].next)
        {
            int v=edges[p].v;
            if(layer[v]==-1&&edges[p].cap)
            {
                layer[v]=layer[u]+1;
                q[t++]=v;
            }
        }
    }
    return layer[T]!=-1;
}

int DFS(int u,int flow)
{
    int used=0;
    if(u==T) return flow;
    for(int p=head[u];p!=-1;p=edges[p].next)
    {
        int v=edges[p].v;
        if(layer[v]==layer[u]+1&&edges[p].cap)
        {
            int tmp=DFS(v,min(flow-used,edges[p].cap));
            edges[p].cap-=tmp;
            edges[p^1].cap+=tmp;
            used+=tmp;
            if(used==flow) break;
        }
    }
    if(!used) layer[u]=-1;
    return used;
}

int Dinic()
{
    int maxflow=0;
    while(CountLayer())
        maxflow+=DFS(S,INF);
    return maxflow;
}

bool isPrime[31623];
int primes[100000],tot=0;

void getPrime()
{
    memset(isPrime,true,sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    for(int i=2;i<31623;i++)
    {
        if(!isPrime[i]) continue;
        primes[++tot]=i;
        for(int j=i+i;j<31623;j+=i)
            isPrime[j]=false;
    }
}

int cnt[MAXV]; //cnt[i]=a[i]   prime   

int solve(int prime)
{
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)
        while(a[i]%prime==0)
        {
            a[i]/=prime;
            cnt[i]++;
        }
    nCount=1;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        if(inX[i])
            add(S,i,cnt[i]);
        else
            add(i,T,cnt[i]);
    }
    for(int i=1;i<=m;i++)
        add(opt[i].first,opt[i].second,min(cnt[opt[i].first],cnt[opt[i].second]));
    return Dinic();
}

int main()
{
    int ans=0;
    getPrime();
    memset(head,-1,sizeof(head));
    S=MAXV-2,T=MAXV-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i&1) inX[i]=true;
        else inY[i]=true;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&opt[i].first,&opt[i].second);
        if(inX[opt[i].second])
            swap(opt[i].first,opt[i].second);
    }
    for(int i=1;i<=tot;i++)
        ans+=solve(primes[i]);
    memset(head,-1,sizeof(head));
    nCount=1;
    for(int i=1;i<=n;i++)
    {
        if(inX[i])
            add(S,i,1);
        else
            add(i,T,1);
    }
    for(int i=1;i<=m;i++)
        if(a[opt[i].first]==a[opt[i].second]&&a[opt[i].first]>1)
            add(opt[i].first,opt[i].second,1);
    ans+=Dinic();
    printf("%d
",ans);
    return 0;
}