# AnotherGori#002

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

# 概要

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

長さは $N$ 以上
先頭 $N$ 文字が文字列 $s$ に一致する
先頭 $N$ 文字が文字列 $t$ に一致する

# 解法

文字列 $s$ の後半 $i$ 文字と, 文字列 $t$ の前半 $i$ 文字が同じになるように文字列を設定したい.
ここで, 制約が $1 \leq N \leq 100$ なので, $O(N)$ で間に合う.
したがって, インデクス $i$ について, 全探索をして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)$ , $(M, T)$ が与えられる. ここで, 文字列 $S$ と $T$ から生成される以下の条件を満たすような最短の文字列 $X$ の長さを求めよ.

$X$ の長さを $L$ とすると, $L$ は $N$ でも $M$ でも割り切れる.
$X$ の $(si * L / N)$ 文字目は $S$ の $si$ 文字目と等しい.
$X$ の $(ti * L / M)$ 文字目は $T$ の $ti$ 文字目と等しい. ただし, そのような文字列が存在しない場合は, -1を出力せよ.

# 解法

題意では,

$X$ の長さを $L$ とすると, $L$ は $N$ でも $M$ でも割り切れる.
最短の文字列長を求めよ

と言われているため, $X$ の長さ $L$ は, $N$ と $M$ の最小公倍数(LCM)となることがわかる.

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

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

$X$ の $si * L / N$ 文字目は $S$ の $si$ 文字目と等しい.
$X$ の $ti * L / M$ 文字目は $T$ の $ti$ 文字目と等しい. を満たすように設定すればいいことがわかるので, インデクス $si$ および $ti$ で別々に全探索して, 条件を満たすか確認すればよい.
ただし, 文字列 $X$ を愚直に作ろうとすると, 制約より非常に大きな数になる可能性があるため( $GCD(N, M) = 1$ の時), std::mapを使って実装する(文字列長が長くなるので, int64_tやlong 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,...,N$ }の要素で構成される数列 $p$ が与えられる.
この時, 以下の条件を全て満たす2つの正の整数列 $a_1,a_2,...,a_n$ および $b_1,b_2,...,b_n$ を求めよ.

$a_1 < a_2 < ... < a_n$
$b_1 > b_2 > ... > b_n$
$a_{p_1}+b_{p_1} < a_{p_2}+b{p_2} < ... < a_{p_n}+b{p_n}$

# 解法

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

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

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

したがって, 以下のように $a_i$ および $b_i$ を定める.

$r_{p_i} = i (0 \leq i \leq n-1)$
$a_i = N * i + 1(0 \leq i \leq n-1)$
$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;
}

以上.
お疲れ様でした.

# AnotherGori#002

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

# 概要

# 解法

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

# 概要

# 解法

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

# 概要

# 解法

# 参考資料