AtCoder Beginner Contest 148 Solution & Reflection

December 22, 2019


Foreword

This is a relatively easy contest, especially the first 5 questions.

A: Round One

for (int i = 1; i <= 3; i++)
  if (i != A && i != B)
    cout << i << endl;

B: Strings with the Same Length

for (int i = 0; i < N; i++)
  cout << S[i] << T[i];

C: Snack

Output the LCM of AA and BB. You can use the __gcd function in C++.

cout << A * B / __gcd(A, B) << endl;

D: Brick Break

Greedy to find the longest subsequence of 1,2,3,1, 2, 3, \dots. If there is no such subsequence (i.e. no 11 in the sequence) output -1.

int t, nxt = 1, cnt = 0;
for (int i = 0; i < N; i++) {
  cin >> t;
  if (t == nxt)
    nxt++;
  else
    cnt++;
}
cout << (cnt == n ? -1 : cnt);

E: Double Factorial

If NN is odd, the number of trailing zeros is 0. Otherwise, it is the number of 5 in the prime factorization of 24N2 \cdot 4 \cdot \dots \cdot N.

if (N % 2) cout << 0;
else {
  long long ans = 0;
  while (N) {
    ans += N / 10;
    N /= 5;
  }
}

F: Playing Tag on Tree

Assume that Aoki is standing on the root of the tree. Then Aoki always walk downwards. We can exhaust the ending vertex of Takahashi.

If Takahashi ends at vertex EE, then he will first move to the lowest common ancestor of EE and uu. We must check that Aoki cannot reach this vertex before Takahashi does. Then Takahashi and Aoki will both move downwards until Takahashi reaches node EE. Finally, Aoki moves towards Takahashi while Takahashi keeps moving between EE and parent of EE.