This is unofficial editorial for atCoder abc185.

A - ABC Preparation

Just take the minimum number of the 4 given numbers.

Time complexity \(O(1)\).

Code

B - Smartphone Addiction

We need to take the difference between different intervals, if Takahashi was at a cafe at that time then add to his phones battery (be careful not to exceed the maximum capacity), otherwise subtract from his phones battery and keep track that the battery charge remains positive.

Time complexity \(O(M)\).

Code

C - Duodecim Ferra

We can use dp to solve this problem, let’s define dp[i][c] to be the number of ways to cut a bar with length \(i\) into \(c\) cuts. The answer is at dp[l][12]. We can write:

dp[i][c] = dp[i + 1][c] + dp[i + 1][c + 1];

At each state we either make a cut or don’t make a cut.

Time complexity \(O(L \times 12)\).

Code

D - Stamp

We need to find the minimum interval not containing a blue square, as this is the best value to chose for \(k\). And for every interval of white squares of length \(l\) we need to use the stamp: \(\frac{l + k - 1}{k}\) times. Time complexity \(O(M)\).

Code

E - Sequence Matching

We can use dp to solve this problem, let’s define dp[i][j] to be the minimum cost for the suffix of length \(i\) from \(A\) and suffix of length \(j\) from \(B\).

The base case can be defined as:

if (i == n || j == m){
  return (n - i) + (m - j);   // we should delete all remaining numbers.
}

At each state we either delete from \(A\) with cost 1 and move to state dp[i + 1][j] or delete from \(B\) with cost 1 and move to state dp[i][j + 1]. Or keep a mismatch with cost 1 and move to state dp[i + 1][j + 1]. Finally in case of match we move to state dp[i + 1][j + 1] with zero cost.

Time complexity \(O(N \times M)\).

Code

F - Range Xor Query

Very standard segment tree problem, you can read about the solution here.

Time complexity \(O(Q \times log(N))\).

Code