beet's soil

競プロのことなど

AtCoder Regular Contest 071

229th 1957 -> 1944 (-13)
CDEの三完。レートの減少が止まらない。

【C - 怪文書 / Dubious Document】

n個の文字列が与えられる。
与えられた文字列から任意の数の文字を任意の順番で並べて新しい文字列を作る。
どの文字列が与えられたとしても作れる文字列のうち、最長のものを求める。
最長のものが複数ある場合は辞書順最小のものを求める。

それぞれの文字列について、a-zまで数えてmin取ってa-zの順番で繋げればいい。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  int x[26]={};
  for(int i=0;i<(int)s[0].size();i++)
    x[s[0][i]-'a']++;
  
  for(int i=0;i<n;i++){
    int y[26]={};
    for(int j=0;j<(int)s[i].size();j++)
      y[s[i][j]-'a']++;
    for(int j=0;j<26;j++) x[j]=min(x[j],y[j]);
  }
  string ans;
  for(int i=0;i<26;i++){
    for(int j=0;j<x[i];j++){
      ans+=(char)('a'+i);
    }
  }
  cout<<ans<<endl;
  return 0;
}
【D - 井井井 / ###】

N本のy軸に平行な直線とM本のx軸に平行な直線が与えられる。
長方形と考えられる全ての面積の和をMOD1e9+7で求める。

上から0番目、右からi番目の長方形が数えられる回数は、
( (i+1)*(n-(i+1))*(m-1) )%MOD回になる。
(右上の頂点の候補の数×左下の頂点の候補の数)
これにそれぞれの幅をかけて0番目の高さをかけると0段目の面積Sがわかる。
i段目の面積はS/( (0番目の高さ)*(m-1) )*( (i+1)*(m-(i+1))*(i番目の高さ) )で求められる。
(組み合わせの数を考えるとそうなる。)
よってO(N+M)で解ける。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007

int extgcd(int a,int b,int& x,int& y){
  int d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
int mod_inverse(int a,int m){
  int x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}

signed main(){
  int n,m;
  cin>>n>>m;
  int x[n],y[m];
  for(int i=0;i<n;i++) cin>>x[i];
  for(int i=0;i<m;i++) cin>>y[i];
  int ans=0;
  int t[n];
  for(int i=0;i<n-1;i++) t[i]=((i+1)*(n-(i+1))*(m-1))%MOD;
  for(int i=0;i<n-1;i++) (t[i]*=x[i+1]-x[i])%=MOD;
  int tmp=0;
  for(int i=0;i<n-1;i++) (tmp+=t[i])%=MOD;
  (tmp*=mod_inverse(m-1,MOD))%=MOD;
  for(int i=0;i<m-1;i++){
    int res=tmp;
    (res*=(i+1))%=MOD;
    (res*=(m-(i+1)))%=MOD;
    (res*=(y[i+1]-y[i]))%=MOD;
    (ans+=res)%=MOD;
  }
  cout<<ans<<endl;
  return 0;
}
【E - TrBBnsformBBtion】

'A'と'B'からなる文字列S,Tが与えられる。
ある文字列について、以下の4つの操作を任意の回数行うことができる。
ある'A'を"BB"と置き換える。
ある'B'を"AA"と置き換える。
ある"AAA"を取り除く。
ある"BBB"を取り除く。
この条件のもと、以下のQ個のクエリに答える。
Sのaからb文字目までを4つの操作によってTのcからd文字目までに一致させることができるかを判定する。

A->BB->AAB->AAAA->A->BB->AAB->ABBB->ABAAAA->ABA->AAAA->A
B->AA->BBA->BBBB->B->AA->BBA->BAAA->BABBBB->BAB->BBBB->B
のように考えると全ての操作は可逆であることがわかる。
また、任意の文字列について1文字以下に変化させることができることもわかる。
よってダブリングによって1クエリあたりO(log|S|+log|T|)、全体でO(Q(log|S|+log|T|))で解ける。
(mod 3を考えるとより簡単に解ける。)

#include<bits/stdc++.h>
using namespace std;
#define int long long
string calc(string s){

  
  //cout<<s<<":";

  while(1){
    string t=s;
    int k;
    
    if((k=s.find("AAA"))!=-1) s.erase(k,3);
    if((k=s.find("BBB"))!=-1) s.erase(k,3);
    if((k=s.find("AB"))!=-1) s.erase(k,2);
    if((k=s.find("BA"))!=-1) s.erase(k,2);
    
    if((k=s.find("AA"))!=-1){
      s.erase(k,1);
      s[k]='B';
    }
    if((k=s.find("BB"))!=-1){
      s.erase(k,1);
      s[k]='A';
    }
    if(s==t) break;
  }
  
  //cout<<s<<endl;
  
  return s;
}
signed main(){
  string s,t;
  int q;
  cin>>s>>t>>q;
  int a[q],b[q],c[q],d[q];
  for(int i=0;i<q;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
  int n=s.size(),m=t.size();
  string ds[20][n];
  for(int i=0;i<n;i++) ds[0][i]=s[i];
  int tmp=1;
  for(int i=1;i<20;i++){
    for(int j=0;j<=n-tmp;j++){
      //cout<<i<<"/"<<j;
      ds[i][j]=calc(ds[i-1][j]+ds[i-1][j+tmp]);
    }
    tmp*=2;
    if(tmp>n) break;
  }
  string dt[20][m];
  for(int i=0;i<m;i++) dt[0][i]=t[i];
  tmp=1;
  for(int i=1;i<20;i++){
    for(int j=0;j<=m-tmp;j++){
      //cout<<i<<"/"<<j;
      dt[i][j]=calc(dt[i-1][j]+dt[i-1][j+tmp]);
    }
    tmp*=2;
    if(tmp>m) break;
  }
  int p[20];
  p[0]=1;
  for(int i=0;i<19;i++) p[i+1]=p[i]*2;

  //cout<<endl<<endl;
  for(int i=0;i<q;i++){
    a[i]--;b[i]--;c[i]--;d[i]--;
    string x,y;
    int e=b[i]-a[i]+1,f=a[i];
    for(int j=18;j>=0;j--){
      if((e>>j)&1){
	//cout<<j<<" "<<f<<" "<<ds[j][f]<<endl;
	//cout<<ds[j][f]<<endl;
	x=calc(x+ds[j][f]);
	f+=p[j];
      }
      //cout<<f<<"-";
      //cout<<x<<endl;
    }
    //cout<<endl;
    int g=d[i]-c[i]+1,h=c[i];
    for(int j=18;j>=0;j--){
      if((g>>j)&1){
	//cout<<j<<" "<<h<<" "<<dt[j][h]<<endl;
	y=calc(y+dt[j][h]);
	h+=p[j];
      }
      //cout<<h<<"-";
      //cout<<y<<endl;
    }
    //cout<<endl;
    //cout<<x<<":"<<y<<endl;
    cout<<(x==y?"YES":"NO")<<endl;
  }
  return 0;
}
【F - Infinite Sequence】

各要素が1-nからなる無限長の数列aのうち、次の二つの条件を満たしているものの個数を求める。
1 第n項から先は全て同じ数である。
2 どのiに対しても、a_iの後のi項は全て同じ数である。

DPと累積和で解ける。
0文字は1通り、1文字はn通りである。
2文字以上の時は{1,(k-1)文字}
または{x,1,1,...,(k-x+1)文字}
または{x,y,y,y,...}
または{x,1,1,1,...}になる。
これを適宜累積和を求めながらDPすればいい。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
int dp[1111111],su[1111111];

signed main(){
  int n;
  cin>>n;
  dp[0]=1;dp[1]=n;
  su[0]=1;su[1]=n+1;
  for(int i=2;i<=n;i++){
    dp[i]=(dp[i-1]+(i>=3?su[i-3]:0LL)+(n-1)*(n-1)+(n-i+1))%MOD;
    su[i]=(su[i-1]+dp[i])%MOD;
    //cout<<dp[i]<<endl;
  }
  cout<<dp[n]<<endl;
  return 0;
}