記録

Dashboard - Codeforces Round #818 (Div. 2) - Codeforces

まったり参加で3完, 約17000人中1336位でした Dは誤読ミス、Eは間に合わなかった…

解法・反省

A

解法

2変数のlcm, gcdに対して次の等式がある. これは有名だとおもう.
$\text{lcm}(a,b) \times \text{gcd}(a,b) = a \times b$
だから, $\frac{\text{lcm}(a,b)}{\text{gcd}(a,b)} \le 3 \Leftrightarrow \frac{a \times b}{\text{gcd}(a,b)^2} \le 3$ となる.

一方, サンプルを眺めるとCF Div.2-A問題らしく, O(1)っぽい. 周期があるんだろうか. 周期は $\text{lcm}(1,2,3) = 6$ っぽい. 1から5までのサンプルはあるので, 6の値を調整してサンプルが全部合うようにする. 投げるとAC.（1個目の解法）

厳密には, 新たに $n$ を絶対使うとき, $\frac{a \times b}{\text{gcd}(a,b)^2} = 1$ のとき $(n,n)$ . $略=2$ のときは $(n/2, n), (n, n/2)$ （ただし $n/2$ が整数のとき）の2種. $略=3$ のときは $(n/3, n), (n, n/3)$ の2種.
これらはそれぞれ異なるから, $1$ の倍数→ $+1$ , $2$ の倍数→ $+2$ , $3$ の倍数→ $+2$ とできる.
$O(N)$ 解ができたが, 主客転倒すると $O(1)$ に帰着できる.（2個目の解法）

提出

Pypy3 Submission #170595385 - Codeforces

Pypy3 Submission #170715002 - Codeforces

B

Problem - B - Codeforces
提出 20分 (0)

解法

ぼくは英語が読めない. 問題文がわからないんだ.
問題は構築問題で, どの隣接する連続kマス（kはnの約数）にも文字「X」が1個以上含まれるようなもののうち,「X」の数が最小になるものを出力するもの. ただし, 入力で与えられる座標 $(r,c)$ は必ず「X」を使わないといけないらしい.

n×nのテーブルを, k×kの小ブロックによって (n/k)×(n/k)に分割する. 小ブロックはどれも同じように繰り返し, 小ブロックは

とする.
これで連続kマスに文字「X」が1個以上必ず存在するようにできて, しかもそういうものとして最小と証明できる（鳩の巣論法とかで）
しかし, これでは $(r,c)$ の条件を確保できない. 解決は簡単で, たんに小ブロック内で条件確保するために順列をswapすればよい.

提出

PyPy3 Submission #170603358 - Codeforces

C

Problem - C - Codeforces
提出 28分 (1)

解法

問題文は巡回っぽい操作をさせている. 操作は可換じゃない.
まず $a_i$ は増加させる方にしか行けないから, $a_i > b_i$ なら駄目. もちろん, 操作して $a_i > b_i$ にするのも駄目.
$a_i = b_i$ ならそのままがいいし, $a_{i-1}$ にとっても $a_i$ がでかければでかいほど増加できる最大値が高くていい.

つまり, 操作を繰り返すことをまとめたとき, $a_i \leftarrow \text{max}(a_i, \text{min}(b_i, a_{i+1} + 1))$ とできる.
ここで, 本番は後ろから操作することを何回か繰り返した嘘解法で通したが, 自明な反例があったので投げたらhackできた. 弱すぎる.
結局, $a_{i-1} = b_{i-1}$ でないなら, $b_i$ に対して $b_{i-1}$ が $b_i + 1$ 以下であることが必要.

提出

Pypy3 (嘘解法, Hacked） Submission #170607146 - Codeforces

Pypy3（多分正しい） Submission #170719228 - Codeforces

D

Problem - D - Codeforces
提出コンテスト後

解法

問題文を誤読しまくって結局何も分からなかった.
・Madokaはトーナメントの参加者と, それぞれのトーナメントの勝敗をあらかじめ決定する.
・スポンサーは, トーナメントの勝敗を最高 $k$ 回変えて優勝者の番号を変える.

意志の考察としては
・Madokaはトーナメントの勝者の番号をできるだけ小さくしたいが, スポンサーは勝者の番号をできるだけ大きくしたい.
となる.

Madokaが定める最適なトーナメントにおいて, スポンサーが達成できる勝者の番号の最大値を求めればいい.
$n <= k$ ならスポンサーは最も番号が小さい人を優勝させられるので $2^n$ .

トーナメントはこのような形に帰着できるが, 勝利するためにどのくらい変更すればいいかは緑色になる. 勝利するための変更数を小さい方から, 番号が小さい順に埋めればいい.

変更数が $i$ であるものは $\binom{n}{i}$ 個あることが証明できる！（エスパーもできる）
だから結局答えは $\sum^{k}_{i = 0} \binom{n}{i}$ となる. 二項係数前処理でok.

提出

Pypy3 Submission #170657625 - Codeforces

E

Problem - E - Codeforces
提出コンテスト後

解法

A問題の考察のごとく
$\displaystyle \text{lcm}(c, \text{gcd}(a,b)) = \frac{c \times \text{gcd}(a,b)}{\text{gcd}(a,b,c)}$ となる.

愚直にやると自由度2なので $O(n^2)$ で求められる. 高速な言語でも工夫しない限りちょっと無理そう.

$c$ を固定する. このとき, 残りは $n-c$ を $a, b$ に分配する. このとき, $\text{gcd}(a,b) = g$ としたら, $g \mid a$ かつ $g \mid b$ である. （ $x \mid y$ は $y$ は $x$ で割り切れること）よって, $g \mid n-c = a+b$ である.
つまり, $\text{gcd}(a,b)$ は必ず $n-c$ の約数となる. この手の問題には主客転倒が効く. 愚直に計算する代わりに, gcdが $g$ となるようなものの個数を数え上げる手法である.
今回, $g \mid n-c$ に対して, $g \mid a$ and $g \mid b = n-a-c$ となるような $a,b \ge 1$ は $\frac{n-c}{g} - 1$ 個ある.
そこから, $g \mid g'$ かつ $g' \mid n-c$ に対して, $\text{gcd}(a,b) = g'$ となるようなものをすべて除外すればよい.
$\text{gcd}(a,b) = g, a+b=n-c, a,b \ge 1$ となる個数を $f(c,g)$ とする. いま $f(c,g)$ は計算できた.
それが問題に寄与するのは $\displaystyle \frac{c\times g}{\text{gcd}(c,g)} \times f(c,g)$ である. これは簡単に計算できる.
$x$ の約数の個数を $\sigma(x)$ として, $c$ を固定すると $O(\sigma(n-c)^2)$ の計算量で計算できた.

我々は $O(\sum^{n-1}_{i=1} \sigma(i)^2) + O(\sum^{n-1}_{i=1} \sqrt{i})$ で求めることができた. これでACできる.
計算量は後者は $n^{3/2}$ だが, 前者は正直わからなかった. 手元環境でかなり速かったので提出した.

解法をまとめるとかなり簡単だが, これを考えつくまでにかなり時間がかかった. コンテスト中に通したかった…