静かで孤独な日記

のんびりたまに

ABC030-D へんてこ辞書

競プロ 
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
int n,a;
string k;
int b[100001];
int num[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>>a;a--;
  cin>>k;
  for(int i=0;i<n;i++){
    cin>>b[i];b[i]--;
  }
  if((int)k.size()<=7){
    ll h=stoi(k);
    int ans=a;
    for(int i=0;i<h;i++){
      ans=b[ans];
    }
    print(ans+1);
  }else{
    for(int i=0;i<n;i++){
      num[i]=-1;
    }
    int now=a;
    int t,circle;
    for(int i=0;;i++){
      if(num[now]!=-1){
        t=num[now];
        circle=i-t;
        break;
      }
      num[now]=i;
      now=b[now];
    }
    int h=0;
    for(int i=0;i<(int)k.size();i++){
      h=(h*10+(int)(k[i]-'0'))%circle;
    }
    h-=t;
    if(h<0){
      int temp=-h/circle;
      temp++;
      h+=circle*temp;
    }
    int ans=a;
    for(int i=0;i<t+h;i++){
      ans=b[ans];
    }
    print(ans+1);
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

  • 最初、ダブリングだーって思って提出したらWAで、なんでやって制約見たら卒倒した。
  • 閉路に入る前と後に分けるのが重要で、modとった後に閉路に入る前の分だけ引く。
  • これでマイナスだとダメなので正の数に直してあげましょう。

ABC031-D 語呂合わせ

競プロ 
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
int n,k;
string v[51],w[51];
int mojisuu[10];

bool check(){
  map<char,string> mp;
  for(int i=0;i<n;i++){
    int nowmojisuu=0;
    for(int j=0;j<(int)v[i].size();j++){
      nowmojisuu+=mojisuu[v[i][j]-'0'];
    }
    if(nowmojisuu!=(int)w[i].size())return 0;
    int start=0;
    for(int j=0;j<(int)v[i].size();j++){
      if(mp.count(v[i][j])){
        string temp="";
        for(int k=0;k<(int)mp[v[i][j]].size();k++)temp+=mp[v[i][j]][k];
        string temp2=w[i].substr(start,mojisuu[v[i][j]-'0']);
        if(temp!=temp2)return 0;
        else{
          start+=mojisuu[v[i][j]-'0'];
        }
        continue;
      }
      mp[v[i][j]]=w[i].substr(start,mojisuu[v[i][j]-'0']);
      start+=mojisuu[v[i][j]-'0'];
    }
  }
  for(int i=0;i<n;i++){
    string now="";
    for(int j=0;j<(int)v[i].size();j++){
      now+=mp[v[i][j]];
    }
    if(now!=w[i])return 0;
  }
  for(int i=0;i<k;i++){
    cout<<mp[(char)(i+'1')]<<"\n";
  }
  return 1;
}

void dfs(int nownum,int nowmojisuu){
  mojisuu[nownum]=nowmojisuu;
  if(nownum==k){
    if(check())exit(0);
  }else{
    for(int i=1;i<=3;i++){
      dfs(nownum+1,i);
    }
  }
}

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>>k>>n;
  for(int i=0;i<n;i++){
    cin>>v[i]>>w[i];
  }
  for(int i=1;i<=3;i++){
    dfs(1,i);
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • めっちゃめんどくさかった。。。

ABC027-D ロボット

競プロ 
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>>s;
  n=(int)s.size();
  int now=0;
  vector<int> v;
  for(int i=n-1;i>=0;i--){
    if(s[i]=='+'){
      now++;
    }else if(s[i]=='-'){
      now--;
    }else{
      v.push_back(now);
    }
  }
  sort(v.begin(),v.end());
  int ans=0;
  for(int i=0;i<(int)v.size();i++){
    if(i<(int)v.size()/2){
      ans+=-v[i];
    }else ans+=v[i];
  }
  print(ans);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 僕は入力される+と-にしか注目できませんでした。
  • 視点を変えて、Mに注目すると見えるんですね。

ABC026-D 高橋君ボール1号

競プロ 
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};
const double eps=1e-10;
int n,m,h,w;
string s;
double a,b,c;
const double PI=acos(-1.0);

bool check(double mid){
  double f_t=a*mid+b*sin(c*mid*PI);
  if(f_t>100+eps){
    return 1;
  }else return 0;
}

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>>a>>b>>c;
  double l=0,r;
  for(int i=1;;i++){
    if(a*(double)i+b*sin(c*(double)i*PI)>100+eps){
      r=i;
      l=i-1;
      break;
    }
  }
  for(int i=0;i<100;i++){
    double mid=(l+r)/2;
    if(check(mid)){
      r=mid;
    }else{
      l=mid;
    }
  }
  print(l);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • こんなのも二分探索でいけるんですね。

ARC092-D Two Sequences

競プロ 
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;
ll a[200001],b[200001];

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++){
    cin>>a[i];
  }
  for(int i=0;i<n;i++){
    cin>>b[i];
  }
  ll t=1;
  ll ans=0;
  for(int i=0;i<30;i++){
    if(i!=0)t*=2;
    vector<int> v1,v2;
    for(int j=0;j<n;j++){
      v1.push_back(a[j]%(2*t));
      v2.push_back(b[j]%(2*t));
    }
    sort(v2.begin(),v2.end());
    int res=0;
    for(int j=0;j<n;j++){
      int x=lower_bound(v2.begin(),v2.end(),t-v1[j])-v2.begin();
      int y=lower_bound(v2.begin(),v2.end(),2*t-v1[j])-v2.begin();
      int z=lower_bound(v2.begin(),v2.end(),3*t-v1[j])-v2.begin();
      res+=y-x;
      res+=n-z;
    }
    if(res&1){
      ans+=t;
    }
  }
  print(ans);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 解説動画見て実装
  • なんかむちゃくちゃ遅かった
  • k- bit目が1か0かが周期的であることに気づけなかった
  • xorを考えるときは各 bitごとに区切って考えるのが定石だそうです(ツイッターで誰かが言ってました)

ARC092-C 2D Plane 2N Points

競プロ 
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;
vector<pair<int,int> > aka,ao;
bool past[101];

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 a,b;cin>>a>>b;
    aka.push_back({a,b});
  }
  for(int i=0;i<n;i++){
    int a,b;cin>>a>>b;
    ao.push_back({a,b});
  }
  sort(ao.begin(),ao.end());
  int ans=0;
  for(int i=0;i<n;i++){
    int maxy=-1;
    int res=-1;
    for(int j=0;j<n;j++){
      if(past[j])continue;
      if(aka[j].fi<ao[i].fi && aka[j].se<ao[i].se){
        if(maxy<aka[j].se){
          res=j;
          maxy=aka[j].se;
        }
      }
    }
    if(res!=-1){
      past[res]=1;
      ans++;
    }
  }
  print(ans);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 赤の点は左下にあるほど貴重なので、青の点と友達にするのは取れる赤の点のうち最も下にあるもの。
  • これを最初に青のx座標でソートして行えば大丈夫。
  • x座標でソートしたら、もう赤のx座標のことは考えなくていいよね。

ABC058 井井井/###

競プロ
  • 以前解いた時と解法が全く違ったので記念に。
  • 前回は解説見て実装したからそれはそう。
  • そう思うと解説のような綺麗な解き方するのは中々難しい。。
#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cout<<#x<<"="<<x<<"\n"
typedef long long ll;
template<typename T>
void print_to(std::ostream &os,const char *,const char *tail,const T &fst){
  os<<fst<<tail;
}
template<typename Fst,typename... Rst>
void print_to(std::ostream &os,const char *del,const char *tail,const Fst &fst,const Rst &... rst){
  os<<fst<<del;
  print_to(os,del,tail,rst...);
}
template<typename Iter>
void print_to_(std::ostream &os,const char *del,const char *tail,Iter bgn,Iter end){
  for(Iter it=bgn;it!=end;){
    os<<*it;
    if(++it!=end)os<<del;
    else os<<tail;
  }
}
template<typename Fst,typename... Rst>
void println(const Fst &fst,const Rst &... rst){
  print_to(std::cout,"\n","\n",fst,rst...);
}
template<typename Fst,typename... Rst>
void print(const Fst &fst,const Rst &... rst){
  print_to(std::cout," ","\n",fst,rst...);
}
template<typename Iter>
void println_(Iter bgn,Iter end){
  print_to_(std::cout," ","\n",bgn,end);
}
using namespace std;
const ll MOD=(ll)1e9+7;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
ll x[100001],y[100001],sumy[100001],sumx[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>>m;
  for(int i=0;i<n;i++){
    cin>>x[i];
  }
  for(int i=0;i<m;i++){
    cin>>y[i];
  }
  for(int i=m-1;i>=0;i--){
    if(i==m-1){
      sumy[i]=y[i];
      continue;
    }
    sumy[i]=y[i]+sumy[i+1];
  }
  for(int i=n-1;i>=0;i--){
    if(i==n-1){
      sumx[i]=x[i];
      continue;
    }
    sumx[i]=x[i]+sumx[i+1];
  }
  ll sumyy=0;
  for(int i=0;i<m;i++){
    ll p=i;
    sumyy=(sumyy+MOD)%MOD+(sumy[p+1]+MOD)%MOD+-(((m-1-p)%MOD)*(y[p]%MOD)+MOD)%MOD;
    sumyy%=MOD;
    //print(sumyy);
  }
  ll sumxx=0;
  for(int i=0;i<n;i++){
    ll p=i;
    sumxx=(sumxx+MOD)%MOD+(sumx[p+1]+MOD)%MOD-(((n-1-p)%MOD)*(x[p]%MOD)+MOD)%MOD;
    sumxx%=MOD;
  }
  //show(sumxx);
  //show(sumyy);
  print((((sumxx+MOD)%MOD)*((sumyy+MOD)%MOD)+MOD)%MOD);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
    return 0;
}