AtCoder abc267 参加メモ

NEC Programming Contest 2022 (AtCoder Beginner Contest 267) - AtCoder

B - Split?

  • 1番のピンが立っていたらNo
  • 各レーンで1本でもピンが立っているレーン番号の集合を取る
  • ピンが立っているレーン番号を昇順にみていって間が空いていたらYes
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

const vector<vector<int>> g = { { 6 }, { 3 }, { 1,7 }, { 0,4 }, { 2,8 }, { 5 }, { 9 } };
const int l = g.size();

int main() {
  string s; cin >> s;
  if (s[0] == '1') { cout << "No" << endl; return 0; }

  vector<int> on;
  REP(i,l) for(int v: g[i]) {
    if (s[v] == '1') { on.push_back(i); break; }
  }

  bool ok = false;
  int last = -1;
  for(int v: on) {
    if (last == -1) last = v;
    if (v - last > 1) ok = true;
    last = v;
  }

  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

C - Index × A(Continuous ver.)

  1. 配列aの累積和を取っておく
  2. 0からmまでの連続部分列を計算しておく
  3. 1から1+mまでの連続部分列の計算は差分を取っていく。2で求めた値に、0〜mの累積和を引いて、a[1]*m を足すことで求められる
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'
using ll = long long;

int main() {
  int n,m; cin >> n >> m;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];

  vector<ll> ac(n+1); // 累積和
  REP(i,n) ac[i+1] = ac[i] + a[i];

  ll now = 0;
  REP(i,m) now += a[i] * (i+1);
  ll ans = now;
  for(int i = 1; i < n-m+1; i++) {
    now -= ac[i+m-1] - ac[i-1];
    now += a[i+m-1] * m;
    ans = max(ans,now);
  }

  cout << ans << endl;
  return 0;
}

D - Index × A(Not Continuous ver.)

  • dpする。dp[i][j] := i番目までみたときにj個選んだときの最大値
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'
using ll = long long;
const ll LINF = numeric_limits<ll>::max();

int main() {
  ll n,m; cin >> n >> m;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];

  vector<ll> dp(m+1, -LINF);
  dp[0] = 0;
  REP(i,n) {
    vector<ll> p(m+1, -LINF);
    p[0] = 0;
    swap(dp,p);

    REP(j,m) {
      if (p[j] == -LINF) continue;
      dp[j+1] = max(p[j+1], p[j] + a[i] * (j+1));
    }
  }

  cout << dp[m] << endl;
  return 0;
}