見出し画像

アルゴリズム道中記〜20240405, ABC346〜

貝時計 KAITOKEI



A問題 Adjacent Product

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep (i, 0, N) 
  {
    cin >> A[i];
  }
  rep (i, 0, N-1)
  {
    cout << A[i] * A[i+1] << " ";
  }
}

B問題 Piano

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
using namespace std;
using ll = long long;

int main() {
  ll W, B;
  const string base = "wbwbwwbwbwbw";
  string piano = "";
  rep (i, 0, 100)
  {
    piano = piano + base;
  }
  cin >> W >> B;
  rep (i, 0, piano.length() - (W + B))
  {
    int w = 0, b = 0;
    rep (k, i, i + W + B)
    {
      if (piano[k] == 'w') w++;
      if (piano[k] == 'b') b++;
    }
    if (W == w and B == b)
    {
      print("Yes");
      return 0;
    }
  }
  print("No");
  return 0;
}

「無限」とありましたが、WとBの定義域が100以下でしたので、ベースとなる文字列を適当な数だけ連結して、そのなかで単純なループを回して部分文字列を検索しました。DPやなんかのもっと良い方法があるかもしれません。

C問題 Σ

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
using namespace std;
using ll = long long;

int main() {
  ll N, K, sum, ans = 0;
  cin >> N >> K;
  sum = (K * (K + 1)) / 2;
  map<ll, bool> ks;
  rep (i, 0, N)
  {
    ll a;
    cin >> a;
    if (a <= K and not ks.count(a)) 
    {
      sum -= a;
      ks[a] = true;
    }
  }
  print(sum);
}

mapの使い方を忘れていました。keyの検索には、countメソッドを使うと楽ですね。


この記事が気に入ったらサポートをしてみませんか？