AtCoder arc138 メモ

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138） - AtCoder のメモ

A - Larger Score

dp配列へ dp[i] = a[i]〜a[n-1] の中で最小の値 を事前に持っておく。 a[k]〜a[n-1] の値を、それぞれ最小で何回入れ替えることでs+1に以上にできるかを見ていく。 このとき a配列の最小値 == a[i] の場合は明らかに s+1 にできないので無視する。 最小で何回入れ替えることができるかは、dp配列が単調減少になっているため二分探索で求めることができる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9+5;

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

  int mn = INF;
  REP(i,k) mn = min(mn, a[i]);

  vector<int> dp(k);
  dp[k-1] = a[k-1];
  for(int i = k-2; 0 <= i; i--) dp[i] = min(a[i], dp[i+1]);

  int ans = INF;
  for(int i = k; i < n; i++) {
    if (a[i] <= mn) continue;

    int ok = 0, ng = k;
    while(abs(ok-ng) > 1) {
      int mid = (ok+ng)/2;
      if (dp[mid] < a[i]) ok = mid;
      else ng = mid;
    }
    ans = min(ans, i-ok);
  }

  cout << (ans == INF ? -1 : ans) << endl;
  return 0;
}

B - 01 Generation

配列Aから逆の操作をしてN回分操作可能であれば Yes。

先頭と末尾の要素を操作するため、dequeを使う(配列A要素をdequeに入れる) dequeから先頭と末尾の要素を取り出し、flipフラグが立っていればflipさせておく。 末尾が0であれば末尾をトル。末尾が1であれば、先頭が0のとき先頭の0を取り、flipフラグをxorする。それ以外のケースでは不可能なため No を出力する。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)

int main() {
  int n; cin >> n;
  deque<int> d;
  REP(i,n) {
    int a; cin >> a;
    d.push_back(a);
  }

  int flip = 0;
  REP(i,n) {
    int bk = d.back() ^ flip;
    int fr = d.front() ^ flip;

    if (bk == 0) {
      d.pop_back();
    } else if (fr == 0) {
      d.pop_front();
      flip ^= 1;
    } else {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}