---
tags: Programming Contest
---

# Codeforces #662 (Div. 2) 題解

[題目連結](https://codeforces.com/contest/1393)

## 心得

久違地打 codeforces，然後狂掉 64 分，第三題解出來了，最後卡在沒開 long long，在 main test 倒數第二個測資被 hacked QQ。第一次看到在比賽開始後半小時內發了 3 個 announcements 來說明題意，由此可知敘述有夠難懂。我是不是被 AtCoder 寵壞了，受不了敘述這麼長的題目。在討論區[有人放了這圖](https://codeforces.com/blog/entry/81037?#comment-675778)，有笑到 XD


## A. Rainbow Dash, Fluttershy and Chess Coloring

我觀察到只看矩陣的左上部份時，主對角線一次只會有一格被填，這是 critical path。詳細來說，當 n 是奇數時，第一次填與最後一次填是同樣顏色，所以 critical path 是從左上角到中心點的長度 (n + 1) / 2；當 n 是偶數時，第一次填與最後一次是不同顏色，所以 critical path 是對角線長度 n / 2 再 + 1。

## B. Applejack and Storages

維護目前容器中：

1. 次數 >= 8 的有幾種數字 `has_8`
2. 次數 6 or 7 的有幾種數字 `has_6`
3. 次數 4 or 5 的有幾種數字 `has_4`
4. 次數 2 or 3 的有幾種數字 `has_2`

注意一種數字最多只會出現在其中一項。可行的情況有以下 5 種：

bool cond0 = has_8 >= 1;
bool cond1 = has_6 >= 2;
bool cond2 = has_6 == 1 and (has_4 >= 1 or has_2 >= 1);
bool cond3 = has_4 >= 2;
bool cond4 = has_4 == 1 and has_2 >= 2;

## C. Pinkie Pie Eats Patty-cakes

最小值最大化，標準二分搜的題目，問題是 check 怎麼寫。給定 shortest distance m，我們要判定 m 可不可行。我的方法是最優地去放數字，看能不能放成功。

所謂最優就是數字是 **週期性出現**（週期是 m + 1），且我優先放那些出現次數高的數字。假設某數字的出現次數是 `c`，且是第 `i` 高（最高=第 0 高，次高=第 1 高），那該數字要放的位置是等差數列 `(k - 1) * (m + 1) + i（1 <= k <= c）`

所謂能不能放成功，是指要放的那些位置必須 `< N`。實作上，針對每種數字，我只檢查他等差數列的最後一項，即 `(c - 1) * (m + 1) + i`。

好像這樣思考的人不多，看到不少人是用 priority queue 來實作 check，不明覺厲。

from collections import Counter

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    C = sorted(Counter(A).values(), reverse=True)

    def check(m):
        for i, c in enumerate(C):
            if (c - 1) * (m + 1) + i >= N:
                return False
        return True

    lb, ub = -1, N
    while ub - lb > 1:
        m = (lb + ub) // 2
        if check(m):
            lb = m
        else:
            ub = m
    return lb

TC = int(input())
for _ in range(TC):
    print(solve())

## D. Rarity and New Dress

[Maximum Size Square](https://leetcode.com/problems/maximal-square/) 的變形，請參我之前的[題解](https://hackmd.io/@amoshyc/HyMBdb3-v)。

這題就是稍為變化了一下。設 `dp[r, c]` 為「菱形的最下端點在 `(r, c)` 時，最大的菱形的邊長」。轉移來自 `(r - 1, c - 1)`, `(r - 1, c)`, `(r - 1, c + 1)`, `(r - 2, c)`，因為當 `dp[r, c] = L` 時，這四個位置的 `L - 1` 菱形都可以擴張變成位於 `(r, c)` 的 `L` 菱形。

最大正方形中的「都為 1」變成「跟 `A[r, c]` 是同樣數字」。dp 的初使值也不一樣，此題中，每個位置的 dp 都大於等於 1，所以初使化為 1。我們一樣透過「檢查 dp 值」來取代「檢查擴張的那些格子符不符合條件」。

將這個 dp 建好後，題目所求恰好是這個 dp 表格每項的和。以下給出使用 C++17 的 AC code，除了最簡化的轉移方程，另一種轉移方程在註解中。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll solve() {
    int N, M;
    cin >> N >> M;

    vector<string> A(N);
    for (int i =0; i < N; i++) {
        cin >> A[i];
    }

    auto dp = vector<vector<ll>>(N, vector<ll>(M, 1ll));
    for (int r = 2; r < N; r++) {
        for (int c = 1; c < M; c++) {
            if (A[r][c] != A[r - 1][c - 1] or A[r][c] != A[r - 1][c] or 
                A[r][c] != A[r - 1][c + 1] or A[r][c] != A[r - 2][c]) {
                continue;
            }

            dp[r][c] = max(dp[r][c], 
                min({
                    dp[r - 1][c - 1], dp[r - 1][c], 
                    dp[r - 1][c + 1], dp[r - 2][c]
                }) + 1
            );

            // ll L1 = dp[r - 1][c - 1];
            // ll L2 = dp[r - 1][c];
            // ll L3 = dp[r - 1][c + 1];
            // ll L4 = dp[r - 2][c];

            // if (L1 <= min({L2, L3, L4})) {
            //     dp[r][c] = max(dp[r][c], L1 + 1);
            // }
            // if (L2 <= min({L1, L3, L4})) {
            //     dp[r][c] = max(dp[r][c], L2 + 1);
            // }
            // if (L3 <= min({L1, L2, L4})) {
            //     dp[r][c] = max(dp[r][c], L3 + 1);
            // }
            // if (L4 <= min({L1, L2, L3})) {
            //     dp[r][c] = max(dp[r][c], L4 + 1);
            // }
        }
    }

    ll ans = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            ans += dp[r][c];
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << solve() << endl;
    return 0;
}

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::