Language Test 202001

Language Test 202001

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

PracticeA - Welcome to AtCoder

Do as they indicate us to do.

ABC086A - Product

Flush Odd if $(AB) \% 2 = 0$ or ‘Even’ otherwise.

ABC081A - Placing Marbles

Count 1.

ABC081B - Shift only

Let

$f(x) = $ how many times we can divide $x$ by $2$.

We can implement $f$ by shift operation. The answer is $\min _ {i \in N} f(A[i])$.

ABC087B - Coins

Execute $3$-times loops.

ABC083B - Some Sums

For all $1 \leq x \leq N$, we calculate the sum of each digit of $x$. We sum up suitable $x$.

ABC088B - Card Game for Two

Simple greedy algorithm works.

ABC085B - Kagami Mochi

The answer is the number of the unique elements of $d$. We can easily calculate it as follows.

  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
  cout << d.size() << endl;

ABC085C - Otoshidama

We can solve it by brute-force method in $O(N^2)$-time. Let $i$, $j$ be the number of $10000$-yen, $5000$-yen, respectively. We use $k$ to denote the number of $1000$-yen. Of course $k = N - i - j$. We check whether $10000i + 5000j + 1000k = Y$ or not.

ABC049C - 白昼夢 / Daydream

We reverse $S$ and each keyword. Then, we can use greedy algorithm.

ABC086C - Traveling

First of all, we set the first state as $(0, 0, 0)$.

For each $i$, let $d$ be the $l ^ 1$ distance between $(x _ i, y _ i)$ and $(x _ {i + 1}, y _ {i + 1})$ and $T = t _ {i + 1} - t _ i$. We can take a trip on $i \to (i + 1)$ if and only if $d \geq T$ and $\lvert T - d \rvert \% 2 = 0$.

L - Interactive Sorting

Solution

We define bool query(int const& x, int const& y); by asking the query.

Case 1

We can use std::sort. We use query as its third argument.

Case 2

The idea is the same as above. We make our marge_sort and use query as its compare function. With the help of STL, we can easily implement as follows.

template <typename Iter, typename Comp>
void merge_sort(Iter begin, Iter end, Comp cmp)
{
  int N{static_cast<int>(end - begin)};
  if (N <= 1)
  {
    return;
  }
  auto mid{begin + N / 2};
  merge_sort(begin, mid, cmp);
  merge_sort(mid, end, cmp);
  vector<typename Iter::value_type> temp(N);
  merge(begin, mid, mid, end, temp.begin(), cmp);
  copy(temp.begin(), temp.end(), begin);
}

Here we have assumed that Iter is a random access iterator. Using SFINAE, we can implement as follows.

template <typename Iter, typename Comp>
void merge_sort_impl(Iter begin, Iter end, Comp cmp, random_access_iterator_tag)
{
  // same.
}

template <typename Iter, typename Comp>
void merge_sort(Iter begin, Iter end, Comp cmp)
{
  merge_sort_impl(begin, end, cmp, typename std::iterator_traits<Iter>::iterator_category());
}

Case 3

We can possess the whole space of the possibilities by next_permutation. Every time we determine the query, we choose the most powerful query. That’s all.

M - モンスターテイマー

We are waiting for WJ…

Others