【AtCoder】競プロ初心者でもできる300点問題

はじめに

こんにちは、背の高い人と申します。今のところ何か特別強いものを持っているわけではありませんが、競プロが好きなので競プロの話をします(AtCoderのレートはたまに茶色パフォが出る程度の灰色です)。何か書くことないかなーと思ってAtcoder Problemsを見ていたら僕が自力でACできた300点問題を見つけたので2問ほど紹介しようと思います。200点問題が安定してきたから300点も解けるようになりたい！っていう人はぜひ解いてみて自信をつけてください。特に弊部のつよつよ1年生なんかは解けるのではないでしょうか。

環境

C++14(GCC 5.4.1)

問題たち

C - Remainder Minimization 2019

https://atcoder.jp/contests/abc133/tasks/abc133_c
この問題は全探索しようをするとTLEします。そこでループの回数を工夫しましょう。まず確認しておくと、 (i × j)mod 2019 とは 「(i × j)を2019で割った余り」のことです(僕は所見でググりました)。2019で割った余りを求めるのであれば、0 <= (i × j)mod 2019 < 2019 となります。ということはL < i < Rの範囲でループしながらL < j < L+2019 または L < j < R を満たす(i × j)mod 2019 の範囲を探索してあげればいいですね。そうすればなんと2重目のループの回数が最高でも2019回で済みます。
↓コードの例

#include<bits/stdc++.h>
using namespace std;

int main(){

    long long int l,r;
    cin >> l >> r;
    long long int ans = 2019;

    for(long long int i = l; i < r; ++i){
        for(long long int j = i+1; j <= r && j < l+2019; ++j){
            ans = min((i*j)%2019, ans);
            if(ans == 0)break;
        }
    }

    cout << ans << endl;


}

この問題に限ったことではありませんが、300点問題あたりから非常に大きな数値を扱うことが多くなります。適宜long long型の変数を使ってあげましょう。僕はとある問題で変数のサイズの設定のミスに二日くらい気付かず頭を悩ませていたこともあるので、考え方は正しいはずなのになぜかWAが出る！というときはデバッグ時にそこも気を付けてみてください。

C - Exception Handling

https://atcoder.jp/contests/abc134/tasks/abc134_c
この問題は各ループで消去される変数が1個だけというのがポイントです。1個しか消去されないなら、数列の最大値が消去されない限りは何が消去されようと条件に合う要素の最大値はそのまま数列の最大値となります。ということで最大値をまず max_a という変数にコピーしてあげましょう。あとは基本的に max_a を出力し、 max_a と同値の要素が消去されたときは2番目に大きい要素を出力する…
というのは実は間違いです。というのも、この考え方では最大値が複数ある場合に対応できません。例えば、 {1. 3. 3} という数列の場合、2番目の3を消去しても3番目の3が残っているので、最大値は3になります。しかし、先程の考え方では数列の最大値である3を無視してしまうので適切ではありません。そこで、最大値を max_a にコピーするのではなく、隔離しましょう。最大値となる要素をを1つだけ max_a に格納し、その要素を0にしておきます。そして元々最大値であった0が消去された場合は現在の数列の最大値を、されなかった場合は max_a を出力すれば解けます。
↓コード

#include<bits/stdc++.h>
using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> a(n);
    int max_a = 0;

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

    for(int i = 0; i < n; ++i){
        if(a.at(i) == max_a){
            a.at(i) = 0;
            break;
        }
    }

    for(int i = 0; i < n; ++i){
        if(a[i] == 0)cout << *max_element(a.begin(), a.end()) << endl;
        else cout << max_a << endl;
    }

}