[Codeforces] Educational Codeforces Round 56 C. Mishka and the Last Exam

Mishka and the Last Exam

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

考え方

題意

\( n \) が偶数として、要素数が \( n \) の単調増加な配列 \( a \) を求める問題です。

要素数が \( \dfrac{n}{2} \) の配列 \( b \) が与えられます。この配列の要素は、\( b_i = a_i + a_{n – i + 1}\) が成り立ちます。

方針

方針が思いつかなったので、解説を読みました。

\( l = 0, \ r = 10^{18} \) とします。次の手順を繰り返して配列 \( a \) を求めます。配列の添え字は \( 0 \) オリジンとします。

  • \( a_i = \min(l, b_i – r), \ a_{n – i – 1} = \max(r, b_i – l)\)
  • \( l = a_i, \ r = a_{n – i – 1} \)

コード

感想

解説を読んでもいまいち分かりませんでした。

シェアする

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

フォローする