20日目：Beginner037

20日目(2019/9/5)

AtCoder Beginner Contest 037

解けた問題

A:饅頭

数買うだけなら、安い方を限界まで買えばいいよね。ってことでif文で分岐して、大きい方でCを割った結果を出力したよ。

B:編集

問題サイズがそこまで大きくなかったので二重ループで回しても間に合うな、と思って順当に更新していって出力しました。

#include <iostream>
#include <vector>
using namespace std;


int main(void){
    int N,Q;
    cin >> N >> Q;
    vector<int> a(N);
    int L,R,T;
    for(int i=0;i<Q;i++){
        cin >> L >> R >> T;
        for(int j=L-1;j<R;j++){
            a[j] = T;
        }
    }
    for(int i=0;i<N;i++){
        cout << a[i] << endl;
    }
}

C:総和

問題サイズ的に二重ループを回したら間に合わないなって思って、二重ループにならない方向性で考えました。
端っこの方からKまでは、1~K個と順番に足す回数が増えていき、 K番目からN-K-1番目まではK個足して、 N-K~N-1まではK~1まで減っていく、という考えでかけたものを足して出力、細かいところでめちゃくちゃミスしたなぁ…。
重なる場合とかも考慮してあげよう。

#include <iostream>
#include <vector>
using namespace std;

int main(void){
    int N,K;
    long long sum=0;
    cin >> N >> K;
    vector<long long> a(N);
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    int judge = K > N-K+1 ? N-K+1 : K;
    for(int i=0;i<(N+1)/2;i++){
        
        // 
        // cout << i <<":"<<a[i] << "|" << N-i-1 << a[N-i-1] << endl; 
        if (i<judge){
            sum += a[i]*(i+1);
            if(i!=N-i-1)
                sum += a[N-i-1]*(i+1);
        }else{
            sum += a[i]*judge;
            if(i!=N-i-1)
                sum += a[N-i-1]*judge;
        }
    }
    cout << sum << endl;
}

解説を見てみる

今日はC問題まで解きました。
C問題は、全体の和を求めておいて実装する方法もあるみたい。 S[0]=a[0]~a[K-1]までの和を求めて、S[1] = S[0]-a[0]+a[K]みたいな方法で和を求めてももしかしたら計算時間的に余裕あるかもな～なんて思いました。