22日目(2019/9/8)

AtCoder Beginner Contest 140

10:00開始で、11時には予定が入っていたので、 45分くらい取り組みました！久々のリアタイ参加！ A~C問題を解いてレーティングは315(+67)になりました。
んー…フル参加できたらD問題くらいまでは解けたかもしれないと考えるとちょっと悔しいかもだけど順調に上がってきたので文句なしです！
振り返っていこう。

解けた問題

A: Password

3桁のパスワードを設定するらしい。 1~N以下の数字のみを使うらしいので、N*N*Nを出力すればいいですね！

B:Buffet

ビュッフェってこう書くんだ…。
まず情報を整理すると、Aで出てくる順番がわかる。
なので、i回目の食事に得られる満足度はB[A[i]]で与えられる
連続で食べた時のボーナスA[i-1]+1 == A[i]のときに、C[A[i-1]-1]を満足度に加算するように実装しました。

// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N-1);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    for(int i=0;i<N;i++){
        cin >> B[i];
    }
    for(int i=0;i<N-1;i++){
        cin >> C[i];
    }
    int sat = B[A[0]-1];
    for(int i=1;i<N;i++){
        sat += B[A[i]-1];
        if(A[i-1]+1 == A[i]){
            sat += C[A[i-1]-1];
        }
    }  
    cout << sat << endl;
}

C : Maximal Value

max(Ai,Ai+1)<=Bを満たすので、まず左右の要素A[0],A[N-1]は、B[0]とB[N-2]になるなぁ、と考え、その間の要素を埋めていこうと考えました。　　で、ルールを考えると、


A	B[0]		min(B[0],B[1])		min(B[1],B[2])		min(B[2],B[3])
B		B[0]		B[1]		B[2]

となることに気づいたので、実装しました。

// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N-1);
    for(int i=0;i<N-1;i++){
        cin >> B[i];
    }
    int max=B[0];
    int sum=B[0];
    for(int i=0;i<N-1;i++){
        if(i==N-2){
            sum += B[i];
        }else{
            sum += min(B[i],B[i+1]);
        }
    }
    cout << sum << endl;
}

解けなかった問題

D:Face Produces Unhappiness

この問題に取り組む時点で30分くらい経過していたので、残り10分ほどでした。
同じ向きを多くの人が向いている状態を作り出すにはどうしたら良いか、色々考えたけど良い手法が思いつかず…。

解説を見てみる

向きを変える操作を行うと、一回につき最大で2人を幸福にすることができる。ということにまず気づけなかった（注目しなかった）のが多分最大の敗因。端の部分以外は、この操作を行うことによって、2人ずつ増やすことができ、端では1人のみを増やすことができるので、その回数を考えてみると答えが出てくるみたいですね。

アルスの今日プロ日記

22日目： Beginner 140