AtCoder Beginner Contest 336

AtCoder Beginner Contest 336 - AtCoder

結果

A - Long Loong : AC(1:19)
B - CTZ : AC(6:08)
C - Even Digits : AC(28:03)
D - Pyramid : AC(48:35)
E - Digit Sum Divisible : 提出無し

A - Long Loong

正整数$${X}$$が与えられるため、「Long」の「o」を$${X}$$個にして出力する問題

自分の回答

int main(){
  int N;
  cin >> N;

  printf("L");
  for(int i = 0; i < N; i++){
    printf("o");
  }
  printf("ng\n");
}

そのまま

公式解説

省略

B - CTZ

正整数$${X}$$が与えられ、それを$${2}$$進数で表したとき末尾に$${0}$$がいくつ連続するか求める問題

自分の回答

int main(){
  int N;
  cin >> N;

  bitset<31> BN(N);
  int ans = 0;
  for(int i = 0; i < 31; i++){
    if(BN[i] == 1){
      break;
    }
    ans++;
  }

  printf("%d\n", ans);
}

そのまま

公式解説

省略

C - Even Digits

非負整数$${n}$$が偶数の数字のみで構成されているとき、その数を良い整数と呼ぶ
正整数$${N}$$が与えられるため、小さい方から$${N}$$番目の良い整数を求める問題

自分の回答

int main(){
  int64_t N;
  cin >> N;

  vector<int> ans;
  while(N != 0){
    ans.push_back(N % 5);
    N /= 5;
  }
  ans[0]--;
  for(int i = 0; i < ans.size(); i++){
    if(ans[i] != -1){
      break;
    }
    ans[i] = 4;
    ans[i + 1]--;
  }

  for(int i = ans.size() - 1; i >= 0; i--){
    printf("%d",ans[i] * 2);
  }
  printf("\n");
}

良い整数のみを見たらそれは5進数として解釈できるためNを5進数に変換し0から始まる分-1して各桁を倍

公式解説

int main() {
  long long N;
  cin >> N;
  N--;
  vector<int> a;
  while (N) {
    a.push_back(N % 5);
    N /= 5;
  }
  if (a.empty()) a.push_back(0);
  reverse(begin(a), end(a));
  for (auto& x : a) cout << x * 2;
  cout << endl;
}

https://atcoder.jp/contests/abc336/editorial/9058より

そうかNはN-1で始めればよかったか

なるほど

D - Pyramid

長さ$${2k-1}$$であり、各項の値が$${(1,2,…,k-1,k,k-1,…,2,1)}$$である数列をサイズ$${k}$$のピラミッド数列という
長さ$${N}$$の数列$${A}$$が与えられるため、$${A}$$に対して
・任意の項の値を$${1}$$減らす
・先頭もしくは末尾の項を削除する
操作を任意の回数繰り返すことで最大いくつのサイズのピラミッド数列を作れるか求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> A(N + 2, 0);
  for(int i = 1; i <= N; i++){
    cin >> A[i];
  }

  vector<int> LR(N + 2, 0);
  for(int i = 1; i <= N; i++){
    if(A[i] > LR[i - 1]){
      LR[i] = min(i, LR[i - 1] + 1);
    }
    else{
      LR[i] = min(LR[i - 1], A[i]);
    }
  }
  vector<int> RL(N + 2, 0);
  for(int i = N; i > 0; i--){
    if(A[i] > RL[i + 1]){
      RL[i] = min(i, RL[i + 1] + 1);
    }
    else{
      RL[i] = min(LR[i + 1], A[i]);
    }
  }
  int ans = 0;
  for(int i = 1; i <= N; i++){
    ans = max(ans, min(LR[i], RL[i]));
  }

  printf("%d\n", ans);
}

各項ごとに最大でどの値になれるかを左からと右からでそれぞれ調べて、各項の小さい方の最大

公式解説

N = int(input())
A = [0] + list(map(int, input().split()))

l, r = [0] * (N + 2), [0] * (N + 2)
for i in range(1, N + 1):
    l[i] = min(A[i], l[i - 1] + 1)
for i in range(N, 0, -1):
    r[i] = min(A[i], r[i + 1] + 1)
print(max(min(l[i], r[i]) for i in range(1, N + 1)))

https://atcoder.jp/contests/abc336/editorial/9078より

考えは同じだけどifはいらなかったか

E - Digit Sum Divisible

正整数$${n}$$が$${n}$$の各桁の和で割り切れる時、$${n}$$を良い整数と呼ぶ
正整数$${N}$$が与えられるため、$${N}$$以下の良い整数がいくつあるか求める問題

自分の回答

制約的に良い整数だけ列挙する方法があるんだろうけどさっぱり思いつかなかった
和ごとに何かできそうな気はするんだけど…

公式解説

int main() {
  string N;
  cin >> N;
  long long ans = 0;
  for (int s = 1; s <= 9 * 14; s++) {
    vector dp(N.size() + 1, vector(s + 1, vector(s, vector(2, 0LL))));
    dp[0][0][0][1] = 1;
    rep(d, N.size()) rep(i, s + 1) rep(j, s) rep(f, 2) rep(t, 10) {
      if (i + t > s) continue;
      if (f and N[d] - '0' < t) continue;
      dp[d + 1][i + t][(j * 10 + t) % s][f and N[d] - '0' == t] += dp[d][i][j][f];
    }
    ans += dp[N.size()][s][0][0] + dp[N.size()][s][0][1];
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc336/editorial/9055より

桁和を固定して0から始めてそこに0～9をpush_backした結果どうなるかを[何桁目まで][今の桁和][余り][N以上になる可能性があるか]のdpで配っていく形か
push_backする数字がtだから桁はd+1、桁和はi+t、余りは(j*10+t)%s、fが0かつtがNのd桁目未満なら1に
これで固定した桁和を1～14*9までしてそれぞれのdp[Nの桁数][s][0][0||1]の総和が答え

なるほど