AtCoder Beginner Contest 043

[TakefumiYamamura]

http://abc043.contest.atcoder.jp/

[TakefumiYamamura]

C - いっしょ / Be Together

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 200 点

問題文

N 個の整数 a1,a2,..,aN が与えられます。えび君はこれらを書き換えて全て同じ整数にしようとしています。各ai(1≦i≦N)は高々一回しか書き換えられません(書き換えなくても良い)。整数xを整数yに書き換えるとき、コストが(x−y)2かかります。仮にai=aj(i≠j)だとしても、ひとつ分のコストで同時に書き換えることは出来ません(入出力例2 を参照)。えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。

制約

1≦N≦100 −100≦ai≦100

Note

Constraint is not so hard, so I can use Brute-force search

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long
using namespace std;

int main(){
    int n;
    int a[101];

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    ll ans = 1000*1000;
    for (int i = -100; i < 101; ++i)
    {
        ll tmp = 0;
        for (int j = 0; j < n; ++j)
        {
            tmp += (a[j] - i) * (a[j] - i);
        }
        ans = min(tmp, ans);
    }
    cout << ans << endl;

}

[TakefumiYamamura]

D - アンバランス / Unbalanced

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 400 点

問題文

文字列 t について、t の長さが 2 以上であり、かつ t の中の文字のうち過半数が同じ文字であるとき、t をアンバランスであると呼ぶことにします。例えば、voodoo や melee はアンバランスであり、noon や a はアンバランスではありません。

小文字のアルファベットからなる文字列 s が与えられます。s にアンバランスな (連続する) 部分文字列が存在するか判定してください。存在する場合は、s の中でそのような部分文字列が存在する位置を一つ示してください。

制約

2≦|s|≦105 s は小文字のアルファベットのみからなる。 部分点 2≦|s|≦100 を満たすデータセットに正解した場合は、200 点が与えられる。

note

think of the minimum set

#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <map>
#define ll long long 

using namespace std;

int main(){
    string s;
    cin >> s;
    map<string, int> hash;

    for (int i = 0; i < s.length(); ++i)
    {
        if(i+1 < s.length() && s[i] == s[i+1]){
            cout << i+1 << " " << i+2 << endl;
            return 0;
        }
        if(i+2 < s.length() && s[i] == s[i+2]){
            cout << i+1 << " " << i+3 << endl;
            return 0;
        }
    }
    cout << "-1 -1" << endl;
}