Codeforces Hello 2020
https://codeforces.com/contest/1284
Problem A. Since this system is similar to 十干十二支, so I immediately understood this problem. Maybe, the two are the same.
Problem B. "The sequence is ascent" is the same as "the sequence is not non-increasing".
Problem C. Consider the framed sequence which has a as the minimum and b as the maximum. This sequence must be a permutation of a,a+1,a+2,...,b because this sequence has exactly b-a+1 elements.
Problem D. If a and b are overlap in A and they are not overlap in B, then the subset {a, b} causes "NO". Conversely, if such a pair doesn't exist, the answer is "YES". We can check this condition using line-sweep.
Problem E. Fix a quadrilateral ABCD. There are two cases. The one is that the four makes concave quadrilateral, the other is that the four makes convex quadrilateral. Fix a point P. Consider triangle ABC, ABD, ACD, BCD. In both cases, the point P is included in exactly two of them if and only if the point P is included in the quadrilateral ABCD. Therefore, we only have to count the number of triangles which contains P for all P. Fortunately, this task already exists.
https://yukicoder.me/problems/no/947
問A 十干十二支がある文化圏だとわかりやすそう。
問B ascent は広義単調減少でないことと同値。全体から広義単調減少になるものの数を引けばよい。
問C 最小と最大を固定すると、その部分列の要素数は最大引く最小足す一だから、実はこの列は最小から最大までの数をすべて持つ列になっている。
問D 一方においては重なっているが、もう一方では重なっていない区間の対があったとすると、そのふたつだけを持つ集合を考えると答えがいいえになることがわかる。逆にこのような対がなければ答えははいである。このような対があるかどうかを調べるには平面走査をすればいい。
問E 四角形 ABCD を固定すると、その形状は凸か凹である。点を固定する。点がこの四角形に含まれているとき、かつそのときに限り三角形 ABC, ABD, ACD, BCD のうちちょうどふたつがこの点を含む。これは四角形が凸であっても凹であっても同じである。よって点を固定して、その点を含む三角形がいくつあるか数えればよい。幸いこの問題は yukicoder で出されている。実行時間の速いひとのコードを読むと線形でできるっぽいので、それを読んで解いた。
