[AtCoder] AtCoder Petrozavodsk Contest 001 B – Two Arrays

Two Arrays

https://atcoder.jp/contests/apc001/tasks/apc001_b

二つの数列に操作を施して同じ数列になるかどうかを調べる問題です。

考え方

題意

数列 \( A = \{a_1, a_2, \cdots , a_N \} , B = \{b_1, b_2, \cdots , b_N \}\) に対して、次の操作を行います。

\(a_i \) に \( 2 \) を加算し、 \( b_j \) に \( 1 \) を加算します。この操作を行って同じ数列を作れるかどうかを判定します。

方針

  • \( a_i < b_i\) のとき

\( b_i – a_i \) 回 \( a_i \) と \( b_i \) に操作を施します。

  • \( b_i < a_i\) のとき

\( a_i – b_i \) 回 \( b_i \) に1を加算することで、\( a_i = b_i \) となります。このとき、\( a_j \leq b_j – 2 \) となる \(a_j\) に \( 2 \) を\( a_i – b_i \) 回加算する必要があります。

したがって、まず初めに、\( b_i < a_i\) となる要素に対して、

\[ t = \displaystyle \sum_{ i = 1 }^{ n } (a_i – b_i )\]

を計算します。\( t\) 回分 \( a_j \leq b_j – 2 \) となる \(a_j\) に対して \( 2 \) を加算することができれば同じ数列を作成できます。

つぎに、\( a_i < b_i\) となる要素に対して、

\[ s = \displaystyle \sum_{ i = 1 }^{ n } \lfloor \dfrac{b_i – a_i}{2} \rfloor \]

を計算します\( t \leq s \) となれば同じ数列を作成できます。

コード

感想

下のサイトの考え方が分かりやすかったです。

https://kimiyuki.net/writeup/algo/atcoder/apc001-b/

\( 300 \) 点の問題にしては考察が難しい問題だと思いました。

シェアする

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

フォローする