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

こんな感じかしら

そして
curがS.size()と等しくなったら、すなわちSの要素を全て使ったら
　ansの長さが3以上かつTにそれが存在しなかったらansを出力してexit
　そうでないならreturn

この関数によってSの並び順でできうる全てのパターンを作れるのか
そしてdo-whileでnext_permutationすることでSの並び順も総当たりできる

再帰だが帰ってくるわけではなく最深部が目的地なわけね
再帰関数にそういう使い方もあるのか

なるほど