■競技プログラミング AtCoder Beginner Contest 133 D 問題 不合格の巻

面白がって過去問題を解いているうちに、なんと D 問題まできてしまいました。

AtCoder Beginner Contest 133 D 問題 は Rain Flows into Dams です。

 

問題文

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

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

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

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

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

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

 

さて頭が痛くなりそうですが (^_^;) まずは問題を理解しなければなりません。紙に山とダム (谷) を描いて考えてみましょう。

山が 3 個あるとします。ダム 1 の左が山 1 、右が山 2 です。ダム 1 に溜まった水 A1 は、山 1 と山 2 に降った雨 X1、X2 の半分です。

 

A1 = ( X1 + X2 ) ÷ 2

 

したがって山 1 に降った雨 X1 は、

 

X1 = 2 × A1 - X2

 

となります。同様にそれぞれの山に降った雨は、

 

X2 = 2 × A2 - X3

X3 = 2 × A3 - X1

 

です。ということで、それぞれの式を代入して X を求めると、

 

X1 = A1 - A2 + A3

X2 = A2 - A3 + A1

X3 = A3 - A1 + A2

 

となりました。

山が 5 個の場合はどうでしょう。同様に考えていくと

 

X1 = A1 - A2 + A3 - A4 + A5

X2 = A2 - A3 + A4 - A5 + A1

X3 = A3 - A4 + A5 - A1 + A2

X4 = A4 - A5 + A1 - A2 + A3

X5 = A5 - A1 + A2 - A3 + A4

 

となります。

さてプログラムですが、この式をどうしましょうか。

 

for ( i = 0 ; i < N ; i++ ) {

  for ( j = i ; j < N+i ; j++ ) { 

    A[ j%N ];

 

って感じでループすれば、

 

A[0] A[1] A[2] A[3] A[4]

A[1] A[2] A[3] A[4] A[0]

A[2] A[3] A[4] A[0] A[1]

A[3] A[4] A[0] A[1] A[2]

A[4] A[0] A[1] A[2] A[3]

 

という数列が作れます。あとは符号を反転しては加算していく、と。うん、できそうですね。

 

ということで、

 

  1. 山の数 N を入力
  2. ダムの水量 A を入力
  3. 降雨量 X を計算
  4. すべての山に対して繰返し
  5. 結果を表示

 

という流れでプログラムを書いてみました。

 

/*  AtCoder Beginner Contest 133 D - Rain Flows into Dams
    2019.07.26 by meyon */

 

#include <stdio.h>
#include <stdlib.h>

 

void err()
{
  printf("Error!¥n");
  exit(1);
}

 

int main()
{
  // input N
  int N;
  scanf("%d", &N);
  if(3>N || 99999<N || 0==N%2) {
    err();
  }

 

  // input A
  int A[N];
  for(int i=0; i<N; i++) {
    scanf("%d", &A[i]);
    if(0>A[i] || 1000000000<A[i]) {
      err();
    }
  }

 

  // rainfall X
  int X[N];
  for(int i=0; i<N; i++) {
    X[i]=0;
  }
  for(int i=0; i<N; i++) {
    int s=-1;
    for(int j=i; j<N+i; j++) {
      int amou=A[j%N];
      s=-s;
      X[i] += s*amou;
    }
  }

 

  // display answer
  for(int i=0; i<N; i++) {
    printf("%d ", X[i]);
  }
  printf("¥n");

 

  return 0;
}

 

さぁ提出してみましょう。…… あれ? … あー、TLE (実行時間制限超過) になってしまいました (*_*;)

 


コメント
コメントする








   
この記事のトラックバックURL
トラックバック

■calendar

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
<< October 2019 >>

■search this site.

■recommend

毎日貯まるポイントサイト ECナビ

■recommend

* 楽天ROOM *

■Twitter

■recommend

■recommend

■selected entries

■categories

■archives

■recent comment

■recent trackback

■links

■profile

■others

■mobile

qrcode

■powered

無料ブログ作成サービス JUGEM