Arc's blog

競プロなど

ABC072/ARC082を解いたので記録を残す

だいぶ昔のやつですが、ABC072/ARC082のA~D問題を解いたので記録を残します。

問題文はAtCoder公式からどうぞ。

A - Sandglass2

ans=x-tをして、ans>=0だったらそのまま出力。それ以外だったら0を出力。

int main(void)
{
    int x, t;
    cin >> x >> t;
    int answer = x - t > 0 ? x - t : 0;
    cout << answer << endl;
 
    return 0;
}

B - OddString

一文字飛ばしで文字を足していく。実装ゲー。

int main(void)
{
    std::string s;
    std::string answer;
    cin >> s;
    for (int i = 1; i <= (int)s.size(); i++)
    {
        if (i % 2 == 1)
        {
            answer += s[i - 1];
        }
    }
    cout << answer << endl;
 
    return 0;
}

C - Together

{\displaystyle a_i}{\displaystyle a_i-1}{\displaystyle a_i}{\displaystyle a_i+1}になれる。

{\displaystyle x}に対して、count[x-1]++; count[x]++; count[x+1]++;をしていった後、どのcount[]が最大の値かを調べればOK。

イメージとしては「長さnの直線上に積み木を3つずつ積んでいく」感じ。一番高く積み上がった場所が答え。

int main(void)
{
    int n;
    int count[100000] = {};
 
    cin >> n;
    int m1;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        count[m1]++;
        if (m1 - 1 >= 0)
            count[m1 - 1]++;
        if (m1 + 1 < 100000)
            count[m1 + 1]++;
    }
 
    int max = 0;
    for (int i = 0; i < 100000; i++)
    {
        if (count[i] > max)
            max = count[i];
    }
 
    cout << max << endl;
 
    return 0;
}

D - Derangement

{\displaystyle p_i\neq i}である所をt,そうでない所をfとする。

ffとなっている所をスワップするとttにできる。

また、ftとなっている所をスワップしてもttにできる(数は1つずつしかないため、スワップ後にtがfになってしまうことはない)。

貪欲的に「fが見つかったら右隣とスワップして、さらに右隣の場所から検索を再開する」という操作をしていけばいい(自分のソースコードだと無駄な処理をしています)。

int main(void)
{
    int n;
    int answer = 0;
    int m1;
    std::vector<int> number;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        number.push_back(m1);
    }
 
    for (int i = 0; i <= n; i++)
    {
        if (number[i] == i + 1)
        {
            if (i + 1 < n && number[i + 1] == i + 2)
            {
                answer++;
                i++;
            }
            else
            {
                answer++;
            }
        }
    }
 
    cout << answer << endl;
 
    return 0;
}