AtCoder Beginer Contest 082 - u_sho競プロぶろぐ

　久々にブログ書くけど、書いてない間に競プロやってなかったわけではないよ。・・・ほんとだよ？
きのうもABCは21時開始のとこ21:40にレジったけど、競プロやってなかったわけではないんだよ。・・・ほんとだってば。

A - Round Up the Mean

　はい！　自然数 a, b がもらえるので、a と b の平均(mean)を小数点以下を切り上げ(round up)て整数で出力しなさい。っていう問題。
a+b=c とおいたとき、c が偶数なら、答えは c/2 ですが、c が奇数なら、答えは (c+1)/2 ですね。というのを使って解きました。

#include <iostream>
int main(){
    int a, b;
    std::cin >> a >> b;
    c = a+b;
    if(c%2) c = (c+1)/2;
    else c /= 2;
    std::cout << c << std::endl;
    return 0;
}

　ほかの解法として、切り上げ関数ceilを用いるものがあります。ceilはmath.hに入っていて、実数型を受け取って小数点以下を切り上げてくれます。double型で読み取って、double型の割り算をして、ceilを使って切り上げて、int型にキャストして、出力します。

#include<iostream>
#include<cmath>
int main(){
    double a, b;
    std::cin >> a >> b;
    std::cout << (int)ceil((a+b)/2.0) << std::endl;
    return 0;
}

　でもね、もっと頭のいいやり方があってね、

#include <iostream>
int main(){
    int a, b;
    std::cin >> a >> b;
    std::cout << (a+b+1)/2 << std::endl;
}

　こっちの方が自然そうなのに何で思いつかなかったんでしょうね。

B - Two Anagrams

　英小文字からなる２つの文字列 s, t が与えられるので、s と t をそれぞれ並べ替えて、辞書順で s
よりも t が大きくなるかどうかを判定しなさい。という問題。
　つまり、s を辞書順最小に並べ替えて(qwerty->eqrtwy)、t を辞書順最大に並べ替えて(qwerty->ywtrqe)、このときに辞書順で s < t かどうかを判定すればよい。注意するのは、s = t のときである。このときは s < t でないから、"No\n" を出力する。また、s が "aaa" で t が "aa" とかのときは s > t である。注意。
　辞書順に並べ替えるのには、sort関数を使うとよい。この関数大好き。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    string s, t;
    getline(cin, s);    getline(cin, t);
    sort(s.begin(), s.end());    sort(t.rbegin(), t.rend());

    bool ans=false;
    if(s.length()>=t.length()){
        for(int i=0; i<t.length(); i++){
            if(s[i] > t[i])break;
            if(s[i] < t[i]){
                ans = true;
                break;
            }
        }
    }else{
        ans = true;
	for(int i=0; i<t.length(); i++){
            if(s[i] > t[i]){
                ans = false;
                break;
            }
            if(s[i]<t[i]) break;
	}
    }
    if(ans)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

　これ頑張って書いたんですよ。でもね、

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
    if (s < t) cout << "Yes\n";
    else cout << "No\n";
}

　これでコンパイル通るらしくてね。虚無。入力のgetlineも辞書順比較のためのfor文も必要なかった...orz
　んで、t.rbegin()とかt.rend()とかなんなんだというお話ですが、begin()は先頭のイテレータ、end()は末尾のイテレータでしたが、rbegin()は先頭の逆(reverse)イテレータで、同じくrend()は末尾の逆イテレータですね。つまり、sort(t.begin(), t.end())したあとにreverse(t.begin(),t.end())してるのと一緒ですね。ただし、これは、sort(t.begin(), t.end(), greater())よりも遅いらしいので、時間制約が厳しい場合には注意しましょう。

C - Good Sequence

　長さNの数列 a が与えられるので、a から要素をいくつか取り除いて、a をよい数列(good sequence)にします。a　がよい数列であるとは、a の任意の要素 x が、a 全体で x個存在することを言います。取り除く最小の個数を出力しなさい。という問題。
　たとえば、3が2個(2<3)のときは、2個とも取り除き、3が4個(4>3)のときは、1個(4-3)取り除き、3が3個(3=3)のときは、0個(3-3)取り除きます。

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

int ans, count, num;

int main(){
    int N;  cin >> N;
    int a[N];
    for(int i=0; i<N; i++)cin >> a[i];
    sort(a, a+N);
    for(int i=0; i<N; i++){
        if(num!=a[i]){
            ans += count<num ? count : count-num;
            num = a[i];
            count = 0;
        }
        count++;
        if(i==N-1)
            ans += count<num ? count : count-num;
    }
    cout << ans << endl;
    return 0;
}

　んでね、解説見たらね、、、

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> mp;
    int a, N; cin >> N;
    for(int i=0; i<N; i++){
        cin >> a;
        mp[a]++;
    }
    int ans = 0;
    for(auto p: mp){
        int x = p.first;
        int n = p.second;
        ans += n<x ? n : n-x;
    }

    cout << ans << endl;
}

　数え方が上手！　んで、for(auto p:mp)とはなんぞやという話なんだけど、こいつは範囲for文というやつで、任意なコンテナのサイズいっぱい回してくれるんですね。便利かもよ。

D - FT Robot

　解法思いついたよ。でもその解法TLEなると思ったよ。想定解だったよ。おしまい。

おしまい。