ABC052 ARC067 の問題を解いてみました

A問題

面積を比較しましょう。どちらの面積も同じ場合、どちらを出力してもok。

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

int main(void){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(a * b > c * d){ //面積の大きい方を出力(maxを使ってもいい)
    cout << a * b << endl;
  }
  else{
    cout << c * d << endl;
  }
}

B問題

もし、I が出現したら 変数に +1 して、
D が出現したら 変数に -1 して、
その変数の最大値を出力します。

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

int main(void){
  int n;
  string s;
  cin >> n >> s;
  int x = 0, ans = 0;
  
  for(int i = 0; i < n; i++){
    if(s[i] == 'I'){ // I なら +1
      x++;
    }
    else{ //D なら -1
      x--;
    }
    if(x > ans) ans = x; //最大値を記録
  }
  cout << ans << endl;
}

C問題

$N!$ の約数は、$N!$ の素因数からいくつか選んだものの積 で表せます。
そして、$N!$ の素因数は、$1$ から $N$ までの数の素因数の種類・個数の合計から求められます。

素因数の種類・個数 から 正の約数 の数を求めるには、
$それぞれの素因数の個数 + 1$ の積を求めればよいです。
なので、その結果を出力すればよいです。

(なぜそれで約数の数が求められるかは、下に書いています。)

入力例2

6

なら、1 ~ 6 を素因数分解して、

• $1$
• $2$
• $3$
• $2^2$
• $5$
• $2 \times 3$

となり、この結果から $6!$ を素因数分解すると、
$2^4 \times 3^2 \times 5$ と表せるとわかります。
そして、それぞれの素因数の個数 + 1 の積を求めれば良いので、
$(4 + 1) \times (2 + 1) \times (1 + 1) = 5 \times 3 \times 2 = 30$
で、入力例2 の答えは 30 だとわかります。

なぜ約数の数を求められるか

単純に、指数 の組み合わせが、 素因数の個数 + 1 個あるからです。 上の例では、30種類の約数があるとわかりましたが、 例えば 2 で説明すると、 $2^0,2^1,2^2,2^3,2^4$ で指数の組み合わせが 5 通りあるので、このような計算になります。

https://www.try-it.jp/chapters-4962/sections-4963/lessons-5000/

上のサイトで丁寧に説明してくれています。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
const long long MOD = 1000000007;

int main(void){
  int n;
  cin >> n;
  int prime[1010]; //素因数の個数を記録する配列
  for(int i = 0; i < 1000; i++) prime[i] = 0;
  
  for(int i = 2; i <= n; i++){
    int x = i;
    for(int y = 2; y * y <= i; y++){
      while(x % y == 0){
        prime[y]++;
        x /= y;
      }
      if(x == 1) break;
    }
    if(x != 1) prime[x]++;
  }
  // 2 ~ n の整数を素因数分解して、何がいくつあるかを記録しておく
  
  long long ans = 1;
  for(int i = 1; i <= 1000; i++){
    if(prime[i]){
      ans *= prime[i] + 1; //素因数の数 + 1 の積を求める
      ans %= MOD;
    }
  }
  cout << ans << endl;
}

D問題

この問題では、実は 隣の町に移動する と 隣の町にテレポートする 以外の行動を取る必要はありません。
なぜなら、隣の町に移動せずに、そのさらに先の街に移動しても、結局戻る手間が発生して、一度通った道をもう一度往復しなければならないからです。

なので、隣の町に移動する のと 隣の町にテレポートする で、疲労度が少なくなる方を選べばよいです。

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

int main(void){
  long long n, a, b;
  cin >> n >> a >> b;
  long long x[n];
  for(int i = 0; i < n; i++) cin >> x[i];

  long long ans = 0;
  for(int i = 0; i < n - 1; i++){
    long long cost = (x[i+1] - x[i]) * a;
    //歩きの疲労度を計算する
    
    ans += min(cost, b);
    //隣の町まで歩くか、テレポートするかの楽な方を選ぶ
  }
  cout << ans << endl;
}