Discommunication

日記帳

ABC043 B-C

All Submissions - AtCoder Beginner Contest 043

  • B - バイナリハックイージー
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    string answer = "";
    for(int i=0;i<s.size();i++){
        if(s[i]=='0' || s[i]=='1') answer.push_back(s[i]);
        else{
            if(answer.size()==0);
            else answer.erase(answer.end()-1);
        }
    }
    cout << answer << endl;
}

・雑感
 そのまま実装するだけ

  • C - いっしょ
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    int a[100];
    for(int i=0;i<N;i++) cin >> a[i];
    int ave=0;
    for(int i=0;i<N;i++) ave += a[i];
    ave = (int)round(ave/N);

    vector<long long int> cost(3,0);
    for(int i=0;i<N;i++){
        cost[0] += pow(a[i]-ave-1,2);
        cost[1] += pow(a[i]-ave,2);
        cost[2] += pow(a[i]-ave+1,2);
    }
    long long int k = *min_element(cost.begin(),cost.end());
    cout << k << endl;
    return 0;
}

・雑感
 cost=Σ[(a[i]-x)^2]を最小にしたい訳だが、どう見てもxの値が平均値周りの時は最小を取る。
 なので平均値を求めてからその周りを調べて最小値を出力すれば良い
 模範解答見たらx=[1-100]で全探索とかいっててびっくりしちゃった 
 ゴリ押し最強か?
 
 数学的には、cost'=Σ(2x-2a[i])=2(Nx - Σa[i])。
 増減表

x ... Σa[i]/N ...
cost' - 0 +
cost x