メンズワキガ対策専門ブランドD AGICA【ディーアジカ】

 

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

AtCoder Beginner Contest 133 D 問題  Rain Flows into Dams を解いてみましたが、TLE (実行時間制限超過) となって不合格でした。

 

余談ですが、いろいろ数値を入力して確認しているときに、答えが負数になる場合がでてきました。確認のために AC の方のプログラムを実行してみたところ、やっぱり負数になります。うーん、マイナスの雨が降るなんてありえない話じゃ ……

考えること小一時間 (^_^;) 問題文の制約に次の一文を見つけました。

 

入力が表す状況は、各山に非負の偶数リットルの雨が降った際に発生しうる。

 

わかりにくい文ですが、つまり「答えが負数になるような入力は与えませんよ」ってことなんでしょう。ということで、それは気にする必要はないのだと判断しました。

 

閑話休題

 

結果が TLE になったということは計算量が多すぎるってこと。解決策を求めて解説をみてみることにします。ん〜と… そうか、漸化式をそのまま順番に計算していけば O(n) にできるんだ。なるほど (^_^;)

 

では解説を参考にして、もう一度考えなおしてみましょう。

 

前回と同じく山は 5 個とします。降雨量の総量を S とすると、

 

S = A1 + A2 + A3 + A4 + A5 = X1 + X2 + X3 + X4 + X5

X1 = S - ( X2 + X3 + X4 + X5 )

 

X2 + X3 = 2 × A2 、X4 + X5 = 2 × A4 ですから、

 

X1 = S - 2 × ( A2 + A4 )

 

これでまず X1 が求まりました。あとは、

 

X2 = 2 × A1 - X1

X3 = 2 × A2 - X2

X4 = 2 × A3 - X3

X5 = 2 × A4 - X4

 

と順番に計算していけばよいです。このような前の式によって定まる式を「漸化式」というそうです。漸化式をそのまま順番に計算していくことで全体の計算量を減らせるなんて、考えが及びませんでした。

 

ということで、計算部分を改善してみました。太字が変更した部分です。

 

/*  AtCoder Beginner Contest 133 D - Rain Flows into Dams
    2019.07.28 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;
  }

 

  int S=0;
  for(int i=0; i<N; i++) {
    S += A[i];
  }
  int P=0;
  for(int i=1; i<N; i+=2) {
    P += A[i];
  }
  X[0]=S-2*P;   // X1=S-2(A2+A4+...+A[n-1])

 

  for(int i=0; i<N-1; i++) {
    X[i+1]=2*A[i]-X[i];   // X[i+1]=2Ai-Xi

  }

 

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

  return 0;
}

 

入力して、範囲外の場合はエラー終了。ここは毎度同じです。

改善した rainfall X の部分。

 

  1. 配列変数 X[N] を宣言して初期化
  2. 総降雨量 S = A1 + A2 + ... + A5 を計算
  3. X1 の算出のために P = (A2 + A4) を計算
  4. X1 = S - 2 × P で X1 を求める
  5. X2 = 2 × A1 - X1 を求め、繰返し X3、X4、X5 を算出

 

といった感じです。

はい、これで AC (合格) となりました \(^o^)/ 実行時間は 23ms 、メモリ 2048KB でした。

 


コメント
コメントする








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

■calendar

S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031
<< August 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