競プロ日記

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n;
  cin >> n;
  vector a(n);
  rep (i, n) cin >> a[i];
  unordered_map<int, int> num;
  rep (i, n)++ num[a[i]];
  vector b;
  allrep (n, num) b.push_back(n.second);
  const int bn = b.size();
  sort(all(b));
  vector sumv(bn + 1);
  rep (i, bn) sumv[i + 1] = sumv[i] + b[i];
  unordered_map<int, int> large;
  rep (i, bn) large[b[i]] = i;
  unordered_map<int, int> k_max;
  int r = -1;
  rep1 (x, n) {
    if (large.find(x) != large.end()) r = large[x];
    int sum = sumv[r + 1] + x * (bn - r - 1);
    k_max[sum / x] = x;
  }
  vector ans(n + 1);
  int now = 0;
  rrep1 (i, n) {
    if (k_max.find(i) != k_max.end()) now = k_max[i];
    ans[i] = now;
  }
  rep1 (i, n) cout << ans[i] << "\n";
  return 0;
}

YouTubeの解説聞いてなるほどなーうーんうーんとなった問題。
数学的な話で言うとsnukeさんが解説してくれた数学的帰納法による証明はうんうんそうなるねって感じなのだが、感覚的に理解できていないような理解できているような。
一度に取る数Kを求めたいのに、取れる回数Tについて考えるというのが素直に受け入れられないからだと思う。

　数式や理論のみを理解できる
→同様の問題に対して、「この方針で解け」というような誘導があれば、その問題に合った形で解法を適応させて正解まで辿り着ける。
　感覚的に理解できる
→同様の問題に対して、誘導がなくとも自然な流れとして解法を頭に思い浮かべられる。

自分の中では理解度でこれくらいの差があると考えているため、基本的には感覚的に理解できるところまで持っていきたいのだが、なぜ回数を考える方向に持っていけるのかが理解できない。
いわゆる決め打ちして二分探索の仲間だと思うので、こういった問題が初めてだから仕方ない部分もあるとは思うが、自然な流れで回数を考える方向に持っていくには足りないものが多すぎる気がする。

回数で考えるという方針さえ理解してしまえば、後はデータの持ち方の問題だった。
愚直なO(N^2)の実装でTLEすることを確認し、累積和を使ったO(N)の実装でACできた。
方針のみ調べて、後は自力でACまで持っていけたのは成長ポイント。
特に、閉区間・半開区間をだいぶ使い分けられるようになったきたように思う。
右端-左端の値から-1する必要があるのかそのまま使えるのか、そういった部分を頭の中ですんなり解決できるようになってきたのは大きい。
最初は各種ライブラリも閉区間で実装していたのだが、途中から半開区間に変えて、便利さを強制的に理解実感していこうとしたのが生きている。