ABC055 ARC069 の問題を解いてみました

A問題

もらえる金額を考えずに、まずは払う金額を掛け算で先に計算します。
その後、貰える金額も計算することによって、この問題は解くことができます。

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

int main(void){
  int n;
  cin >> n;
  int ans = n * 800; //払う金額を計算
  ans -= n / 15 * 200; //貰う金額を計算
  cout << ans << endl;
}

B問題

この問題は $N!$ を計算するという問題です。
繰り返しで計算しましょう。

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

int main(void){
  int n;
  cin >> n;
  long long ans = 1;
  for(int i = 1; i <= n; i++){ //階乗を計算する
    ans *= i;
    ans %= 1000000007;
  }
  cout << ans << endl;
}

C問題

S は、Scc を作るためにしか使えないので、Scc を優先的に作っていきます。
その後に、c が余ったなら、c4つ で Scc を作ります。

上の手順でできた Scc の数を出力すれば良いです。

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

int main(void){
  long long n,m;
  cin >> n >> m;
  long long ans = 0;
  
  ans += min(n, m / 2);
  //S,cのどちらかがなくなるまで、Scc をとりあえず作る
  n -= ans;   
  m -= ans * 2;
  //上の手順で使った S,c の数を減らす
  
  ans += m / 4;
  //余った c で Scc を作る
  
  cout << ans << endl;
}

D問題

$i - 2$ 番目と、 $i - 1$ 番目の動物の種類がわかっていれば、$i$ 番目の動物の種類が特定できます。

• $i-1$ 番目の動物が羊で、その羊が o と答えたなら $i$番目の動物は、$i-2$番目の動物と同じ種類になります。
• $i-1$ 番目の動物が羊で、その羊が x と答えたなら $i$番目の動物は、$i-2$番目の動物と違う種類になります。
• $i-1$ 番目の動物が狼で、その狼が o と答えたなら $i$番目の動物は、$i-2$番目の動物と違う種類になります。
• $i-1$ 番目の動物が狼で、その狼が x と答えたなら $i$番目の動物は、$i-2$番目の動物と同じ種類になります。

つまりは、連続した二つの動物の種類さえわかっていれば、他の動物の種類もわかるということです。

連続した二つの動物の種類の 羊と羊, 羊と狼, 狼と羊, 狼と狼 という組み合わせを試して、矛盾が発生するかを調べます。
もし、矛盾が発生しない方法があるならば、その方法を出力して、
そうでなければ -1 を出力します。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
string a[4] = {"SS", "SW", "WS", "WW"};
//隣り合う動物の並びすべて

int main(void){
  int n;
  string s, t;
  cin >> n >> s;
  
  for(int i = 0; i < 4; i++){ // 4通り試す
    t = a[i]; //動物の組み合わせ
    
    for(int j = 2; j < s.size(); j++){ //動物の種類を決めていく
      if(t[j-1] == 'S'){ //j番の動物が羊なら
        if(s[j-1] == 'o'){ //j番の動物の両端が同じなら
          t += t[j-2];
          // j-1 番の動物 == j+1 番の動物
        }
        else{ //j番の動物の両端が違うなら
          if(t[j-2] == 'S') t += "W";
          else t += "S";
          // j-1 番の動物 != j+1番の動物
        }
      }
      else{ //j番の動物が狼なら
        if(s[j-1] == 'x'){ //j番の動物の両端が同じなら
          t += t[j-2];
        }
        else{ //j番の動物の両端が違うなら
          if(t[j-2] == 'S') t += "W";
          else t += "S";
          //j-1 番の動物 != j+1番の動物
        }
      }
    }
    //矛盾が生じていないのか確かめる
    bool ok = true;
    if(t[n-1] == 'S'){ //最後の動物が羊なら
      if(s[n-1] == 'o'){ //最後の動物の両端が同じなら
        if(t[n-2] != t[0]) ok = false;
        //矛盾が生じているなら
      }
      else{ //最後の動物の両端が違うなら
        if(t[n-2] == t[0]) ok = false;
        //矛盾が生じているなら
      }
    }
    else{ //最後の動物が狼なら
      if(s[n-1] == 'x'){ //最後の動物の両端が同じなら
        if(t[n-2] != t[0]) ok = false;
        //矛盾が生じているなら
      }
      else{ //最後の動物の両端が違うなら
        if(t[n-2] == t[0]) ok = false;
        //矛盾が生じているなら
      }
    }
    if(t[0] == 'S'){ //最初の動物が羊なら
      if(s[0] == 'o'){ //最初の動物の両端が同じなら
        if(t[n-1] != t[1]) ok = false;
        //矛盾が生じているなら
      }
      else{ //最初の動物の両端が違うなら
        if(t[n-1] == t[1]) ok = false;
        //矛盾が生じているなら
      }
    }
    else{ //最初の動物が狼なら
      if(s[0] == 'x'){ //最初の動物の両端が同じなら
        if(t[n-1] != t[1]) ok = false;
        //矛盾が生じているなら
      }
      else{ //最後の動物の両端が違うなら
        if(t[n-1] == t[1]) ok = false;
        //矛盾が生じているなら
      }
    }
    
    if(ok){ //矛盾が生じていないなら
      cout << t << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}