# AnotherGori#002

# A - Prefix and Suffix(AGC006-A) (opens new window)

# 概要

長さNNの文字列ssttが存在する.
この時, 以下の条件を満たす文字列のうち, 最も短いものの長さを求めよ.

  • 長さはNN以上
  • 先頭NN文字が文字列ssに一致する
  • 先頭NN文字が文字列ttに一致する

# 解法

文字列ssの後半ii文字と, 文字列ttの前半ii文字が同じになるように文字列を設定したい.
ここで, 制約が1N1001 \leq N \leq 100なので, O(N)O(N)で間に合う.
したがって, インデクスiiについて, 全探索をしてminを取ればよい.

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  string s,t;
  cin >> s >> t;
  
  int ans = 2 * n;
  for(int i=0; i<n; ++i){
    string s_substr = s.substr(n-1-i, i+1);
    string t_substr = t.substr(0, i+1);
    if (s_substr == t_substr){
      ans = min(ans, 2*n-i-1);
    }
  }
  cout << ans << endl;
  return 0;
}

# B - Two Abbreviations(AGC028-A) (opens new window)

# 概要

(長さ, 文字列) = (N,S)(N, S), (M,T)(M, T)が与えられる. ここで, 文字列SSTTから生成される以下の条件を満たすような最短の文字列XXの長さを求めよ.

  • XXの長さをLLとすると, LLNNでもMMでも割り切れる.
  • XX(siL/N)(si * L / N)文字目はSSsisi文字目と等しい.
  • XX(tiL/M)(ti * L / M)文字目はTTtiti文字目と等しい. ただし, そのような文字列が存在しない場合は, -1を出力せよ.

# 解法

題意では,

  • XXの長さをLLとすると, LLNNでもMMでも割り切れる.
  • 最短の文字列長を求めよ

と言われているため, XXの長さLLは, NNMMの最小公倍数(LCM)となることがわかる.

LCM(N,M)LCM(N, M) = N×M÷GCD(N,M)N \times M \div GCD(N, M)である.

さて, その上で長さL=LCM(N,M)L = LCM(N, M)で文字列XXが成立するかを確認する.
題意より,

  • XXsiL/Nsi * L / N文字目はSSsisi文字目と等しい.
  • XXtiL/Mti * L / M文字目はTTtiti文字目と等しい. を満たすように設定すればいいことがわかるので, インデクスsisiおよびtitiで別々に全探索して, 条件を満たすか確認すればよい.
    ただし, 文字列XXを愚直に作ろうとすると, 制約より非常に大きな数になる可能性があるため(GCD(N,M)=1GCD(N, M) = 1の時), std::mapを使って実装する(文字列長が長くなるので, int64_tlong longを使う必要がある).
#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

int gcd(int a,int b){
  return (a%b==0?b:gcd(b,a%b));
}

signed main(){
  int n,m;    cin >> n >> m;
  string s,t; cin >> s >> t;
  
  int l = n*m/gcd(n,m);
  
  map<int,int> mp;
  for(int si=0; si<n; ++si){
    mp[si*l/n] = s[si];
  }
  for(int ti=0; ti<m; ++ti){
    // 上のforループで初期化されていないものは, なんでもok
    if(mp[ti*l/m] == 0) continue;
    // 同じ部分がsとかぶった時はNG
    // (文字列長Lをk倍したとしても, 結局は同じ部分が被るのでやはりNG)
    if(mp[ti*l/m] != t[ti]) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << l << endl;
  return 0;
}

# C - Construct Sequences(AGC007-B) (opens new window)

# 概要

集合{$1,2,...,N2,...,N}の要素で構成される数列ppが与えられる.
この時, 以下の条件を全て満たす2つの正の整数列a1,a2,...,ana_1,a_2,...,a_nおよびb1,b2,...,bnb_1,b_2,...,b_nを求めよ.

  • a1<a2<...<ana_1 < a_2 < ... < a_n
  • b1>b2>...>bnb_1 > b_2 > ... > b_n
  • ap1+bp1<ap2+bp2<...<apn+bpna_{p_1}+b_{p_1} < a_{p_2}+b{p_2} < ... < a_{p_n}+b{p_n}

# 解法

時間内に解けなかったので, Editorialに準拠する.

一般解を考える.
結論から言うと,
ap1+bp1=ap2+bp2=...=apn+bpna_{p_1}+b_{p_1} = a_{p_2}+b{p_2} = ... = a_{p_n}+b{p_n}
となるような数列aia_ibib_iを構成し, 前から順に+0,+1,...,+(n1)+0, +1, ..., +(n-1)のように加算すれば良い.
そうすれば, 題意のap1+bp1<ap2+bp2<...<apn+bpna_{p_1}+b_{p_1} < a_{p_2}+b{p_2} < ... < a_{p_n}+b{p_n}を満たせる.

この時, a_iの値を定めれば, 自ずとbib_iの値も定まることがわかる.
(ap1+bp1=ap2+bp2=...=apn+bpn\because a_{p_1}+b_{p_1} = a_{p_2}+b{p_2} = ... = a_{p_n}+b{p_n}となるように設定する.)
ただし, aia_iおよびbib_iの範囲は, NNは欲しいところである.
(\because 加算する数の範囲は, 0Nn10 \leq N \leq n-1)

したがって, 以下のようにaia_iおよびbib_iを定める.

  • rpi=i(0in1)r_{p_i} = i (0 \leq i \leq n-1)
  • ai=Ni+1(0in1)a_i = N * i + 1(0 \leq i \leq n-1)
  • bi=N(Ni)+ri+1(0in1)b_i = N * (N-i) + r_i + 1 (0 \leq i \leq n-1)
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  vector<int> p(n);
  for(int pi=0; pi<n; ++pi) {
    cin>>p[pi];
    // 0-indexedに
    --p[pi];
  }
  
  vector<int> a(n), b(n),r(n);
  for(int pi=0; pi<n; ++pi){
    r[p[pi]] = pi;
  }
  for(int ai=0; ai<n; ++ai){
    a[ai] = n*ai + 1;
  }
  for(int bi=0; bi<n; ++bi){
    b[bi] = n*(n-bi) + r[bi] + 1;
  }
  
  for (int ai=0; ai<n; ++ai){
    cout << a[ai];
    if(ai<n-1) cout << " ";
    else cout << endl; 
  }
  for (int bi=0; bi<n; ++bi){
    cout << b[bi];
    if(bi<n-1) cout << " ";
    else cout << endl; 
  }
  
  return 0;
}

以上.
お疲れ様でした.

# 参考資料

Last Updated: 5ヶ月前