ABC060 ARC073 の問題を解いてみました

今回から記事の書き方を変更していく予定です。

A問題

言われているとおりに判定しましょう。

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

int main(void){
  string a, b, c;
  cin >> a >> b >> c;
  
  //しりとりになっているか判定する
  if(a.back() == b.front() && b.back() == c.front()){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl; 
  }
}

B問題

まず、$A$の倍数は、いくつ足しても$A$の倍数です。
つまり、問題文は$B$で割ると$C$あまる$A$の倍数は存在するか、という問題に言い換えられます。

そして、少し考察をしてみると、$A$の倍数を$B$で割ったあまりは$B$個ごとに周期的に繰り返されているということがわかります。

具体例

$A = 5, B = 3$ とすると、

$A$ に 1 をかけたとき、あまりは 2
2 をかけたとき、あまりは 1
3 をかけたとき、あまりは 0
4 をかけたとき、あまりは 2
5 をかけたとき、あまりは 1

なので、$An \ (1 \leq n \leq B) ≡ C \pmod B$ となるような$n$が存在するかを確かめればよいです。

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

int main(void){
  int a, b, c;
  cin >> a >> b >> c;
  
  for(int i = 1; i <= b; i++){
    
    if(i * a % b == c){ //条件を満たすのか判定する
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

C問題

この問題では、$i$人目と$i+1$人目との間のお湯が出る時間について考えます。
入力例2を見てみます。

入力例2

2 4
0 5

この場合、1人目と2人目の間では、4秒お湯が出ています。

入力例1を見てみます。

入力例1

2 4
0 3

この場合、1人目がスイッチを押した3秒後に2人目がスイッチを押しているので、3秒しかお湯が出ていません。

これらのことから、$i$人目と$i+1$人目の間には、$min(T, t_{i+1} - t_i)$秒間お湯が流れるということがわかります。

なので、$min(T, t_{i+1} - t_i)$ の値を足していけば、答えが求まります。
($N$人目は、必ず$T$秒お湯が流れます)

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

int main(void){
  int N, T;
  cin >> N >> T;
  int t[N], ans = 0;
  for(int i = 0; i < N; i++) cin >> t[i];
  //入力受け取り
  
  for(int i = 0; i < N - 1; i++){
    ans += min(T, t[i+1] - t[i]);
  }
  ans += T;
  
  cout << ans << endl;
}

D問題