ABC478を振り返る

皆様こんにちは！ばるとーくです！
今回はABC478の振り返りをしていこうと思います！

はじめに～結果～
各問題振り返り
終わりに～レート変動～

はじめに～結果～

2完でした...正直ガン萎えでしたねぇ
C問題惜しかった気がするんですけども！

各問題振り返り

A - Grapes

問題文
$1$ から $N$ までの番号がついた $N$ 人の人がいます。
$M$ 粒のぶどうがあります。これらを次のようにして $N$ 人に配ります。
人 $1,2,\dots,N$ の順に $1$ 粒ずつ配る。途中でぶどうがなくなったらその時点で終了する。
人 $N$ に配った後もまだぶどうが残っている場合は、人 $1$ に戻って再び順番に配る。これをぶどうがなくなるまで繰り返す。
各人が何粒のぶどうをもらうかを求めてください。
制約
$1 \leq N \leq 100$
$1 \leq M \leq 10000$
入力はすべて整数

A - Grapes

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

for文を使って，各人を模した配列に $+1$ しまくるだけです．
途中で配列の最後に行ってしまったら，配列の参照をはじめに戻します．そのために，配列参照用の now という変数を作っています．
A問題にしては難しい気もしますが...これはサクサクと～

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> ans(n);
  int now = 0;
  rep(i, 0, m) {
    ++ans[now];
    ++now;
    if (now >= n) {
      now = 0;
    }
  }

  rep(i, 0, n) {
    cout << ans[i] << " ";
  }
  cout << "\n";
  return 0;
}

B - Topping

問題文
高橋君はラーメン屋に来ています。
このラーメン屋では $N$ 種類のトッピングがあり、$i$ 番目のトッピングは価格が $i$、嬉しさが $W_i$ です。
高橋君は、価格の総和が $V$ 以下になるように相異なる $3$ 種類のトッピングを選びます。高橋君が選んだトッピングの嬉しさの総和の最大値を求めてください。
ただし、価格の総和が $V$ 以下になるように相異なる $3$ 種類のトッピングを選ぶ方法が $1$ 通り以上存在することが制約より保証されます。
制約
$3 \leq N \leq 100$
$6 \leq V \leq 3N-3$
$1 \leq W_i \leq 10^6$
入力はすべて整数

B - Topping

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

地味～に時間を食わされました...
嬉しさが大きい方から取れば？と思いましたが，それだと価格が考慮できないな～などと悩んだ結果，愚直に3重ループを書くことに
書くの久々すぎて戸惑いましたがね...

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, v;
  cin >> n >> v;
  vector<ll> w(n);
  ll ans = 0;

  rep(i, 0, n) {
    cin >> w[i];
  }

  rep(i, 0, n) {
    rep(j, i + 1, n) {
      rep(k, j + 1, n) {
        if (i + j + k + 3 <= v) {
          ans = max(ans, w[i] + w[j] + w[k]);
        }
      }
    }
  }

  cout << ans << "\n";
  return 0;
}

C - Sort Subarray

問題文
長さ $N$ の整数列 $A=(A _ 1,A _ 2,\ldots,A _ N)$ が与えられます。
$A$ に対して、次の操作をちょうど $\mathbf{1}$ 回行います。
$1$ 以上 $N-K+1$ 以下の整数 $i$ をひとつ選ぶ。$A _ i,A _ {i+1},\ldots,A _ {i+K-1}$ を昇順にソートする。より厳密には、$A _ i,A _ {i+1},\ldots,A _ {i+K-1}$ を小さいほうから順に並べたものを $B _ 1,B _ 2,\ldots,B _ K$ とし、$1\le j\le K$ について一斉に $A _ {i+j-1}$ を $B _ j$ で置き換える。
この操作ののち、$A$ が昇順になっている、つまりすべての $1\le i\lt N$ に対して $A _ i\le A _ {i+1}$ が成り立っているようにできるか判定してください。
制約
$1\le K\lt N\le2\times10 ^ 5$
$1\le A _ i\le N\ (1\le i\le N)$
入力は全て整数

C - Sort Subarray

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

多分今までで一番提出がぶっ飛んでる．
爆撃レベルで提出したんで．
私の考えとしては一貫してこうでした．

整列されてない連続部分の長さと $K$ を比べる?

これに付随して，「整列が必要な部分があまりにも離れすぎているとダメだよなぁ」と思い，初回提出がこちら

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, 0, n) {
    cin >> a[i];
  }
  int big = a[0];
  int len = 1;
  int maxlen = 0;
  int cnt = 0;
  int dist = 0;
  int maxdist = 0;
  rep(i, 1, n) {
    if (big > a[i]) {
      ++len;
      maxdist = max(dist, maxdist);
      dist = 0;
    } else {
      maxlen = max(len, maxlen);
      if (len > 1) {
        ++cnt;
        if (dist == 0) {
          dist = len;
        } else {
          ++dist;
        }
      }
      len = 1;
      big = a[i];
    }
  }

  maxlen = max(len, maxlen);
  if (len > 1) {
    ++cnt;
    if (dist == 0) {
      dist = len;
    } else {
      ++dist;
    }
  }

  if (maxlen <= k && (cnt == 1 || maxdist <= k)) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
  return 0;
}

しかしWAでした．問題は「左端の位置」だったようです．後ろの最小値が $A[i]$ より小さくなる最小の $i$ を探す必要があることに気づけず...
ACコードはこちら

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  vector<int> b(n);
  rep(i, 0, n) {
    cin >> a[i];
    b[i] = a[i];
  }

  sort(b.begin(), b.end());

  int min_i = n;
  int max_i = 0;
  rep(i, 0, n){
    if(b[i] != a[i]){
      min_i = min((int)i, min_i);
      max_i = max((int)i, max_i);
    }
  }

  if (max_i - min_i + 1 <= k) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
  return 0;
}

D - Range Set Insertion Query

問題文
$N$ 個の集合 $S _ 1,S _ 2,\ldots,S _ N$ があります。はじめ、$S _ 1,S _ 2,\ldots,S _ N$ はすべて空集合です。
これらの集合に対して、以下のような操作を $Q$ 回行います。$i$ 番目 $(1\le i\le Q)$ の操作では、整数の $3$ つ組 $(L _ i,R _ i,X _ i)$ が与えられ、以下の操作を行います。
$S _ {L _ i},S _ {L _ i+1},\ldots,S _ {R _ i}$ に対して、$X _ i$ を追加する。
すべての操作を終えたあとの $S _ i$ の要素数を、すべての $i=1,2,\ldots,N$ に対して求めてください。
制約
$1\le N\le2\times10 ^ 5$
$1\le Q\le2\times10 ^ 5$
$1\le L _ i\le R _ i\le N\ (1\le i\le Q)$
$1\le X _ i\le Q\ (1\le i\le Q)$
入力はすべて整数