CF 375 div2

今回も反省文オンリー。にしようと思ったけどコードも少し貼った。

　systest前だけど２完で2000位とかだった。
　C,Dともに解法は自明だけど実装でつまづくタイプで、案の定実装で死んだ。
　こういう問題苦手だし解いてもあんまり面白くないので、次回以降実装ゲー回は即撤退というのもありかもしれない。
　レート激落ちしそうで辛いなあ。

最近のAtCoderとかで出る地頭って感じの問題やSRM系の問題も苦手なんだけど、実装ゲーもまた苦手なので弱る。
　じゃあ何が解けるのかというと典型DPや有名アルゴリズムを使う問題しかない気がする。悲しい。

[追記]
　Cは、解き方は問題そのままって感じだからそのへんの方針は間違っていないんだけど、実装の方針がバグの原因だったっぽい。

　僕は大きい方から順に処理しようとしていたんだけど、これだと偶奇の場合分けが必要で面倒になる。
　あとは配るのと貰うのもいっぺんにやるのもちょっとアレだったかな。

　アルゴリズムの方針が違ってハマるのは、これはコンテストにおける正統的敗北なので諦めという感じなのだが、実装でハマるのはなんかこう、もにょるので、コンテストを楽しむためにも実装をもう少し練習せにゃあかん、という気がする。

[さらに追記]
　Dは湖を半分にして数を増やすクエリがありうる、と誤読していた。
　減らすだけならかなり簡単だしもはや実装が難しくもない。
　つらい……。

屈辱を忘れないために、コードを貼ることにした。
C（提出してWAしたもの）

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    for(int& x : a) {
        cin >> x;
        --x;
    }
    if(N == 1) {
        if(a[0] == 0)
          cout << 1 << ' ' << 0 << endl;
        else
          cout << 1 << ' ' << 1 << endl;
        cout << 1 << endl;
        return 0;
    }
    if(M == 1) {
        int ans = 0;
        for(int x : a) if(x > 0) ans++;
        cout << N - ans << ' ' << ans << endl;
        for(int _ : in(N)) cout << 1 << ' ';
        cout << endl;
        return 0;
    }
    vector<int> bucket(M + 1, 0);
    for(int x : a) {
        if(x < M)
          bucket[x]++;
        else
          bucket[M]++;
    }
    int ans = N / M;
    int maxNum = (N % M == 0) ? ans : ans + 1;
    vector<vector<int>> wariate(M + 1);
    set<pair<int, int>> deq;
    for(int i : in(M)) 
      deq.emplace(bucket[i], i);

    int valE = maxNum - 1;
    if(N % M == 0) valE++;
    int max_maxE = N % M;
    int maxEplus = 0, sum = 0;
    bool upd = false;
    
    while(true) {
        auto en = deq.end();
        --en;
        if(en->first > maxNum) {
            auto be = deq.begin();
            wariate[en->second].emplace_back(be->second);
            ++sum;
            pair<int, int> ne1(en->first - 1, en->second);
            pair<int, int> ne2(be->first + 1, be->second);
            deq.erase(en); deq.erase(be);
            deq.emplace(ne1); deq.emplace(ne2);
        }
        else if(en->first == maxNum) {
            int cnt = 0;
            for(auto p : deq)
              if(p.first == maxNum)
                cnt++;
            if(N % M) {
                int opeNum = cnt - max_maxE;
                if(opeNum > 0)  for(int i : in(opeNum)) {
                    auto be = deq.begin(), en2 = deq.end();
                    en2--;
                    wariate[en2->second].emplace_back(be->second);
                    ++sum;
                    pair<int, int> ne1(en2->first - 1, en2->second);
                    pair<int, int> ne2(be->first + 1, be->second);
                    deq.erase(en2); deq.erase(be);
                    deq.emplace(ne1); deq.emplace(ne2);
                }
                if(opeNum < 0) maxEplus -= opeNum;
            }
            upd = true;
            break;
        }
        else
          break;
    }
    if(upd == false) {
        maxEplus = max_maxE;
    }
    for(auto& p : deq) {
        if(p.first <= valE) {
            int num = valE - p.first;
            if(maxEplus > 0) {
                num++;
                maxEplus--;
            }
            if(num > 0)
              for(int i : in(num)) {
                  wariate[M].emplace_back(p.second);
                  ++sum;
              }
        }
    }
    cout << ans << ' ' << sum << endl;
    for(int x : a) {
        if(x >= M) x = M;
        if(wariate[x].size() > (size_t)(0)) {
            cout << wariate[x].back() + 1 << ' ';
            wariate[x].pop_back();
        }
        else
          cout << x + 1 << ' ';
    }
    cout << endl;
    return 0;
}

どう考えても場合わけが多すぎるクソ解法。

解き直したC

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    for(int& x : a) {
        cin >> x;
        --x;
    }
    vector<int> bucket(M, 0);
    for(int x : a) {
        if(x < M)
          bucket[x]++;
    }

    int ans = N / M;
    int cnt = 0;
    for(int i : in(M)) {
        while(bucket[i] < ans) {
            for(int j : in(N))
              if(a[j] >= M || bucket[a[j]] > ans) {
                  if(a[j] < M) --bucket[a[j]];
                  ++bucket[i];
                  a[j] = i;
                  cnt++;
                  break;
              }
        }
    }
    cout << ans << ' ' << cnt << endl;
    for(int x : a) cout << x + 1 << ' ' ;
    cout << endl;
    return 0;
}

D

class in {struct my_iterator{int it;const bool rev;explicit constexpr my_iterator(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(my_iterator& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const my_iterator i,n;public:explicit constexpr in(int n):i(0),n(n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const my_iterator& begin(){return i;}const my_iterator& end(){return n;}};

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int H, W, N;
int used[51][51];
vector<string> fld;
const int INF = 1e7;
int cnt = 0;
int dfs(int y, int x, int num) {
    used[y][x] = num;
    int res = 1;
    for(int i : in(4)) {
        int nx = x + dx[i], ny = y + dy[i];
        if(ny < 0 || nx < 0 || ny >= H || nx >= W) {
            res += INF;
            continue;
        }
        if(used[ny][nx] != -1) continue;
        if(fld[ny][nx] == '.')
          res += dfs(ny, nx, num);
    }
    return res;
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> H >> W >> N;
    fld.resize(H);
    for(int i : in(H)) cin >> fld[i];
    memset(used, -1, sizeof(used));
    int lakeNum = 0;
    vector<pair<int, int>> lakeSize;
    for(int i : in(H))
      for(int j : in(W))
        if(used[i][j] == -1 && fld[i][j] == '.') {
            int tmp = dfs(i, j, ++lakeNum);
            if(tmp >= INF) continue;
            lakeSize.emplace_back(tmp, lakeNum);
        }
    sort(lakeSize.begin(), lakeSize.end());
    int K = (int)lakeSize.size() - N;
    int sum = 0;
    for(int i : in(K)) {
        sum += lakeSize[i].first;
        for(int y : in(H)) for(int x : in(W))
          if(used[y][x] == lakeSize[i].second)
            fld[y][x] = '*';
    }

    cout << sum << endl;
    for(auto s : fld)
      cout << s << endl;
    return 0;
}

D、INFを返す実装で若干つまずいたくらいで本当に難しくないし、ノードに番号を振るという方針も良かった。
実装ミスと誤読が痛い。

レートは痛恨の-63。まあ、水色にならなかっただけマシか……。

[3度目の追記]
実はCも誤読していて、最初のはバグで落ちるんだと思っていたけどどうやら嘘解法だったようだ。