Divisor [第八回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202109-open/tasks/past202109_d

前提知識

• 約数列挙

解説

https://atcoder.jp/contests/past202109-open/submissions/26602449

とある数の約数の個数が計算できれば、あとは判定するだけとなるので、
実質問題視されているのは、約数の部分である。
今回は制約的に実は約数列挙してしまっても問題ない。
今後のためにも、高速に約数列挙する方法を学んでおこう。
自分はライブラリ化してあるので、回答自体は貼るだけだった。

約数列挙

自分が下手に説明するより、
N の約数を全列挙するアルゴリズム | アルゴリズムロジック
を見る方がいいと思う。
計算量がO(sqrt(N))となっているが、sqrtは平方根のことである。
平方根を知らない学生については、そちらも学ぶといいかもしれない。

あと、自分の実装では少し計算量が悪くてlogがついてしまっているのだが、
今まで問題になったことはない。
自分の実装は上の投稿リンクからたどってほしい。

int X, Y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y;

    int cntX = enumdiv(X).size();
    int cntY = enumdiv(Y).size();

    if (cntX > cntY) cout << "X" << endl;
    else if (cntX < cntY) cout << "Y" << endl;
    else cout << "Z" << endl;
}

Number of Apperance [第八回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202109-open/tasks/past202109_c

解説

https://atcoder.jp/contests/past202109-open/submissions/26585529

問題で要求されていることを実装する問題。
入力の個数がやや多いので少し気を付ける必要があるかもしれない。
何故か通らないという場合は入力処理だけを残して提出してTLEになっていないか確認するといいだろう。
今はどうか分からないが、昔はcin.tie(0); ios::sync_with_stdio(false);を付けないとcinではTLEしていた。

あとは、それほど難しいものはない。
ループで配列Aをなめていって、Xと同じものがあればカウンターをインクリメントしてやるだけ。

int N, X, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];

    int ans = 0;
    rep(i, 0, N) if (A[i] == X) ans++;
    cout << ans << endl;
}

intersection [第八回 アルゴリズム実技検定 B]

https://atcoder.jp/contests/past202109-open/tasks/past202109_b

解説

https://atcoder.jp/contests/past202109-open/submissions/26585385

やや工夫が必要になる問題。
配列A,Bに含まれる数は制約からすべて別々であるということから、
重複とかは考えずに、単純にA[i] == B[j]を満たすようなものを選択して値の小さい順に答えていく。
配列Aと配列Bが値の小さい順になっているとは限らないので、一旦答えを配列ansに保持しておいて、
最後にソートしてから答えることにする。

A[i] == B[j]を満たすような(i,j)を探せばいいので、iとjをそれぞれ探索するような2重ループを書こう。
条件を満たすような数が見つかれば、それを配列ansに入れていく。

値の小さい順に答える必要があるので、答える前にソートをしよう。
C++であればsort関数を使う。
自分は特殊なマクロで書いているが、マクロなしだとsort(ans.begin(), ans.end());といった感じになるだろう。

後は答えるだけであるが、少し見栄えを気にして前の要素があれば空白を入れるなどしている。
多分昨今は無駄なスペースがあっても通るような気がするが、別の競プロサイトはAtCoderほどしっかりしてない可能性もあるので、
自分はなるべく要求通りに書くようにしている。

int N, M;
int A[1010];
int B[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    vector<int> ans;
    rep(i, 0, N) rep(j, 0, M) if (A[i] == B[j]) ans.push_back(A[i]);
    sort(all(ans));

    rep(i, 0, ans.size()) {
        if (0 < i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}

Bubbler [第八回 アルゴリズム実技検定 A]

https://atcoder.jp/contests/past202109-open/tasks/past202109_a

解説

https://atcoder.jp/contests/past202109-open/submissions/26585144

指定されていることを実装する問題。
取れる選択肢は、

「A + B - C」円（それぞれ頼んで割引する）
「D」円（セットを頼む）

の2択なので、この2択の小さい方を答えとすればいい。
C++ではmin関数というのがあり、引数のうち小さい方を返してくれるので、これを使うとスムーズ。

int A, B, C, D;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C >> D;
    int ans = min(A + B - C, D);
    cout << ans << endl;
}

箱と鍵 (Boxes and Keys) [JOI 2021/2022 一次予選 (第1回) 過去問 D]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_d

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26486427

宝箱を中心に考えてみよう。
とある宝箱を開錠するためには書かれている番号と同じ番号が書かれた鍵が存在する必要がある。
よって、すべての宝箱についてループを書いて、その中で対応する鍵があるかどうかを確認しよう。
これも同様にすべての鍵についてループを書いて、存在するものがあるかどうかを探せばいい。

発展課題

今回は宝箱のループで100回のループ、鍵のループで100回のループを行ったので、全体で最大10000回のループを
行っていることになる。
鍵のループの部分はsetなどのデータ構造を使うことで、ループの回数を減らしてより高速に計算することが可能になる。
他にもソートを使ってうまくやる方法などもあるので、高速化の方法も考えてみるといいと思う。

より詳しく書くと今回の解法は計算量O(N²)であるが、O(NlogN)、O(N)まで改善ができる。
考えてみるといい。

int N, M, A[101], B[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        bool ok = false;
        for (int j = 0; j < M; j++) {
            if (A[i] == B[j]) ok = true;
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}

複雑な文字列 (Complex String) [JOI 2021/2022 一次予選 (第1回) 過去問 C]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_c

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26485238

文字種を数える問題なので、C++であればsetを使うのがオススメ。
setは同じ要素が入った場合でも1つにまとめてくれるので、全要素を入れても最終的には重複を除いた状態で格納してくれる。
なので、すべての文字をsetに入れて、中身の個数を持ってくると種類数が得られる。
これを3以上とそれ以外で答え分けをすればACできる。

int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    set<char> chars;
    for (auto c : S)
    {
        chars.insert(c);
    }

    if (3 <= chars.size()) cout << "Yes" << endl;
    else cout << "No" << endl;
}

移動 (Moving) [JOI 2021/2022 一次予選 (第1回) 過去問 B]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_b

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26485022

A地点からB地点を経由してC地点に移動するにはX+Y時間だけかかる。
判定したいのはZ時間30分以内に移動できるかということである。
ここで注意点があり、問題文をより正確に判定するのであれば、気持ちとしては「X+Y≦Z + 1/2」を判定したくなる。
コンピュータ上では小数を正確に扱うというのはやや難しく、条件判定をする際にもなるべく小数をなくす方がいい。
今回はX,Yはどちらも整数なので、X+Yも同様に整数となる。
よって、小数の1/2を考える必要はなく、「X+Y≦Z」と判定してしまって問題ない。

int X, Y, Z;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y >> Z;

    if (X + Y <= Z) cout << 1 << endl;
    else cout << 0 << endl;
}