Educational Codeforces Round 80 A から E
A. Deadline
x と d/(x+1) が近いほど値が小さくなりそうなので d の正の平方根の前後を 100000 くらいを探したんだけど、これやるなら 1 から 1000000 を全探索で良かった。
B. Yet Another Meme Problem
b の桁数を L だと仮定する。そうすると与えられた条件は $ab + a + b = a \cdot 10^L + b$ と言い換えられる。式変形すると $a(b+1-10^L)=0$ となる。$a$ は零でないため $b+1-10^L=0$ である。つまり $b=10^L - 1$ である。$b=10^L - 1$ とすると確かに $L$ 桁になっているから、これは解である。$L$ としてありうるものは 1 から 10 しかないため、すべて探しても間に合う。なお各 $b$ に対して $a$ は任意であるから、$b$ としてありうる場合の数に A を掛けたものが答えになる。
C. Two Arrays
これは本番自分が思いついた方法とは異なる。b を反転して a の後ろにつければ、この問題は長さ 2m の数列を数え上げる問題に言い換えられる。これは C(2m+n-1,n-1) 通りある。
D. Minimax Problem
最大値を $x$ 以上にできるかを二分探索する。i 番目の数列に対して集合 $S_i$ を $A_{i,j}$ が $x$ 以上となる $j$ 全体とする。$S_i$ と $S_j$ の和集合が $\{1,2,\ldots,m\}$ となれば i と j は答えである。$S_i$ としてありうるものは 256 通りしかないため、$S_i$ を 256 通り確かめればよい。
AtCoder Beginner Contest 151
Tasks - AtCoder Beginner Contest 151
A
言語を間違えてしまい 1WA。char 型に一を足すと int 型になることを考えてなくて 1WA。インクリメントなら壊れません。
B
N 掛ける M 引く総和をそのまま出力して 1WA。点数に上下限があることにきづいて修正しましたが、100 点満点だと勘違いして 1WA。
C
定期的に似たような問題が出されるので、AC してない問題の WA は数えないことは印象に残っていました。
D
グラフの直径といいます。木であれば線形時間で解けますが、一般には二乗時間かかると思います。
E
max X の総和から min X の総和を引けば求まります。max X の総和と min の総和は対称的なので、max X を求めることだけ考えます。A を整列しておきます。N 個から K 個選んだときの最大値は、選ばれた数のうちもっとも右側の数です。もっとも右側の数が A[x] であるような組合せは A[1] から A[x-1] までから K - 1 個選ぶ組合せの数だけあるので、A[x] は C(x-1,K-1) 回足されます。これをすべての A[1] から A[N] に対して行えばよいです。
余談ですが A[1] から A[N] までから K 個選ぶ選び方は、「A[x] が最も右側である K 個の選び方」をすべての x=1 から N までをあわせたもの、なので
\begin{align}
\sum_{x=1}^{N} {}_{x - 1}\mathrm{C}_{K - 1} = {}_{N} \mathrm{C}_{K}
\end{align}
という恒等式が成り立ちます。
F
最小包含円の形は二通りあって、ある二点を直径とする円か、ある三点を通る円です。このことから最小包含円の中心の候補は、二点の中点と、三点の外心に限られます。二点の中点はすぐに求められますが、三点の外心はそこまで明らかではありません。
外心は三角形の各辺に対する垂直二等分線の交点です。よって交点が求められればよいです。任意の三角形は平行移動によって原点を頂点にもつ三角形に移せるので、一点が原点のうえにあるような三角形 OAB に対して外心を与えることを考えます。
直交座標
A(a,b), B(c,d) とします。線分 OA の垂直二等分線は $(a,b) \cdot ( (x, y) - (a / 2, b / 2) ) = 0$ です。原点を通りベクトル $(a,b)$ と直交する直線は $(a,b) \cdot (x,y) = 0$ なので、これを $(a/2, b/2)$ だけ平行移動したと考えればよいです。同様にして線分 OB の垂直二等分線は $(c,d) \cdot ( (x, y) - (c / 2, d / 2) ) = 0$ です。この二直線の交点は連立方程式
\begin{align}
ax + by &= \frac{a^2 + b^2}{2} \\
cx + dy &= \frac{c^2 + d^2}{2}
\end{align}
の解になります。クラメルの公式によって
\begin{align}
x = \frac{\begin{vmatrix} \frac{a^2+b^2}{2} & b \\ \frac{c^2+d^2}{2} & d\end{vmatrix}}{\begin{vmatrix} a & b \\ c & d \end{vmatrix}}
\end{align}
\begin{align}
y = \frac{\begin{vmatrix} a & \frac{a^2+b^2}{2} \\ c & \frac{c^2+d^2}{2}\end{vmatrix}}{\begin{vmatrix} a & b \\ c & d \end{vmatrix}}
\end{align}
です。
複素座標
点 A(a), B(b) とします。線分 OA の垂直二等分線は $|z|^2 = |z-a|^2$ です。$|z|^2 = z \overline{z}$ なので $z \overline{a} + \overline{z} a = a \overline{a}$ と書き換えられます。同様に線分 OB の垂直二等分線は $|z|^2 = |z-b|^2$ であり、書き換えれば $z \overline{b} + \overline{z} b = b \overline{b}$ です。$z$ と $\overline{z}$ の連立方程式を解けばよく、クラメルの公式より
\begin{align}
z = \frac{\begin{vmatrix} a \overline{a} & a \\ b \overline{b} & b\end{vmatrix}}{\begin{vmatrix} \overline{a} & a \\ \overline{b} & b \end{vmatrix} }
\end{align}
です。
直交座標だと x と y の両方を解かなければならないのに対して、複素座標だと z だけ解けばいいので実装するのが楽です。
ちなみに本番は検索して出てきた tubo さんのコードを貼りました。
AtCoder Beginner Contest 150 D. Semi Common Multiple
https://atcoder.jp/contests/abc150/tasks/abc150_d
初項 $A_i / 2$、公差 $A_i$ の等差数列が $N$ 個ある。これらの共通部分を求め、そのうち 1 以上 M 以下のものがいくつあるか求めればよい。ふたつの等差数列の共通部分はまったく存在しないかふたたび等差数列となるかである。そのため等差数列と等差数列の共通部分が求められれば、それを繰り返すのみである。
Codeforces 614 Div. 2 A から F
A
ありうる最も左の点と右の点がわかれば、その間の点はすべてありうるので植木算。自分は気づかなかったが、要素数足す一が答え。
B
連続部分列の和の最大値は動的計画法で求められる。この問題では列全体が答えにならないようにしなければならない。そこで前半 $N - 1$ 個と後半 $N - 1$ 個でそれぞれでわけて解くとよい。
C
$a$ と $b$ が互いに素でないとき $a$ と $b$ を最大公約数で割ったものを選んだほうが得であるため、$a$ と $b$ は互いに素であると仮定してよい。このとき $a$ は $X$ の約数となるはずである。よって $X$ の約数 $d$ であり $d$ と $X/d$ が互いに素になるようなもののなかに答えはある。
D
桁数 $L$ 以下であり、長さ $N$ の列 $A$ が与えられたとき最小値を求める問題 $f(L,A)$ を考える。$X$ を上の桁から決めていくことを考える。$L$ 桁目が $0$ であるものを $A_0$ に、$1$ であるものを $A_1$ に振り分ける。このとき $A_0$ が空ならば $f(L - 1, A_1)$ が答え、$A_1$ が空ならば $f(L - 1, A_0)$ が答え、そうでないならば $f(L - 1, A_0)$ と $f(L - 1,A_1)$ のうち小さい方が答えになる。
E
どの区間も互いに包含関係にならない場合を考える。このとき左端で整列すれば右端も整列される。そのため左から見ていくことで解ける。
包含関係にある場合、ある区間に包含されているような区間を消していくと、どの区間も互いに包含関係にならない区間集合が得られる。この区間集合はどのような消し方をしても同じものが得られる。この過程で消された区間は答えを与えることはないため、得られた区間集合だけを考えればよい。
得られた区間集合を $I_1,\ldots,I_n$ とする。$I_k$ に包含されている区間の集合を $ J_1, \ldots ,J_m $ としたとき、$ I_1, \ldots,I_{k - 1},I_{k+1},\ldots,I_n,J_1,\ldots,J_m $ の和集合の連結成分数を数えられればよい。$ J_1,\ldots,J_m $ を列挙するとき $I_{k - 1}$ や $I_{k+1}$ にも包含されているようなものは列挙する必要がないため、$k$ が $1$ から $n$ を動くとき $ m $ の和は $n$ 以下にできる。また連結成分数の計算は $f(I_1,\ldots,I_{k - 1}) + f(I_{k - 1},J_1,\ldots,J_m,I_{k + 1}) + f(I_{k + 1},\ldots,I_{m}) - 2$ でできる。ただし $I_{k - 1}$ や $I_{k + 1}$ が存在しないときは $2$ の部分を適切に減らす。
F
解説を読んでから解いた。これは賢い。
最大公約数を g に固定する。このとき $g, 2g, 3g, \ldots$ だけを見ればよい。g が 1 から 100000 まで動くとき、見ることになる数は 100000 log 100000 個程度であることに気をつける。
最大公約数が 1 の場合を考える。100000 から 1 へと見ていく数を減らしていき、見終えるたびに見た数をスタックに積んでいく。このときスタックの上の方に小さい値が積まれることに気をつける。いま見ている数と互いに素な数がスタックに含まれている場合、その数より上に積まれている値は取り除いてしまってよい。もしもスタックの中に互いに素な数が含まれているのかが高速に判定できればこの問題を解くことができたことになる。
たとえば 12 と互いに素なものの個数は「1 の倍数の個数」引く「2 の倍数の個数」引く「3 の倍数の個数」足す「6 の倍数の個数」で求められる。「k の倍数の個数」が 1 から 100000 のすべての k に対して計算されていれば、たかだか 12 の約数の個数分の足し引きで互いに素なものの個数が数えられる。
計算量解析においては「k の約数の個数」の二乗を 1 から 100000 まで足したものが現れるが 26324772 であるため間に合う。
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 で出されている。実行時間の速いひとのコードを読むと線形でできるっぽいので、それを読んで解いた。
