AtCoder Beginner Contest 268
https://atcoder.jp/contests/abc268
結果
A - Five Integers:AC(2:51)
B - Prefix?:AC(9:49)
C - Chinese Restaurant:提出無し
D - Unique Username:提出無し
A - Five Integers
整数が5つ与えられ、そこに何種類の整数があるかを求める問題
自分の回答
int main() {
int N;
set<int> A;
for(int i = 0; i < 5; i++){
cin >> N;
A.insert(N);
}
printf("%d\n", A.size());
}
要素の種類ならばsetに全て入れてその個数を出力
公式解説
ifによる初歩的な方法だったため省略
B - Prefix?
文字列$${S,T}$$が与えられ、$${T}$$の先頭に$${S}$$が含まれているかを判定する問題
自分の回答
int main() {
string S, T;
cin >> S >> T;
if(S.size() > T.size()){
printf("No\n");
return 0;
}
for(int i = 0; i < S.size(); i++){
if(S[i] != T[i]){
printf("No\n");
return 0;
}
}
printf("Yes\n");
}
まず$${S}$$の文字数>$${T}$$の文字数ならば条件を満たさず、先の処理に支障をきたすためNoを出力して終了
後は$${S}$$と$${T}$$を1文字目から$${S}$$の最後まで比較して違う文字が存在するならNoを出力して終了、最後まで行ったらYesを出力
公式解説
自分の回答と同じなため省略
C - Chinese Restaurant
長くなるため省略
自分の回答
いい方法が思いつかなかったため愚直に全て調べる方法で書いてみたがサンプルすら通らなかった
ちゃんと書けてたとしても時間内に終わらなそうではある
公式解説
int main() {
int N;
cin>>N;
vector<int> p(N);
for(int i=0;i<N;i++)cin>>p[i];
vector<int> cnt(N,0);
for(int i=0;i<N;i++){
for(int j=0;j<3;j++){
cnt[(p[i]-1-i+j+N)%N]++;
}
}
int ans = 0;
for(int i=0;i<N;i++)ans = max(ans,cnt[i]);
cout<<ans<<endl;
return 0;
}
https://atcoder.jp/contests/abc268/editorial/4776より
そうか初期状態から何回操作すれば喜ぶ人の位置に移動させられるかを挙げれば最頻値の回数が答えになるのか
なるほど
D - Unique Username
$${N}$$個の文字列$${S_{1},S_{2},…,S_{N}}$$を任意の順番で並べ、その間に1つ以上の_を入れて連結した長さ3以上16以下の文字列のうち、$${M}$$個の文字列$${T_{1},T_{2},…,T_{M}}$$と一致しない文字列を求める問題
自分の回答
Sの並べ替えはnext_permutationで総当たりできるとして、_の個数をどうするかがが前に使えそうなものを見たような気がしたけど思い出せなかった
あと書けたとしても時間内に終わるか若干怪しい
公式解説
void dfs(int cur,vector<string> &S,vector<string> &T,int remain,string ans){
if(remain<0)return;
if(cur == S.size()){
if(ans.size()>=3&&!binary_search(T.begin(),T.end(),ans)){
cout<<ans<<endl;
exit(0);
}
return;
}
if(ans.size()>0 && ans.back()!='_'){
dfs(cur,S,T,remain,ans + "_");
}
else{
dfs(cur+1,S,T,remain,ans + S[cur]);
if(ans.size()>0)dfs(cur,S,T,remain-1,ans + "_");
}
}
int main() {
int N,M;
cin>>N>>M;
vector<string> S(N);
for(int i=0;i<N;i++)cin>>S[i];
sort(S.begin(),S.end());
vector<string> T(M);
for(int i=0;i<M;i++)cin>>T[i];
sort(T.begin(),T.end());
int remain = 16;
for(int i=0;i<N;i++)remain -= S[i].size();
remain -= N-1;
do{
dfs(0,S,T,remain,"");
}
while(next_permutation(S.begin(),S.end()));
cout<<-1<<endl;
return 0;
}
https://atcoder.jp/contests/abc268/editorial/4785より
curがSを何個使ったか、remainが_をあと何個使えるか、ansが生成された文字列で
ansの長さが0以上(これは初動のためかな) かつ ansの最後の文字が_でないなら ansに_をつけて再帰
そうでないなら ansにS[cur]をつけてcur+1して再帰、さらにansの長さが0以上ならば _をつけてremain-1して再帰
remainが0になったらreturn
![](https://assets.st-note.com/img/1662995322896-uekiykw58L.png)
そして
curがS.size()と等しくなったら、すなわちSの要素を全て使ったら
ansの長さが3以上かつTにそれが存在しなかったらansを出力してexit
そうでないならreturn
この関数によってSの並び順でできうる全てのパターンを作れるのか
そしてdo-whileでnext_permutationすることでSの並び順も総当たりできる
再帰だが帰ってくるわけではなく最深部が目的地なわけね
再帰関数にそういう使い方もあるのか
なるほど
この記事が気に入ったらサポートをしてみませんか?