盆栽エンジニアリング日記

勉強したことをまとめるブログ

ABC162自分なりのまとめ

AtCoder C++ 競技プログラミング

ABC162自分なりのまとめ

ABC162に出題された問題について、自分なりの理解をまとめます。
今回は50分ほどで4完でしたがレートは落ちました。
やっぱり4完の場合は速解きできないと水色パフォーマンスは出ませんね。

A-Lucky-7

文字列に変換して、各桁に7が入っていないかを調べれば簡単です。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int n;
  cin >> n;
  string s = to_string(n);
  for(int i = 0; i < s.size(); i++)
  {
    if(s[i] == '7') {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

B-FizzBuzz Sum

1からNまで順番に見ていって、3と5で割り切れない値を足していけばいいです。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int n;
  cin >> n;
  ll result = 0;
  for(int i = 1; i <= n; i++)
  {
    if(i % 3 != 0 && i % 5 != 0)
    {
      result += i;
    }
  }
  cout << result << endl;
}

C - Sum of gcd of Tuples (Easy)

制約がk <= 200とゆるいので、愚直に3重ループを回してgcdをとっても間に合うと判断。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;


template <typename number>
pair<number, number> extended_euclid(number a, number b)
{
  number r0, r1, a0, a1, b0, b1;
  r0 = a; r1 = b;
  a0 = 1; a1 = 0;
  b0 = 0; b1 = 1;
  while (r1>0) {
    number q1 = r0 / r1;
    number r2 = r0 % r1;
    number a2 = a0 - q1 * a1;
    number b2 = b0 - q1 * b1;
    r0 = r1 ; r1 = r2;
    a0 = a1 ; a1 = a2;
    b0 = b1 ; b1 = b2;
  }
  number c = r0;
  a = a0; //x
  b = b0; //y
  return  {a, c};
}

int main()
{
  int k;
  cin >> k;
  ll result = 0;
  for(int i = 1; i <= k; i++)
  {
    for(int j = 1; j <= k; j++)
    {
      for(int l = 1; l <= k; l++)
      {
        if(i == 1 || j == 1 || l == 1){
          result++;
        }else{
          int temp = extended_euclid(i, j).second;
          temp = extended_euclid(temp, l).second;
          result += temp;
        }
      }
    }
  }
  cout << result << endl;
}

D - RGB Triplets

まず1つ目の条件である

  • Si != Sj && Si != Sk && Sj != Sk

を満たす組み合わせを数えることを考える。
愚直にやる場合は、3重ループを回せば見つかるが計算量的に間に合わないので高速化を考える。
文字種が2種類の場合は、ある添字iを見ているとき、iより後ろに別の文字種が何個あれば分かれば、O(1)で 組を計算することができる。
3種類の場合は、添字を2つ固定して同様のことを行えばよいので、R,G,B各種について累積和をとっておき 上記の計算を行うことで1つ目の条件を満たす組はO(n2)で計算可能。
次に2つ目の条件

  • j - i != k - j

を考える。 これは、i, j, kの幅を固定して探索することで添字1につきO(n)で1つ目と2つ目の条件を満たす組の個数を 計算することができる。
よって、各添字についてこの処理を行い、最初に求めた組数から引くことでO(n2)で1,2を満たす組の個数が 求まる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

void createA(string &s, v &target, char c){
  if(s[0] == c) target[0] = 1;
 var  for(inservice.Output
  {
    if(s[i] == c){
      target[i] = target[i - 1] + 1;
    }else{
      target[i] = target[i - 1];
    }
  }
}

int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  v r(n, 0);
  v g(n, 0);
  v b(n, 0);
  createA(s, r, 'R');
  createA(s, g, 'G');
  createA(s, b, 'B');
  ll result = 0;
  rep(i, n)
  {
    for(int j = i + 1; j < n; j++)
    {
      if(s[i] == s[j]) continue;
      if(s[i] == 'R'){
        if(s[j] == 'B') result += g[n - 1] - g[j];
        if(s[j] == 'G') result += b[n - 1] - b[j];
      }else if(s[i] == 'G'){
        if(s[j] == 'R') result += b[n - 1] - b[j];
        if(s[j] == 'B') result += r[n - 1] - r[j];
      }else if(s[i] == 'B'){
        if(s[j] == 'R') result += g[n - 1] - g[j];
        if(s[j] == 'G') result += r[n - 1] - r[j];
      }
    }
  }
  rep(i, n)
  {
    for(int radius = 1; radius < n; radius++)
    {
      if(i + radius > n || i + 2 * radius > n) continue;
      string temp;
      temp.push_back(s[i]);
      temp.push_back(s[i + radius]);
      temp.push_back(s[i + 2 * radius]);
      int tempr = 0;
      int tempg = 0;
      int tempb = 0;
      for(auto e : temp)
      {
        if(e == 'R') tempr++;
        if(e == 'G') tempg++;
        if(e == 'B') tempb++;
      }
      if(tempr == 1 && tempg == 1 && tempb == 1) result--;
    }
  }
  cout << result << endl;

}

E - Sum of gcd of Tuples (Hard)

解けなかった。
一歩目の考察はあっていたが、数え上げるフェーズで間違えた。
1~Kまでの数で長さNの数列を作るため、可能な組み合わせはKNとなり、全部試すのは不可能。
そこで、1~Kまでの数の中からある1つの数を選んで、何かできることはないか考えてみる。
すると、選んだ数をgcdにするような数列を数えることを思いつく。
そのような数列は、選んだ数をiとすると、すべての要素がiの倍数となっている数列となるので、k / iのN乗個存在する。
ここで注意しなければいけないのは、このような数え上げを行うと、gcdがiの倍数となるような数列が入り込んでしまう点。
この問題を解決するためにサイズKの配列memoを利用する。
具体的には、memoのi番目の要素にはiをgcdとするような数列の数を記憶する。
これを用いて数え上げをKから行うことで、k / iのN乗からiの倍数がgcdとなるような数列を取り除いていくことができる。
計算量としては、これは調和級数となるためO(k log k)となる。
べき乗の部分も高速べき乗法を用いることでO(log n)で済む。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

ll mod = 1e9 + 7;

ll mypow(ll a, ll n){
  ll x = 1;
  while(n > 0)
  {
    if(n & 1ll)
    {
      x = (x * a) % mod;
    }
    a = (a * a) % mod;
    n >>= 1;
  }
  return x;
}

int main()
{
  ll n, k;
  cin >> n >> k;
  vl memo(k + 1, 0);
  ll result = 0;
  for(ll i = k; i > 0; i--)
  {
    ll cand = k / i;
    memo[i] = mypow(cand, n);
    for(ll j = i + i; j <= k; j += i) memo[i] = (memo[i] - memo[j] + mod) % mod;
    ll temp = (memo[i] * i) % mod;
    result = (result + temp) % mod;
  }
  cout << result << endl;
}