0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

ABC048 ARC064 の問題を解いてみました

Last updated at Posted at 2023-12-31

A問題

素直に "A" と sの一文字目 と "C" を出力すればよいです。

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

int main(void){
  string a, s, c;
  cin >> a >> s >> c;
  
  printf("A%cC", s[0]);
}

B問題

制約が大きいので、愚直に実装していては TLE になってしまいます。
なので、高速に処理をする方法を考えましょう。

もし、$n$ が $x$ で割り切れる場合は、$x$ が 0から数えたときの約数の何番目かを返し、割り切れない場合は $x$ に最も近い、 $x$ 以下の約数が何番目かを返す 関数func を実装します。
つまりは、関数func は $0$以上$n$以下の整数のうち、$x$ で割り切れるものの個数を返します。

累積和のような考え方で、
$0$以上$b$以下の整数のうち、$x$ で割り切れるものの個数 から、
$0$以上$a - 1$以下の整数のうち、$x$ で割り切れるものの個数 を引くことによって、
$a$以上$b$以下の整数のうち、$x$ で割り切れるものの個数 を求められます。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
long long a, b, x;
long long func(long long n){
  if(n < 0) return 0; // n = -1 の場合に対応する
  return n / x + 1;
}

int main(void){
  cin >> a >> b >> x;
  
  cout << func(b) - func(a-1) << endl;
  // a = 0 のとき、 func(-1) が実行される
}
他の正答例
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  long long a, b, x;
  cin >> a >> b >> x;
  
  a = (a + x - 1) / x; // a 以上の x の約数
  b = b / x; //b 以下の x の約数
  
  cout << b - a + 1 << endl;
}

C問題

$a_i + a_{i+1} \leqq x$ が成り立つかどうかを判定して、成り立たない場合は 成り立つように $a_{i+1}$ の値を減らせば正解できます。
$a_{i+1}$ の値を減らすのは、その影響で $a_{i+2}$ の値を減らす回数を減らせる可能性があるからです。

また、$a_1$ の値が $x$ よりも大きい場合は、 $a_1$ の値を $x$ にする必要があるので、そこにも気をつけてください。

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

int main(void){
  int n, x;
  cin >> n >> x;
  int a[n];
  for(int i = 0; i < n; i++) cin >> a[i];
  long long ans = 0;
  
  if(a[0] > x){ // 最初の箱への処理
    ans += a[0] - x;
    a[0] = x;
  }
  for(int i = 0; i < n - 1; i++){ //それ以外の箱への処理
    if(a[i] + a[i+1] > x){
      ans += a[i] + a[i+1] - x; 
      a[i+1] -= a[i] + a[i+1] - x;
    }
  }
  cout << ans << endl;
}

D問題

このゲームが終了するときには、文字列の形は

  • abababa
  • ababab

のどちらかの形になります。
そして、文字列の両端は取り除けないので、両端が同じ文字なら上の形で、そうでなければ下の形 で終了するということがわかります。
そして、上の形なら 終了するときの文字列の長さは 奇数で、
下の形なら 終了するときの文字列の長さは 偶数 です。

消せる文字数は、$開始時の文字列の長さ - 終了時の文字列の長さ$ で求められます。

消せる文字の個数が奇数なら、先手が勝利して、 偶数なら 後手が勝利します。

引き算は、引く数と引かれる数 のどちらかが奇数ならば、答えも奇数になります。

元の文字列の長さが奇数なら、開始時の文字列の長さは奇数になります。(当たり前)
文字列の最初と最後の文字が同じなら、終了時の文字列の長さは奇数になります。
どちらかが成り立てば、計算結果が奇数になります。

つまり、

  • $S$ の長さが偶数
  • $S$ の最初と最後の文字が同じ

のどちらかが成り立つ場合は、後手が勝利して、そうでなければ先手が勝利します。

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

int main(void){
  string s;
  cin >> s;
  int ans = 0;
  
  if(s.size() % 2 == 0) ans++;
  // 文字列の長さを確かめる
  
  int last = s.size() - 1;
  if(s[0] == s[last]) ans++;
  //最初と最後の文字が同じか確かめる
  
  if(ans == 1){ //片方が成り立つなら
    cout << "Second" << endl;
  }
  else{
    cout << "First" << endl;
  }
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?