問題
個のグラスが1列に並んでおり、
番目のグラスにはジュースが
単位だけ入っている。
このグラスの連続する一部分を選択し、奇数番目のグラスに入ったジュースの量の合計と偶数番目のグラスに入ったジュースの量の合計を等しくできるか判定せよ。
すなわち、 である整数
を選んだときに、
の偶奇が等しいならば、
を満たすような が存在するかを判定せよ。
入力
まず最初の1行目に、テストケースの個数を表す整数 が与えられる。
その後、 個のテストケースのそれぞれに対して、以下のように入力が与えられる。
- 最初の1行目には、整数
が与えられる。
- 次の1行には、
が順に与えられる。
条件
- 実行時間制限: 1s
- メモリ制限: 256MB
- すべてのテストケースにおける
を超えない。
- すべてのテストケースにおける
出力
行にわたり、各テストケースについて、等しくできるならば
YES を、できないならば NO を出力すること。
解法
まず、整数 を愚直に
から順番に調べていき、条件を満たす
が存在するのかを調べていく方法が考えられます。
この方法では
の計算量がかかります。
しかし、問題の条件より、 であるので、これでは実行時間制限に間に合いません。
そこで、与えられた条件式を変形して、使いやすい形にできないかを考えます。
与えられた数列 に対して、条件を満たす整数
が存在すると仮定します。
すなわち、
\begin{align}
{a}_{l} + {a}_{l + 2} + \cdots = {a}_{l + 1} + {a}_{l + 3} + \cdots
\end{align}
がこのとき成立します。
この式を変形すると、
\begin{align}
{a}_{l} - {a}_{l + 1} + {a}_{l + 2} - {a}_{l + 3} + \cdots + {(-1)}^{r - l} \cdot {a}_{r} = 0
\end{align}
が成立すると言えます。
さらに、この式の符号について整理すると、
\begin{align}
{a}_{l} + {(-1)} \cdot {a}_{l + 1} + {(-1)}^{2} \cdot {a}_{l + 2} + {(-1)}^{3} \cdot {a}_{l + 3} + \cdots + {(-1)}^{r - l} \cdot {a}_{r} = 0
\end{align}
であり、両辺に
をかけると、
\begin{align}
{(-1)}^{l} \cdot {a}_{l} + {(-1)}^{l + 1} \cdot {a}_{l + 1} + {(-1)}^{l + 2} \cdot {a}_{l + 2} + {(-1)}^{l + 3} \cdot {a}_{l + 3} + \cdots + {(-1)}^{r} \cdot {a}_{r} = 0
\end{align}
が成立します。
ここで、左辺の値に着目すると、
\begin{align}
\, & {(-1)}^{l} \cdot {a}_{l} + {(-1)}^{l + 1} \cdot {a}_{l + 1} + {(-1)}^{l + 2} \cdot {a}_{l + 2} + {(-1)}^{l + 3} \cdot {a}_{l + 3} + \cdots + {(-1)}^{r} \cdot {a}_{r} \\
= \, & \{ {(-1)} \cdot {a}_{1} + \cdots + {(-1)}^{r} \cdot {a}_{r} \} - \{ {(-1)} \cdot {a}_{1} + \cdots + {(-1)}^{l - 1} \cdot {a}_{l - 1} \}
\end{align}
と変形することができます。
このことから、値 を、
\begin{align}
\mathrm{sum}_{i} = {(-1)} \cdot {a}_{1} + \cdots + {(-1)}^{i} \cdot {a}_{i}
\end{align}
として定義すると、問題の条件を満たす
が存在するとき、
\begin{align}
\mathrm{sum}_{r} - \mathrm{sum}_{l - 1} = 0
\end{align}
より、
\begin{align}
\mathrm{sum}_{l - 1} = \mathrm{sum}_{r}
\end{align}
が成立すると言えます。
ここで、 にて問題の条件を満たす
が存在するときについては、先程の変形から
\begin{gather}
{(-1)}^{1} \cdot {a}_{1} + {(-1)}^{2} \cdot {a}_{2} + \cdots + {(-1)}^{r} \cdot {a}_{r} = 0 \\
\therefore \; \mathrm{sum}_{r} = 0
\end{gather}
ということが言えます。
従って、便宜的に
として扱うと、この場合でも
が成立します。
以上から、与えられた数列 に対して、
の値を求め、これらの中から等しい値を取るものが1組でもある場合は、条件を満たす
が存在すると判定することができます。
の値については、
\begin{align}
\mathrm{sum}_{i + 1} = \mathrm{sum}_{i} + {(-1)}^{i + 1} \cdot {a}_{i + 1}
\end{align}
によって求めることができるため、全体で
の計算量で求めることができます。
また、等しい値があるかの判定については、例えば得られた を昇順にソートすることで、要素の前後で等しい組があるかを調べ上げて判定することができます。
これはソートに
の計算量がかかりますが、実行時間制限にも十分間に合うと考えられます。
この問題は の値を出力する問題ではないので、以上の方法により条件内で判定することができます。
ソースコード
整数 が存在するかを判定し、存在するならば
true を、しないならば false を返す関数 solve() を以下のように実装しました。
int n; ll a[int(2e5 + 5)], sum[int(2e5 + 5)]; bool solve() { // 値の入力 cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; if (i % 2 != 0) { sum[i] = sum[i - 1] - a[i]; // i が奇数ならば a[i] を引く } else { sum[i] = sum[i - 1] + a[i]; // i が偶数ならば a[i] を足す } } sort(sum, sum + n + 1); // sum[0] から sum[n] までを昇順にソートする for (int i = 0; i <= n - 1; i++) { if (sum[i] == sum[i + 1]) { // sum の値が前後で等しければ、 true を返す return true; } } return false; // 前後で等しいものが存在しなければ、 false を返す }
