Sumitomo Mitsui Trust Bank Programming Contest 2019 — Unofficial Editorial

Revision en3, by errorgorn, 2019-12-01 17:33:25

Sumitomo Mitsui Trust Bank Programming Contest 2019 has just finished, and this is an unofficial editorial.

Thanks to oolimry and shenxy13 for helping write some of the editorial.

A — November 30

You can solve it simply by checking for each end date of the Gregorian calendar. However, note that as the second date directly follows the first date (a fact which I think is not clear in the English translation), we can also check whether they're in different months, or whether the second date is the first day of a month. This can be done in constant time.

Code

B — Tax Rate

C — 100 to 105

We can simply do a 0-infinity knapsack with weights 100,101,...,105 and check if some value is reachable. We get a time complexity of O(N).

Code

D — Lucky PIN

First, we note that there are O(N^3) subsequences of the string, so generating all of them and using a set to check for number of distinct subsequences is TLE. However, there are only at most 1000 distinct such subsequences, from 000 to 999. We can linearly scan through the string for each of these possible subsequences to check if it is actually a subsequence of the string in O(N). Thus, this can be solved in O(1000N), which is AC.

Code

E — Colorful Hats 2

F — Interval Running

Firstly, if $$$T_{1}*A_{1}+T_{2}*A_{2}=T_{1}*B_{1}+T_{2}*B_{2}$$$, the answer is infinity.

Else, WLOG, we let $$$T_{1}*A_{1}+T_{2}*A_{2} > T_{1}*B_{1}+T_{2}*B_{2}$$$. If $$$A_{1} > B_{1}$$$, then Takahashi and Aoki will never pass by each other. The answer is 0. Now, we have solved all the corner cases. We shall move on to the general case.

Tags #atcoder

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English errorgorn 2019-12-02 13:59:02 99
en12 English errorgorn 2019-12-01 18:31:02 0 (published)
en11 English errorgorn 2019-12-01 18:30:39 8 (saved to drafts)
en10 English errorgorn 2019-12-01 18:18:40 6 Tiny change: 'Aoki will meet each' -> 'Aoki will never meet each'
en9 English errorgorn 2019-12-01 17:50:00 20
en8 English errorgorn 2019-12-01 17:48:51 0 (published)
en7 English errorgorn 2019-12-01 17:48:38 76 (saved to drafts)
en6 English errorgorn 2019-12-01 17:45:23 0 (published)
en5 English errorgorn 2019-12-01 17:45:06 11
en4 English errorgorn 2019-12-01 17:44:25 2498
en3 English errorgorn 2019-12-01 17:33:25 1351 testing latex
en2 English errorgorn 2019-12-01 17:26:03 9 Tiny change: '.\n\n[A -- Novembe' -> '.\n\n[A --- Novembe'
en1 English errorgorn 2019-12-01 17:25:47 970 test (saved to drafts)