[Codeforces] Round #525 C. Ehab and a 2-operation task

Ehab and a 2-operation task

https://codeforces.com/contest/1088/problem/C

考え方

題意

数列 \( a \) について次の操作を行って、厳密に昇順になるようにします。

  1. 整数 \( x \) を用いて、\( 0 \leq i \leq j < n \) を満たす\( j \) を指定し、範囲内の全ての \( i \) について、\( a_i = a_i + x \) と置換する。
  2. 整数 \( x \) を用いて、\( 0 \leq i \leq j < n \) を満たす\( j \) を指定し、範囲内の全ての \( i \) について、\( a_i = a_i \mod x \) と置換する。

\( n + 1 \) 回以下の操作で操作を行った順に出力します。

方針 1

数列を全て \( 0 \) にしてから全て \( 10^6 \) にします。これは、 \( 2 \) 回の操作で行うことができます。最初に \( 1 \) で剰余を行えばよいです。

次に、\( i \) 番目の数列に対して \( i = 0 \) から \( i = n – 2 \) まで順番に、\( 10^6 – i\) で剰余を取ります。この操作を行うと数列は \( [0, 1, \cdots, n – 2, 10^6]\) となります。

従って、全体で \( n + 1 \) 回の操作を行うことになります。

方針 2

数列を \( [0, 1, \cdots, n – 1]\) となるようにします。

まず初めに、加算の操作である操作 1. だけを行って、次のような数列を作ります。

\( a_i = b_in + i\)

上記のような数列ができた後は、全ての要素に対して \( n \) で剰余演算を行えばよいです。このような数列を作るには、数列の末尾から先頭に向かって加算の操作を行います。\( i \) 番目に加算する値を \( x_i \) とします。また、その和を \( s_i = x_0 + x_1 + x_2 + \cdots + x_i \) とします。ただし、\( x_0 = 0 \) とします。

\( x_i = n – (a_{n – i} + s_{i – 1}) \mod n + n – i – 1\)

よって、全体で \( n + 1\) 回の操作が必要になります。

コード

方針 1

方針 2

感想

操作が影響しない項は何かを考えるのが難しかったです。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする