いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

ABC029 C.Brute-force Attack

C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder
解きました
入力Nを受けてN文字でかつ"a","b","c"のみで構成される文字列を辞書順で出力せよという問題
ごり押しでも解けると思ったけど時間かけて綺麗に書けるかなって遠回りしたら綺麗に書けました

解法としては配列にabcを格納して順番に出していくだけ
出し方はループ回数に意識して一番下の文字は1回ごとに変化、二番目は3回ごと、三番目は9回ごと、n番目は3^(n-1)回ごとに文字列を変化できるようにした
これだとcの次はaに帰ってこれず配列の中身のない部分を参照してしまうので3ずつ引いていくことにした
メモリも計算量も最低限にできたのではないかなと思う

#include<iostream>
using namespace std;
#include<vector>

int main(){
	int n;
	cin>>n;
	
	vector<int> k(n+1,1);
	for(int i = 1;i<n+1;i++)k[i]=k[i-1]*3;
	
	vector<string> s(3);
	s[0]="a";
	s[1]="b";
	s[2]="c";
	
	for(int i = 0;i<k[n-1]*3;i++){
		for(int j = n-1;j>=0;j--){
			cout<<s[(i/k[j])-(3*(i/k[j+1]))];
		}
		cout << endl;
	}
	return 0;
}

Submission #1255977 - AtCoder Beginner Contest 029 | AtCoder