---
# System prepended metadata

title: AGC032-B Balanced Neighbors
tags: [構築練習]

---

# AGC032-B Balanced Neighbors

## 問題情報

https://atcoder.jp/contests/agc032/tasks/agc032_b

diff: 1259

## 解法

$N$が偶数の時は

$(1, N), (2, N - 1), (3, N - 2), \dots$とペアを作り、この順にペアを円環につなげる。
- こうすることで、$S = 2(N + 1)$で構築できる

$N$が奇数の時は
$(N), (1, N - 1), (2, N - 2), \dots$として同様に円環につなげることでできる。
- $S = 2N$

## 提出コード

```cpp=
void Main() {
    i32 N; input(N);
    std::vector<std::vector<u32>> sets;
    if (N & 1) {
        sets.push_back(std::vector<u32>{});
        sets.back().push_back(N);
        N--;
    }
    for (i32 i{1} ; i < N ; i++) {
        sets.push_back(std::vector<u32>{});
        sets.back().push_back(i);
        sets.back().push_back(N);
        N--;
    }
    std::vector<std::pair<u32, u32>> E;
    for (u32 i{} ; i < sets.size() ; i++) {
        std::vector<u32> now{sets[i]}, nxt{sets[(i + 1) % sets.size()]};
        for (auto v : now) for (auto v2 : nxt) {
            E.emplace_back(v, v2);
        }
    }
    for (auto& e : E) if (e.first > e.second) std::swap(e.first, e.second);
    std::sort(E.begin(), E.end());
    E.erase(std::unique(E.begin(), E.end()), E.end());
    out(E.size());
    for (auto [u, v] : E) out(u, v);
}
```

## 反省会

かかった時間: 27分

今回は、急に天から解法が降ってきたので、本番で同じように閃きがでるとは思えない。うーーーん