静かで孤独な日記

のんびりたまに

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;
}

AOJ 2610 Fast Division - ヘクトのメモ

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

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;
}
  • 賢い方法とか簡潔に書く方法とか全く思いつかなかったから、とにかくゴリゴリ書いた。
  • 誰かスマートな方法教えてくりー

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 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を疑おうね自分！！！！