AtCoder Beginner Contest 327
結果
A - ab : AC(2:07)
B - A^A : AC(6:28)
C - Number Place : AC(15:51)
D - Good Tuple Problem : AC(32:11)
E - Maximize Rating : 提出無し
A - ab
英小文字からなる長さ$${N}$$の文字列$${S}$$が与えられ、その中に「a」と「b」が隣接している箇所があるか判定する問題
自分の回答
int main(){
int N;
string S;
cin >> N >> S;
for(int i = 0; i < N - 1; i++){
if((S[i] == 'a' && S[i + 1] == 'b') || (S[i] == 'b' && S[i + 1] == 'a')){
printf("Yes\n");
return 0;
}
}
printf("No\n");
}そのまま
公式解説
省略
B - A^A
整数$${B}$$が与えられ、$${A^A=B}$$となる$${A}$$があるか、あるならばそれはいくつか求める問題
自分の回答
int main(){
int64_t B;
cin >> B;
for(int i = 1; i <= 15; i++){
int64_t A = 1;
for(int a = 0; a < i; a++){
A *= i;
}
if(A == B){
printf("%d\n", i);
return 0;
}
}
printf("-1\n");
}A=16でBの最大値を超えるから15まで総当たり
公式解説
省略
C - Number Place
$${9×9}$$のマス目全てに$${1}$$から$${9}$$の数字のいずれか一つが書かれているため、それが数独として成立しているか判定する問題
自分の回答
int main(){
vector<vector<int>> A(9, vector<int>(9));
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
cin >> A[i][j];
}
}
vector<vector<bool>> ic(9, vector<bool>(10, false)), jc(9, vector<bool>(10, false));
vector<vector<vector<bool>>> sq(3, vector<vector<bool>>(3, (vector<bool>(10, false))));
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(ic[i][A[i][j]]){
printf("No\n");
return 0;
}
else{
ic[i][A[i][j]] = true;
}
if(jc[j][A[i][j]]){
printf("No\n");
return 0;
}
else{
jc[j][A[i][j]] = true;
}
if(sq[i / 3][j / 3][A[i][j]]){
printf("No\n");
return 0;
}
else{
sq[i / 3][j / 3][A[i][j]] = true;
}
}
}
printf("Yes\n");
}縦、横、ブロックそれぞれでその数字が既出か見ていく
入力の段階でできるのと判定の部分まとめて短くはできるけど大きくは変わらないか
公式解説
省略
D - Good Tuple Problem
$${N}$$以下の正整数からなる長さ$${M}$$の数列の組$${(S,T)}$$が与えられ、$${0,1}$$からなる長さ$${N}$$の数列$${X}$$において$${X_{S_{i}} \neq X_{T_{i}}}$$が全ての$${i}$$において成り立つか判定する問題
自分の回答
int main(){
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for(int i = 0; i < M; i++){
cin >> A[i];
}
for(int i = 0; i < M; i++){
cin >> B[i];
}
vector<set<int>> G(N + 1);
for(int i = 0; i < M; i++){
G[A[i]].insert(B[i]);
G[B[i]].insert(A[i]);
}
vector<int> num(N + 1, 0);
for(int i = 1; i <= N; i++){
if(num[i] != 0){
continue;
}
queue<pair<int, int>> bfs;
bfs.push({i, 1});
num[i] = 1;
while(!bfs.empty()){
auto [now, n] = bfs.front();
bfs.pop();
for(int go : G[now]){
if(num[go] == n){
printf("No\n");
return 0;
}
if(num[go] == 0){
bfs.push({go, n * -1});
num[go] = n * -1;
}
}
}
}
printf("Yes\n");
}S[i]とT[i]を結んでそこが!=であるかだからそれはグラフとして見れるから探索して全ての辺において両端の頂点を違うものにできるか見る
公式解説
省略
E - Maximize Rating
高橋君が$${N}$$回コンテストに参加し、$${i}$$回目には$${P_{i}}$$のパフォーマンスを獲得した
レート$${R}$$は$${k}$$個のコンテストを選び、そのパフォーマンスが参加順に$${(Q_{1},Q_{2},…,Q_{k})}$$であるとき
$${R= \frac{\displaystyle\sum_{i=1}^{k}(0.9)^{k-i}Q_{i}}{\displaystyle\sum_{i=1}^{k}(0.9)^{k-i}}-\frac{1200}{\sqrt{k}}}$$
である
レートの最大値はいくつになるか求める問題
自分の回答
動的計画法なのはわかるけどそこから進めなかった
公式解説
int main(void){
const double c=0.9;
int n;
cin>>n;
vector<double>p(n);
vector<double>dp(n+1,0);
double w,ans=-1200.0;
for(int i=0;i<n;i++)cin>>p[i];
for(int i=0;i<n;i++){
dp[i+1]=c*dp[i]+p[i];
for(int j=i-1;j>=0;j--){
dp[j+1]=max(c*dp[j]+p[i],dp[j+1]);
}
}
w=0.0;
for(int i=1;i<=n;i++){
w=c*w+1.0;
ans=max(ans,dp[i]/w-1200.0/sqrt((double)i));
}
cout<< std::fixed << std::setprecision(10) <<ans<<endl;
return 0;
}https://atcoder.jp/contests/abc327/editorial/7564より
kを固定すれば$${\displaystyle\sum_{i=1}^{k}(0.9)^{k-i}Q_{i}}$$の最大値を求めればいいからi番目まででj個選んだ時の最大値で動的計画法してkを全部調べるのか
なるほど