# AnotherGori#002
# A - Prefix and Suffix(AGC006-A) (opens new window)
# 概要
長さの文字列とが存在する.
この時, 以下の条件を満たす文字列のうち, 最も短いものの長さを求めよ.
- 長さは以上
- 先頭文字が文字列に一致する
- 先頭文字が文字列に一致する
# 解法
文字列の後半文字と, 文字列の前半文字が同じになるように文字列を設定したい.
ここで, 制約がなので, で間に合う.
したがって, インデクスについて, 全探索をして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)
# 概要
(長さ, 文字列) = , が与えられる. ここで, 文字列とから生成される以下の条件を満たすような最短の文字列の長さを求めよ.
- の長さをとすると, はでもでも割り切れる.
- の文字目はの文字目と等しい.
- の文字目はの文字目と等しい.
ただし, そのような文字列が存在しない場合は,
-1
を出力せよ.
# 解法
題意では,
- の長さをとすると, はでもでも割り切れる.
最短
の文字列長を求めよ
と言われているため, の長さは, との最小公倍数(LCM)となることがわかる.
= である.
さて, その上で長さで文字列が成立するかを確認する.
題意より,
- の文字目はの文字目と等しい.
- の文字目はの文字目と等しい.
を満たすように設定すればいいことがわかるので, インデクスおよびで別々に全探索して, 条件を満たすか確認すればよい.
ただし, 文字列を愚直に作ろうとすると, 制約より非常に大きな数になる可能性があるため(の時),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つの正の整数列およびを求めよ.
# 解法
時間内に解けなかったので, Editorialに準拠する.
一般解を考える.
結論から言うと,
となるような数列とを構成し, 前から順にのように加算すれば良い.
そうすれば, 題意のを満たせる.
この時, a_iの値を定めれば, 自ずとの値も定まることがわかる.
(となるように設定する.)
ただし, およびの範囲は, は欲しいところである.
( 加算する数の範囲は, )
したがって, 以下のようにおよびを定める.
#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;
}
以上.
お疲れ様でした.