0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

円形に N 個の山が連なっており、時計回りに山 1 , 山 2 , … , 山 N と呼ばれます。 N は奇数です。

これらの山の間に N 個のダムがあり、ダム 1 , ダム 2 , … , ダム N と呼ばれます。ダム i ( 1 ≤ i ≤ N ) は山 i と山 i + 1 の間にあります (山 N + 1 は山 1 のことを指します)。

山 i ( 1 ≤ i ≤ N ) に 2 x リットルの雨が降ると、ダム i − 1 とダム i にそれぞれ x リットルずつ水が溜まります (ダム 0 はダム N のことを指します)。

ある日、各山に非負の偶数リットルの雨が降りました。

その結果、ダム i ( 1 ≤ i ≤ N ) には合計で A i リットルの水が溜まりました。

各山に降った雨の量を求めてください。この問題の制約下では解が一意に定まることが証明できます。

2.制約

入力は全て整数である。
3 ≤ N ≤ 10⁵− 1
N は奇数である。
0 ≤ A_i ≤ 10⁹
入力が表す状況は、各山に非負の偶数リットルの雨が降った際に発生しうる。

3.入力例

入力

5
3 8 7 5 5

出力

2 4 12 2 8

4.初見の感想

数式にするとよくわかる(入力をA,B,C,出力をx,y,zという関係で表します)

(x/2)+(y/2)=A
(y/2)+(z/2)=B
(z/2)+(x/2)=C

x,y,zのうち一つ判明すれば、あとは芋づる式に導出できる
上の3つの式を全て足すと

x+y+z=A+B+C

ここからxを求めるなら,(y/2)+(z/2)=Bを使ってy,zを消す

5.学びポイント

最初のダム以外のすべての和を取得したい

→偶数行目だけ足すと、綺麗に最初のダム以外のすべての和の半分が得られる！

芋づる式に計算できるので、計算量が小さいのが最高

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Split();
        long[] A = new long[N];
        long[] ans = new long[N];
        long sum = 0;
        long halfsum = 0;
        for (int i = 0;i < N; i++)
        {
            //全体和sumと最初のダム以外の数値の和halfsumを取得
            A[i] = long.Parse(input[i]);
            sum += A[i];
            if (i % 2 == 1) { halfsum += 2*A[i]; }
        }
　　　//最初のダムの値を計算
        ans[0] = sum - halfsum;
        for(int i = 0; i < N-1; i++)
        {
　　　//式はダムiとダムi+1の関係式なのでダムi+1がわかる
            ans[i + 1] = 2 * A[i] - ans[i];
        }
　　　//配列出力
        Console.WriteLine(string.Join(" ", ans));
    }
}

7.最後に

対称式はとりあえず足せって、大学受験でよく言われたの思い出しました(^-^;

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 133 D - Rain Flows into Dams