静かで孤独な日記

のんびりたまに

AOJ 2600 Koto Distance

競プロ 
#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[200011],b[200011];

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>>w>>h;
  vector<pair<int,int> > okx,oky;
  for(int i=0;i<n;i++){
    int x,y,z;cin>>x>>y>>z;
    okx.push_back({x-z,x+z});
    oky.push_back({y-z,y+z});
  }
  for(int i=0;i<n;i++){
    if(okx[i].fi<0)okx[i].fi=0;
    if(okx[i].se>w)okx[i].se=w;
    a[2*okx[i].fi]++;
    a[2*okx[i].se+1]--;
  }
  for(int i=0;i<n;i++){
    if(oky[i].fi<0)oky[i].fi=0;
    if(oky[i].se>h)oky[i].se=h;
    b[2*oky[i].fi]++;
    b[2*oky[i].se+1]--;
  }
  for(int i=1;i<=2*w;i++){
    a[i]=a[i-1]+a[i];
  }
  for(int j=1;j<=2*h;j++){
    b[j]=b[j-1]+b[j];
  }
  bool flag1=1,flag2=1;
  for(int i=0;i<=2*w;i++){
    if(a[i]<=0)flag1=0;
  }
  for(int i=0;i<=2*h;i++){
    if(b[i]<=0)flag2=0;
  }
  if(flag1 || flag2)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 0からwまでの範囲を全て網羅されているかもしくは、0からhまでの範囲を全て網羅していたらYes
  • 反省することは、点と点の間の空間も配列として持っておくこと(点空間点空間点空間…みたいに)

AOJ 1167 ポロック予想

競プロ 
#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 int inf=100000000;
int n,m,h,w;
vector<int> a,b;
int dp[1000001],dp2[1000001];

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
  for(int i=1;i<200;i++){
    a.push_back(i*(i+1)*(i+2)/6);
    int temp=i*(i+1)*(i+2)/6;
    if(temp&1)b.push_back(temp);
  }
  for(int i=0;i<=1000000;i++)dp[i]=inf;
  dp[0]=0;
  for(int i=0;i<=1000000;i++){
    for(int j=0;j<(int)a.size();j++){
      if(i+a[j]<=1000000){
        dp[i+a[j]]=min(dp[i+a[j]],dp[i]+1);
      }
    }
  }
  for(int i=0;i<=1000000;i++)dp2[i]=inf;
  dp2[0]=0;
  for(int i=0;i<=1000000;i++){
    for(int j=0;j<(int)b.size();j++){
      if(i+b[j]<=1000000){
        dp2[i+b[j]]=min(dp2[i+b[j]],dp2[i]+1);
      }
    }
  }
  while(cin>>n,n){
    cout<<dp[n]<<" "<<dp2[n]<<endl;
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

個数制限なしナップザック問題とおんなじ感じになった。

ABC038-D プレゼント

競プロ 
#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;

class Bit{
public:
    //tbl[1]...tbl[n]
    explicit Bit(int n):size(static_cast<unsigned int>(n)){//1-indexed
        tbl.resize(size+10,0);
    }
    
    //一点のみの更新
    void add(int a,ll w){//tbl[a]+=w , 1-indexed , 1-indexed!!!!!!!!!!!!!!!
        for(int i=a;i<=size;i+=i&-i)tbl[i]=max(tbl[i],w);
    }

    ll sum(int a){//v[1]+...+v[a] , 1-indexed ,1-indexed!!!!!!!!!!!!!
        ll ret=0;
        if(a==0)return 0;
        for(int i=a;i>0;i-=i&-i){
            ret=max(ret,tbl[i]);
        }
        return ret;
    }

    int lower_bound(ll w){
        if(w<=0)return 0;
        int x=0;
        int k=1;
        while(true){
            if(k*2>size){
                break;
            }
            k*=2;
        }
        for(k;k>0;k/=2){
            if(x+k<=size && tbl[x+k]<w){
                w-=tbl[x+k];
                x+=k;
            }
        }
        return x+1;//1-indexed , 1-indexed!!!!!!!!!!!!
    }
private:
    unsigned int size;
    vector<ll> tbl;
};

int n,m,h,w;
vector<pair<int,int> > v;
int dp[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>>n;
  for(int i=0;i<n;i++){
    int h,w;cin>>h>>w;
    v.push_back({h,-w});
  }
  sort(v.begin(),v.end());
  Bit bit(100001);
  for(int i=0;i<n;i++){
    dp[i]=bit.sum(-v[i].se-1)+1;
    bit.add(-v[i].se,dp[i]);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    ans=max(ans,dp[i]);
  }
  cout<<ans<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • ソートするは良いけど、そこから思いつかなかった。
  • hが同じ時wを降順にするの、おぉ！ってなった
  • bitのライブラリ作ってあったから、その場で作り変えて実装させることができた。
  • ライブラリがあると本当に便利よねー
  • w[i]より小さい最大のdpの大きさ、、、、そんな考え方は出来なかった。
  • 未来の自分に向けて言いますが、あなたはおそらくこの問題をいつか復習する際また同じようなところで引っかかってこのブログのページに帰ってくるでしょう。

ABC041-D 徒競走

競プロ 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,h,w;
ll dp[(1<<20)];
vector<int> v[20];

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;x--;y--;
        v[y].push_back(x);
    }
    dp[0]=1;
    for(int i=0;i<(1<<(n+1));i++){
        if(dp[i]==0)continue;
        for(int bit=0;bit<n;bit++){
            if(i&(1<<bit))continue;
            else{
                bool flag=1;
                for(int j=0;j<(int)v[bit].size();j++){
                    if(i&(1<<v[bit][j]))continue;
                    else flag=0;
                }
                if(flag)dp[i|(1<<bit)]+=dp[i];
            }
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}
  • どうやってやるのかなーって考えてる時に bitdpするっていう選択肢を考えなかったのが辛い。
  • 一瞬解説をみて bitdpだとわかったので、それからは自分で考えてやった。
  • k- bit目が0なら k+1番のウサギはまだゴールしてない、1ならゴールしてると考えてやる。
  • 先にゴールしていてほしいウサギが全部ゴールしているなら、着目しているウサギもゴールさせて良い。
  • そんな感じで最後は全員ゴールした状態の通り数なので、全ての bitが1のdp配列を見れば良い。
  • 制約に16があったら bitdpを疑おうね自分！！！！

ABC045 D すぬけ君の塗り絵

競プロ 
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
ll n,m,h,w;
string s;
map<pair<int,int>,ll> mp;
int x[100001],y[100001];
ll ans[10];

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<n;i++){
    cin>>y[i]>>x[i];
    x[i]--;y[i]--;
    for(int j=-2;j<=0;j++){
      for(int k=-2;k<=0;k++){
        if(y[i]+j<0 || y[i]+j+2>=h)continue;
        if(x[i]+k<0 || x[i]+k+2>=w)continue;
        mp[make_pair(y[i]+j,x[i]+k)]++;
      }
    }
  }
  for(auto ite=mp.begin();ite!=mp.end();ite++){
    //auto temp=ite->fi;
    //int temp2=ite->se;
    //print((temp.fi),(temp.se),temp2);
    ans[ite->se]++;
  }
  ans[0]=(w-2)*(h-2)-(int)mp.size();
  println__(ans,ans+10);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 塗られた付近のデータだけ保存しとけば、残りは0個なのでね。

ABC036-D 塗り絵

競プロ 
const ll MOD=(ll)1e9+7;
const ll inf=(ll)1e14;
int n,m,h,w;
vector<int> v[100001];
ll f[100001],g[100001];
bool fpast[100001],gpast[100001];
ll Rank[100001];
int r=0;

void dfs(int now){
  Rank[now]=r;
  r++;
  for(int i=0;i<(int)v[now].size();i++){
    if(Rank[v[now][i]]!=inf)continue;
    dfs(v[now][i]);
  }
}

int memo(int now,int color){
  if(color==0){
    if(fpast[now])return f[now];
    else {
      f[now]=memo(now,1);
      ll temp=1;
      for(int i=0;i<(int)v[now].size();i++){
        if(Rank[v[now][i]]<Rank[now])continue;
        temp=((temp%MOD)*(memo(v[now][i],1)%MOD))%MOD;
      }
      f[now]=(temp+f[now])%MOD;
      fpast[now]=1;
      return f[now];
    }
  }else{
    if(gpast[now])return g[now];
    else{
      ll temp=1;
      for(int i=0;i<(int)v[now].size();i++){
        if(Rank[v[now][i]]<Rank[now])continue;
        temp=(temp%MOD*memo(v[now][i],0)%MOD)%MOD;
      }
      g[now]=temp;
      gpast[now]=1;
      return g[now];
    }
  }
}

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;
  for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;
    a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for(int i=0;i<n;i++)Rank[i]=inf;
  dfs(0);
  print(memo(0,0));
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • メモ化再帰なのはわかったけど、漸化式思いつかなかったなー
  • こういうのって蟻本のってたっけ？

ABC061 D Score Attack

競プロ 
using namespace std;
//const ll MOD=(ll)1e9+7;
const ll inf=(ll)1e15;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
ll d[1001];
vector<pair<int,ll> > v[1001];
bool used[1001];

void dfs(int now){
  used[now]=1;
  for(int i=0;i<(int)v[now].size();i++){
    if(!used[v[now][i].fi])dfs(v[now][i].fi);
  }
}

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<m;i++){
    int from,to;
    ll cost;
    cin>>from>>to>>cost;
    from--;to--;
    v[from].push_back({to,-cost});
  }
  for(int i=0;i<n;i++){
    d[i]=inf;
  }
  d[0]=0;
  ll temp=0;
  for(int i=0;i<=m+10;i++){
    for(int j=0;j<n;j++){
      int now=j;
      if(d[now]==inf)continue;
      for(int k=0;k<(int)v[now].size();k++){
        if(d[now]+v[now][k].se>=d[v[now][k].fi])continue;
        d[v[now][k].fi]=d[now]+v[now][k].se;
      }
    }
    if(i==m)temp=d[n-1];
  }
  bool circle=0;
  if(temp!=d[n-1])circle=1;
  if(circle){
    print("inf");
  }else{
    print(-d[n-1]);
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 閉路があるだけじゃあ得点を無限に増やせる理由にならないことに気づきたい。
  • これは多めにベルマンフォードで回して、ゴールの距離が更に近づいたかどうかで判定ができる。