ARC087 / ABC082 A~D解こうとしてみた。

　ARC087 / ABC082を解いたので、初心者なりに考え方などを書いて行きます。

　AtCoderの解説放送を参考にしています。
https://www.youtube.com/watch?v=GDuzZIuWs2Q

A - Round Up the Mean

　a+b+1の平均を取れば良い。

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a,b;
    cin >> a >> b;

    cout << (a+b+1) / 2 << endl;

    return 0;
}

B - Two Anagrams

　s,tをソートして、tを逆順にして比較すればおk。

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s,t;
    cin >> s >> t;

    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());

    cout << (s < t ? "Yes" : "No") << endl;

    return 0;

}

C - Good Sequence

　数字が出てきた回数がその数字よりも少なかったら出てきた回数、多かったら回数-その数字で良い数列にすることができます。

　数字が出てきた回数を数え上げるところで少し悩んだ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    long long a[100010];
    long long cnt = 1;
    long long ans = 0;

    cin >> n;

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

    sort(a,a+n);

    
    for (int i = 1;i < n;i++){
        if (a[i] == a[i-1]) cnt++;
        else{
            if (a[i-1] > cnt) ans += cnt;
            else ans += cnt - a[i-1];
            cnt = 1;
        } 
    }
    if (a[n-1] > cnt) ans += cnt;
    else ans += cnt - a[n-1];

    cout << ans << endl;

    return 0;

}

D - FT Robot

ロボットの動きを、X軸とY軸に分けて考えるといいらしい。
　
　この考え方でコードを書いてみたが、テストケースの2/3はACできたが、残りの1/3はREになってしまう。二時間粘っても取れなっかったので断念。

まとめ

　D問題はDPをもっと理解していれば解ける気がするので、DP頑張りたい。