2018-03-27

AOJ 2608 Minus One

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
const int inf=(int)1e9;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
int s,t;
//Shortest_Path
//グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです
class shortest_path{
public:
    
    //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください
    explicit shortest_path(int n):vertex(n),INF((ll)1e14){
        v1.resize(static_cast<unsigned long>(vertex));
    }
    
    //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください
    shortest_path(int n,ll inf):vertex(n),INF(inf){
        v2.resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++){
            for(int j=0;j<vertex;j++){
                v2[i][j]=INF;
            }
        }
        for(int i=0;i<vertex;i++)v2[i][i]=0;
    }
    
    //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge(int from,int to,ll cost){
        v1[from].push_back({to,cost});
    }
    
    //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge_(int from,int to,ll cost){//warshall_floyd
        v2[from][to]=cost;
    }
    
    //Dijkstra法です
    //各頂点への距離が格納されたvector<ll>が求まります
    //負のコストの辺がある場合は使えません
    //start地点の頂点番号を引数に入れてください
    vector<ll> dijkstra(unsigned int start){
        vector<ll> d(static_cast<unsigned long>(vertex),INF);
        priority_queue<pair<ll,int> > q;
        d[start]=0;
        q.push({0,start});
        while(!q.empty()){
            int now=q.top().se;
            ll now_cost=-q.top().fi;
            q.pop();
            if(d[now]<now_cost)continue;
            for (auto &i : v1[now]) {
                if(d[i.fi]>now_cost+ i.se){
                    d[i.fi]=now_cost+ i.se;
                    q.push({-d[i.fi], i.fi});
                }
            }
        }
        return d;
    }
    
    //Warshall_Floyd法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    tuple<vector<vector<ll> >,bool> warshall_floyd(){
        for(int k=0;k<vertex;k++){
            for(int i=0;i<vertex;i++){
                if(v2[i][k]==INF)continue;
                for(int j=0;j<vertex;j++){
                    if(v2[k][j]==INF)continue;
                    v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]);
                }
            }
        }
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            if(v2[i][i]<0)is_negative_cycle=true;
        }
        return make_tuple(v2,is_negative_cycle);
    }

    //Bellman_Ford法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    //start地点の頂点番号を引数に入れてください
    tuple<vector<ll>,bool> bellman_ford(int start){
        vector<ll> d(static_cast<unsigned long>(vertex),INF);
        d[start]=0;
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            bool update= false;
            for(int j=0;j<vertex;j++){
                if(d[j]==INF)continue;
                for(int k=0;k<(int)v1[j].size();k++){
                    if(d[v1[j][k].fi]>d[j]+v1[j][k].se){
                        d[v1[j][k].fi]=d[j]+v1[j][k].se;
                        update= true;
                    }
                }
            }
            if(i==vertex-1 && update)is_negative_cycle=true;
            else if(!update)break;
        }
        return make_tuple(d,is_negative_cycle);
    }
private:
    ll INF;
    int vertex;
    vector<vector<pair<int,ll> > > v1;
    vector<vector<ll> > v2;
};
//tuple tp<int,int,int> -> int a=get<0>(tp),b=get<1>(tp),c=get<2>(tp)


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>m>>s>>t;
  s--;t--;
  shortest_path sp(n);
  for(int i=0;i<m;i++){
    int a,b;cin>>a>>b;
    a--;b--;
    sp.add_edge(a,b,1);
    sp.add_edge(b,a,1);
  }
  vector<ll> d=sp.dijkstra(s);
  vector<ll> d2=sp.dijkstra(t);
  int st=d[t];
  if(st==1){
    cout<<0<<endl;
  }else{
    int tmp=st-2;
    sort(d2.begin(),d2.end());
    sort(d.begin(),d.end());
    ll ans=0;
    for(int i=0;i<=tmp;i++){
      ll a=upper_bound(d2.begin(),d2.end(),tmp-i)-lower_bound(d2.begin(),d2.end(),tmp-i);
      ll b=upper_bound(d.begin(),d.end(),i)-lower_bound(d.begin(),d.end(),i);
      ans+=a*b;
      //cout<<ans<<endl;
    }
    cout<<ans<<endl;
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

sからある頂点pまでの最短距離をx、ある頂点qからtまでの最短距離をyとする。
また、sからtまでの最短距離をs_tとすると、求めるものはx+y=s_t-2のものの個数。

これはsが始点のdijkstra、tが始点のdijkstraをやっておいて、各頂点までの距離が昇順になるようソートした後、xの値で全探索する。
そうするとy=s_t-2-xとなるyの個数を二分探索で求められる。
また、sからxが最短距離となるような頂点の数も二分探索で求められるので、それぞれの個数を掛けたものの和が答えになります。
(わかりにくいですね)(説明が下手)

2018-03-24

AOJ 2426 Treasure Hunt

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
vector<int> x,y,xx,yy;
int imos[5011][5011];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>m;
  for(int i=0;i<n;i++){
    int a,b;cin>>a>>b;
    xx.push_back(a);
    x.push_back(a);
    yy.push_back(b);
    y.push_back(b);
  }
  x.push_back(-1000000001);
  y.push_back(-1000000001);
  x.push_back(1000000001);
  y.push_back(1000000001);
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  x.erase(unique(x.begin(),x.end()),x.end());
  y.erase(unique(y.begin(),y.end()),y.end());
  for(int i=0;i<n;i++){
    xx[i]=lower_bound(x.begin(),x.end(),xx[i])-x.begin();
    yy[i]=lower_bound(y.begin(),y.end(),yy[i])-y.begin();
  }
  h=(int)y.size();
  w=(int)x.size();
  for(int i=0;i<n;i++){
    imos[yy[i]][xx[i]]++;
  }
  for(int i=0;i<h;i++)for(int j=1;j<w;j++)imos[i][j]+=imos[i][j-1];
  for(int i=1;i<h;i++)for(int j=0;j<w;j++)imos[i][j]+=imos[i-1][j];
  for(int i=0;i<m;i++){
    int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
    auto xa=lower_bound(x.begin(),x.end(),x1);
    if(*xa>=x1)xa--;
    auto xb=lower_bound(x.begin(),x.end(),x2);
    if(*xb>x2)xb--;
    auto ya=lower_bound(y.begin(),y.end(),y1);
    if(*ya>=y1)ya--;
    auto yb=lower_bound(y.begin(),y.end(),y2);
    if(*yb>y2)yb--;
    x1=xa-x.begin();x2=xb-x.begin();y1=ya-y.begin();y2=yb-y.begin();
    cout<<imos[y2][x2]-imos[y2][x1]-imos[y1][x2]+imos[y1][x1]<<endl;
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

座標圧縮を初めてやった気がしたぉ。
面白いなこれ。

2018-03-23

AOJ 2607 Invest Master

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
int a[11][11];
int dp[11][100001];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>w>>h>>n;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<h;i++)for(int j=0;j<100001;j++)dp[i][j]=-1;
  dp[0][0]=n;
  for(int i=0;i<h-1;i++){
    for(int j=0;j<100001;j++){
      if(dp[i][j]==-1)continue;
      for(int k=0;k<w;k++){
        int cont=1;
        while(dp[i][j]-cont*a[i][k]>=0){
          dp[i][j+cont*a[i+1][k]]=max(dp[i][j]-cont*a[i][k],dp[i][j+cont*a[i+1][k]]);
          dp[i+1][0]=max(dp[i+1][0],dp[i][j]-cont*a[i][k]+cont*a[i+1][k]);
          cont++;
        }
      }
      dp[i+1][0]=max(dp[i][j]+j,dp[i+1][0]);
    }
  }
  cout<<dp[h-1][0]<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

dp[何日目か][その次の日得られる利益の合計]=今日中に使える残りの金額
みたいな漸化式でやったらたまたま出来ました。
嬉しい。

2018-03-23

AOJ 2629 Manhattan

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
double d;

double check(double mid){
  double x=mid;
  double y=sqrt(d*d-x*x);
  return x+y;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>d;
  cout<<max<double>(d*sqrt(2),(double)((int)d+1))<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

うーん、なんか勘違いしていて解けなかった。
反省

2018-03-23

AOJ 2610 Fast Division

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n;
  if(n==0)cout<<1<<endl;
  else if(n==1)cout<<2<<endl;
  else if(n==2)cout<<1<<endl;
  else cout<<0<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

いや知らんがな。以外の感想がなかった。
フェルマーの小定理はmodの逆元とかで使ったことはあるけど、こうフェルマーの小定理が主役の問題は初めてだった。

AOJ 2610 Fast Division - ヘクトのメモ

この記事がとてもわかりやすくて助かった。

2018-03-23

AOJ 2232 Ennichi

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
int n,m,h,w;
char a[50][50];

bool check(){
  bool b[50][50];
  char c[50][50];
  for(int i=0;i<h;i++)for(int j=0;j<w;j++)c[i][j]=a[i][j];
  while(1){
    bool up=0;
    for(int i=0;i<h-1;i++){
      for(int j=0;j<w;j++){
        if(c[i][j]!='.' && c[i+1][j]=='.'){
          swap(c[i][j],c[i+1][j]);
          up=1;
        }
      }
    }
    if(!up)break;
  }
  while(1){
    bool update=0;
    for(int i=0;i<h;i++)for(int j=0;j<w;j++)b[i][j]=0;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        if(j+n>w)continue;
        if(c[i][j]=='.')continue;
        int nowcolor;
        bool flag=1;
        for(int k=0;k<n;k++){
          if(k==0){
            nowcolor=c[i][j+k]-'a';
            continue;
          }
          if(c[i][j+k]!=(char)('a'+nowcolor))flag=0;
        }
        if(flag){
          for(int k=0;k<n;k++){
            b[i][j+k]=1;
          }
        }
      }
    }
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        if(i+n>h)continue;
        if(c[i][j]=='.')continue;
        int nowcolor;
        bool flag=1;
        for(int k=0;k<n;k++){
          if(k==0){
            nowcolor=c[i+k][j]-'a';
            continue;
          }
          if(c[i+k][j]!=(char)('a'+nowcolor))flag=0;
        }
        if(flag){
          for(int k=0;k<n;k++){
            b[i+k][j]=1;
          }
        }
      }
    }
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        if(b[i][j]==1){
          c[i][j]='.';
          update=1;
        }
      }
    }
    if(!update)break;
    while(1){
      bool up=0;
      for(int i=0;i<h-1;i++){
        for(int j=0;j<w;j++){
          if(c[i][j]!='.' && c[i+1][j]=='.'){
            swap(c[i][j],c[i+1][j]);
            up=1;
          }
        }
      }
      if(!up)break;
    }
  }
  bool ok=1;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(c[i][j]!='.')ok=0;
    }
  }
  return ok;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>h>>w>>n;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w-1;j++){
      //if(a[i][j]!='.' && a[i][j+1]!='.'){
        swap(a[i][j],a[i][j+1]);
        if(check()){
          //cout<<i<<" "<<j<<endl;
          cout<<"YES"<<endl;
          exit(0);
        }
        swap(a[i][j],a[i][j+1]);
      //}
    }
  }
  cout<<"NO"<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

賢い方法とか簡潔に書く方法とか全く思いつかなかったから、とにかくゴリゴリ書いた。
誰かスマートな方法教えてくりー

2018-03-23

AOJ 2583 JAG-channel

競プロ

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  while(cin>>n,n){
    vector<string> s(n);
    for(int i=0;i<n;i++){
      cin>>s[i];
      if(i==0)continue;
      int j;
      for(j=0;s[i][j+1]=='.';j++);
      s[i][j]='+';
      for(int k=i-1;k>0;k--){
        if(s[k][j]=='.')s[k][j]='|';
        else break;
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<(int)s[i].size();j++){
        if(s[i][j]=='.')s[i][j]=' ';
      }
      cout<<s[i]<<endl;
    }
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

日本語や読めてなくてかなり時間がかかってしまった。。。

静かで孤独な日記

のんびりたまに

AOJ 2608 Minus One

AOJ 2426 Treasure Hunt

AOJ 2607 Invest Master

AOJ 2629 Manhattan

AOJ 2610 Fast Division

AOJ 2232 Ennichi

AOJ 2583 JAG-channel