スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

Codeforces Round #665 (Div. 2) 感想

競プロ競プロ日記

ABDの3完でレートは 1940→1828(-112)。うーん（失神）

f:id:scol:20200822030721p:plain — は？

A - Distance and Axis

Bの座標を $x = m$ とすると、 $m = (n-k)/2$ 。

答えは、 $n \lt k$ なら→ $k$ 、
$n \ge k$ かつ $n-k$ が奇数なら→ $1$ 、
$n \ge k$ かつ $n-k$ が偶数なら→ $0$ 。

提出コード

B - Ternary Sequence

A の 0 で B の 2 をできる限り打ち消す。残りは両者大きい順に並べる。これが最適。

"You are given two sequences $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ ."（与えられるとは言っていない）

提出コード

C - Mere Array

解けなかった。全体の正解者数は 6762 らしい。でも解けなかった。うわぁぁぁーーーーーーーーーーー！！！！（発狂）俺は紫コーダーだぞふざけるな！（紫コーダーではない）

......。

......。

$a$ をソートした配列を $b$ とすると、移動する必要があるのは $a_i \neq b_i$ である要素。

$a$ の最小値を $m$ とすると、 $m$ の倍数は好きなように動かせる一方で、そうでないものは動かすことができない。なので、 $a_i \neq b_i$ かつ $a_i \operatorname{\%} m \neq 0$ であるような $i$ が存在すれば NO。存在しなけらば YES。

コンテスト後提出コード

D - Maximum Distributed Tree

f:id:scol:20200822025147p:plain:w500

まず、 $p$ を降順ソートしておく。

$n(n-1)/2$ 通りのすべてのパスにおいて辺 $(i,j)$ が使われる合計回数は上の画像のように求められる。

$k \le n-1$ のときは、使用回数が多い辺から順に大きな $p_i$ を割り当てていく。

$k \gt n-1$ のときは、 $p_1 \times p_2 \times \cdots \times p_{k-n+2}$ を最も使用回数が多い辺に割り当て、 $p_{k-n+3}$ 以降を2番目以降に使用回数が多い辺に割り当てていく。

提出コード