【備忘録】AtCoder Beginner Contest 378 －B

問題

AtCoder 市では、
N 種類のゴミを定期的に収集しています。
i(=1,2,…,N) 種類目のゴミは、日付を q iで割ったあまりが r iの日に収集されます。
Q 個の質問に答えてください。j(=1,2,…,Q) 番目の質問では、d j日に t j種類目のゴミが出たときに、次にそれが収集される日を答えてください。
ただし、i 種類目のゴミが出た日が、 i 種類目のゴミが回収される日であった場合、そのゴミは同じ日に収集されるとします。

制約
1≤N≤100
0≤ri<qi≤10^9
1≤Q≤100
1≤tj≤N
1≤dj≤10^9
入力はすべて整数

入力
2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

出力
3
3
10
17
10

出典：https://atcoder.jp/contests/abc378/tasks/abc378_b

方針

問題文の意味が分からないので入力と出力から求められていることを理解する

入力を考える
2種類のゴミがある
1種類目のゴミは7で割って3余る日に回収される
2種類目のゴミは4で割って2余る日に回収される
5個の質問がある
1種類目のゴミが1日目以降に回収される日はいつか
1種類目のゴミが3日目以降に回収される日はいつか
1種類目のゴミが4日目以降に回収される日はいつか
1種類目のゴミが15日目以降に回収される日はいつか
2種類目のゴミが7日以降に回収される日はいつか

出力を考える
5個の質問への解答
0<=x<=30;
1<=7x + 3 = 3
3<=7x + 3 = 3
4<=7x + 3 = 10
15<=7x + 3 = 17
7<=4x +2 = 10

上記の方針をとりあえずコードに起こす

コード

atcorder b.cpp

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

int main(){
 int n = 0;
 cin >> n;
 
 
 vector<int> waru(n);//割る数とあまりの数を受け取る
 vector<int> amari(n);//種類が多いので配列で受け取る
 
 for(int i = 0;i < n;i++){
   cin >> waru[i];
   cin >> amari[i];
 }

 //質問の回数分答えを出力させたいのでquestionを宣言する
 int question = 0;
 cin >> question;

 //質問で聞かれるごみの種類を受け取るための変数
 int syurui = 0;
 //何日目以降でゴミを初めて捨てたいのか受け取るための変数
 int nichimeikou = 0;

 //質問の回答を出力するための処理
 for(int i =0;i<question;i++){
   cin >> syurui >> nichimeikou;//ゴミの種類と何日目以降で捨てたいか受け取る
   //jを0から片っ端から調べてnichimeikou<=割る数*j + 余りが成り立った瞬間
   //ループ抜けて日にちを返す
    for(int j = 0;j<30;j++){
      int hinichi = waru[syurui-1]*j+amari[syurui-1];
      if(nichimeikou<=hinichi){
         cout << hinichi << endl;
         break;
      }
    }
 }
 
}

WAです😊

なぜWAなのか

Github Copilot

問題を解決するためには、ゴミの収集日を正確に計算する必要があります。現在のコードは、30日間の範囲内での収集日を繰り返し計算していますが、これは必ずしも正しいアプローチではありません。

次に収集される日を計算するためには、以下のように修正します：

現在の日付が収集日に該当する場合、その日付を返す
それ以外の場合、次の収集日を計算して返す

copilot b.cpp

    for(int i = 0; i < question; i++){
        int syurui = 0;
        int nichimeikou = 0;
        cin >> syurui >> nichimeikou;
        syurui--; // 0-indexedに変換
        int q = waru[syurui];
        int r = amari[syurui];
        
        // 現在の日が収集日と一致する場合
        if ((nichimeikou - r) % q == 0) {
            cout << nichimeikou << endl;
        } else {
            // 次の収集日を計算
            int next_collection_day = ((nichimeikou - r + q - 1) / q) * q + r;//謎の計算式????
            cout << next_collection_day << endl;
        }
    }

原因

日目以降の範囲が1~10^9なのでその範囲に対応ができていない
waru[syurui-1]*j+amarisyurui-1だと989,999,999日などに対応できないので
waru[syurui-1]*j+amari[syurui-1]の合計が10^9までになるようにループし続けると計算量が多くなるのでやめる

必要な知識

切り上げ除算
整数aとbが与えられたとき小数点以下を切り上げた整数を求めること
(a+b-1)/bで余りを切り上げた整数が出てくる
参考：B - Integer Division Returns 解説 by Nyaan
パターン
「特定の間隔で訪れる最小の数」や「周期的な条件を満たす最小の値を求める」時

改良後のコード

atcorder b.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
 int n = 0;
 cin >> n;
 
 
 vector<int> waru(n);//割る数とあまりの数を受け取る
 vector<int> amari(n);//種類が多いので配列で受け取る
 
 for(int i = 0;i < n;i++){
   cin >> waru[i];
   cin >> amari[i];
 }

 //質問の回数分答えを出力させたいのでquestionを宣言する
 int question = 0;
 cin >> question;

 //質問で聞かれるごみの種類を受け取るための変数
 int syurui = 0;
 //何日目以降でゴミを初めて捨てたいのか受け取るための変数
 int nichimeikou = 0;

 //質問の回答を出力するための処理
 for(int i =0;i<question;i++){
   cin >> syurui >> nichimeikou;
   int r = amari[syurui-1];
   int q = waru[syurui-1];
   //nichimeikouがすでに条件を満たしている場合余りを引いたら割り切れる
    if((nichimeikou-r)%q==0){
      cout << nichimeikou << endl;
    }else{
      //nichimeikouが条件を満たしていない場合
      cout <<((nichimeikou-r+q-1)/q)*q+r << endl;
    }  
 }
 
}

所感

問題文を読んでも何を求められているか全く想像ができなかったので入力と出力をなぞって問題文を理解した

切り上げ除算を使えばいいんだって似た問題を見ても出てこなそう

急いでいると変数がじいちゃんみたいになる

((nichimeikou-r+q-1)/q)*q+rこれが何がしたくてこんな式書いてるかは理解できない

ChatGpt

((nichimeikou-r+q-1)/q)*q+r
上記って何がしたくてこんな式書いてるんですか？

この式の目的は、「ある日 (nichimeikou) より後で、指定の周期 (q) と条件に合う収集日を求める」ことです。具体的には、nichimeikou 日以降で、日付 % q == r を満たす最小の 日付 を探しています。

以下、式の各部分が何をしているかを詳しく見ていきます。

1. nichimeikou - r の意味

nichimeikou - r は、nichimeikou を基準として「余り r を考慮したい日数差」を表現しています。具体的には、nichimeikou が q の周期で余り r に一致する状態を作り出すための基準値を作るためです。

2. (nichimeikou - r + q - 1) / q で切り上げ

次のステップでは、周期 q で割ることで、nichimeikou より後で条件に合う最小の q の倍数を見つけています。

• nichimeikou - r を q で割ると、どの周期の倍数に近いかがわかりますが、通常の除算では余りが切り捨てられてしまいます。
• q - 1 を加えることで、割り算結果を1つ大きい整数に「切り上げる」ことができます。この切り上げが、次の収集日を求めるために必要です。

3. ((nichimeikou - r + q - 1) / q) * q + r の全体の意味

• ((nichimeikou - r + q - 1) / q) * q は、条件を満たす次の収集日に最も近い q の倍数の日を求めています。
• + r を最後に追加することで、収集条件の余り r を考慮した正確な収集日になります。

例で確認

具体的な数字で考えるとわかりやすいです。

たとえば、q = 7、r = 3、nichimeikou = 10 の場合で見てみます。

1. nichimeikou - r = 10 - 3 = 7
2. nichimeikou - r + q - 1 = 7 + 7 - 1 = 13
3. (nichimeikou - r + q - 1) / q = 13 / 7 = 1（ここで整数部分のみを取り、余りは無視）
4. 1 * q + r = 1 * 7 + 3 = 10

これにより、10 日が次の収集日であると確認できました。

まとめ

この式全体としては、以下のことをしています：

• nichimeikou より後（または同じ）で、条件に合う最小の収集日を求めるために、切り上げ除算で次の周期に進めている

別の問題解いて何かつかめたら追記します