[Atcoder備忘録記事]AtCoder Beginner Contest 338 C問題

AtCoder Beginner Contest 338 C問題
こちらの問題です。

問題

入出力例

解法

片方の個数を決めてしまえばもう片方の個数も自動的に決まる性質を利用します。
Q,A,BがNの長さ分あるのでその中から最小を見つけたりといった部分が少し複雑で難しく感じました。
この手の問題にもなれなければいけませんね。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <cmath> 
#include <algorithm>
using namespace std;

int main() {
    int N;
    int ans = 0;
    cin >> N;
    vector<int> Q(N);
    vector<int> A(N);
    vector<int> B(N);
    for(int i = 0; i < N; i++) cin >> Q[i];
    for(int i = 0; i < N; i++) cin >> A[i];
    for(int i = 0; i < N; i++) cin >> B[i];

//iの個数は確定しないので、無限ループで回す。
    for(int i = 0;; i++){
    //最小値の変数。とりあえずでかい値をいれておく
        int y = 10000000;
        //Q配列からAの数分材料を引いたときの残り
        vector<int> R(N);
        bool ok = true;
        //残りをR配列に格納。
        for(int j = 0; j < N; j++) R[j] = Q[j] - A[j] * i;
        //どれか一つでも0をしたまわったらループ離脱(その時点で考え得るAの個数は回し切っているはず)
        for(int j = 0; j < N; j++) if(R[j] < 0) ok = false;
        if(!ok) break;
        //Bの個数を考える。
        for(int j = 0; j < N; j++){
        //0の部分は考慮しない。
            if(B[j] == 0) continue;
            //Bの最小値を考える。
            y = min(y,R[j]/B[j]); 
        }
        //回答の更新
        ans = max(ans,i+y);
    }

    cout << ans << endl;
    return 0;
}