Codeforces Round #737 (Div. 2)のきろく

久しぶりのCodeforces&参戦録です。レート冷えなくてなんとか安心したっていう感じです。問題文和訳はこちら

A. Ezzat and Two Subsequences / Ezzat и две подпоследовательности (500点)

最大値の影響を大きく、最小値の影響を小さくしたいので、最大値を少ない方の部分列に、最小値を多い方の部分列にもっていければいいかなと思いました。公式解説によると、最大値とそれ以外で分ければいいようですが、本番は証明できず、少し怖かったので配列をソートして、b_1,\,b_2,\,\dots,\,b_n として、\displaystyle\max_{i=1}^{n-1}\left\{\frac{1}{i}\sum_{j=1}^i a_j + \frac{1}{n-i}\sum_{j=i+1}^{n} a_j\right\} を出力することにしました。

B. Moamen and k-subarrays / Moamen и k-подотрезки (1000点)

k=l (1 \leq l \lt n) でソートできる場合、k = l+1 では要素数2 以上の連続部分列を分割すれば、同様にソートすることができるので、ソートできる最小分割数を求めればいいことが分かります。

a_i,\,a_{i+1} についてソート後においても連続する (b_j,\,b_{j+1} みたいな感じ) ときは同一連続部分列に属すようにしてもいいですが、そうでない場合は違う連続部分列に属すようにしなければなりません。よって連続部分列の最小数は、ソート後においても連続するような部分列の数となります。

C. Moamen and XOR / Moamen и XOR (1750点)

桁DPです。

{\mathrm{dp}}_{i,j} = (\text{上位 \(i\) 桁について(\(j\) ? 両辺が等しい : 左辺が大きい) 場合の数})
とすると、
{\mathrm{dp}}_{0,j}=\left\{
    \begin{array}{ll}
      0 & (j = \mathrm{false})\\
      1 & (j = \mathrm{true})
    \end{array}
  \right.
です。

各桁について数字の選び方は 2^n 通りです。上位桁で左辺の方が大きいことが決まっている場合、下位については任意の選び方で左辺の方が大きくなります。

n が奇数のときは、bitAND が 1 となる、全てが 1 のときはbitXORも 1 であり、bitANDもbitXORも 0 となるのは偶数個のみが 1 であるときで、{}_n{\mathrm{C}}_0 + {}_n{\mathrm{C}}_2 + \dots + {}_n{\mathrm{C}}_{n-1} = 2^{n-1} 通りであるので

{\mathrm{dp}}_{i,j}=\left\{
    \begin{array}{ll}
      2^n{\mathrm{dp}}_{i-1,\mathrm{false}} & (j = \mathrm{false})\\
      (2^{n-1}+1){\mathrm{dp}}_{i-1,\mathrm{true}} & (j = \mathrm{true})
    \end{array}
  \right.
となります。
n が奇数のときは、bitAND が 1 となる、全てが 1 のときはbitXORは 0 であり、bitANDもbitXORも 0 となるのは偶数個のみが 1 であるときで、{}_n{\mathrm{C}}_0 + {}_n{\mathrm{C}}_2 + \dots + {}_n{\mathrm{C}}_{n-2} = 2^{n-1}-1 通りであるので
{\mathrm{dp}}_{i,j}=\left\{
    \begin{array}{ll}
      2^n{\mathrm{dp}}_{i-1,\mathrm{false}}+{\mathrm{dp}}_{i-1,\mathrm{true}} & (j = \mathrm{false})\\
      (2^{n-1}-1){\mathrm{dp}}_{i-1,\mathrm{true}} & (j = \mathrm{true})
    \end{array}
  \right.
となります。

Ezzat and Grid / Ezzat и таблица (2500点): 未提出

分かりません...

E. Assiut Chess / Шахматы в Assiut (3000点): 未提出

コンテスト中には、問題文すら見ていませんでした...

結果、感想

f:id:Flkanjin:20210812021015p:plain
久しぶりの参戦でレートを温めることができて嬉しいです。このまま紫になりたいなぁ。