# SCCP 2025/06/19 (ICPC2023 国内予選: 略解)
[当時の結果](https://icpc.jp/2023/domestic/results/)
[公式解説](https://storage.googleapis.com/files.icpc.jp/domestic2023/commentaries.html)
~10位: 6完以上
3チーム通過(25チーム): 早い4完
2チーム通過(40チーム): 3完最速レベル
1チーム通過(50チーム): 早い3完
会津大競プロ部の当時の記録は二チーム通過でどちらも4完でした。
Eの難易度はさほどでも無いが、B, C, Dが難しく時間が足りず4完というチームが多そう。F以降は激ムズ。
- 下剋上がしやすいセットであったと言える
## A - Which Team Should Receive the Sponsor Prize?
ICPC国内予選では、テストケースが陽に与えられない特殊(?)な入力形式が毎年採用されていた。今年からジャッジシステムが変更になるということで、この独特な入力形式が続投になるかは不明。ただ、慣れておいて損は無いだろう。
<details>
<summary>解法</summary>
(解答例)
```cpp=
#include <iostream>
#include <cmath>
int N, A[100];
int main() {
while (true) {
std::cin >> N;
if (N == 0) break; // 0は入力の終わり
for (int i = 0 ; i < N ; i++) std::cin >> A[i];
int ans = 0;
for (int i = 0 ; i < N ; i++) {
if (std::abs(A[i] - 2023) < std::abs(A[ans] - 2023)) {
ans = i;
}
}
ans++; // 1-indexedで出力するので+1する
std::cout << ans << '\n';
}
}
```
</details>
## B - Amidakuji
2024年のB問題と比較して露骨に難しい。$N \le 50, M \le 500$ と制約が小さいことに注目する。最良の計算量を目指さずとも、ある程度ナイーブな解法で良いので実装で苦労しない方針を選択することが大事。
<details>
下の解答例では、座標が明らかに変化しないような横線の引き方を除いた、全ての横線の引き方を$y$座標の昇順に調べている。$\Theta(N + M^2)$で動作する(ACには十分高速)。
(解答例)
```cpp=
#include <iostream>
#include <cassert>
int N, M, P, Q, X[500];
// 左からx本目の縦線、上からy本目の横線からはじめてQにたどり着くか?
bool reachQ(int x, int y) {
assert(1 <= x and x <= N);
assert(0 <= y and y <= M);
for (int i = y ; i < M ; i++) {
if (X[i] == x) x++;
else if (X[i] + 1 == x) x--;
}
return x == Q;
}
void solve() {
if (reachQ(P, 0)) { // 1本も横線を追加しないケース
std::cout << "OK\n";
return;
}
int current_x = P;
for (int y = 0 ; y <= M ; y++) { // y本の横線を通った後に一本追加する
if (current_x - 1 >= 1 and reachQ(current_x - 1, y)) { // 左に動くように横線を引く
std::cout << current_x - 1 << ' ' << y << '\n';
return;
}
if (current_x + 1 <= N and reachQ(current_x + 1, y)) { // 右に動くように横線を引く
std::cout << current_x << ' ' << y << '\n';
return;
}
if (y < M) { // 元からあるy本目の線を通る
if (X[y] == current_x) current_x++;
else if (X[y] + 1 == current_x) current_x--;
}
}
std::cout << "NG\n";
}
int main() {
while (true) {
std::cin >> N >> M >> P >> Q;
if (N == 0 and M == 0 and P == 0 and Q == 0) break;
for (int i = 0 ; i < M ; i++) std::cin >> X[i];
solve();
}
}
```
</details>
## C - Changing the Sitting Arrangement
パズルめいた問題であり、人によって得意苦手が大きく分かれるだろう。チームの中で**一番得意な人**が**一番長く取り組む**ことが重要になる。チームメイトの得意苦手は把握しておこう。
<details>
<summary>解法</summary>
解答例では以下のような方針を取っている
1. はじめに、横に隣り合っている人を**行内で並び替えるだけで**$\lfloor\frac{n}{2}\rfloor$以上離すようにする。
2. これは、偶数番目の人を左から順に詰める->奇数番目の人を順に詰めるとすることで達成できる
3. 同じことを縦でもする。この縦の移動では**横には移動しないので、横で隣り合う条件が違反してしまうことは無い**
(解答例)
```cpp=
#include <iostream>
#include <vector>
int N, A[50][50];
void solve() {
std::vector<int> go(N);
// 1, 3, 5, 7, .... -> 0, 1, 2, 3, ...
int cur = 0;
for (int i = 1 ; i < N ; i += 2) {
go[i] = cur;
cur++;
}
// 0, 2, 4, 6, ... -> N/2, N/2+1, ....
for (int i = 0 ; i < N ; i += 2) {
go[i] = cur;
cur++;
}
std::vector ans(N, std::vector<int>(N));
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < N ; j++) {
ans[go[i]][go[j]] = A[i][j];
}
}
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < N ; j++) {
std::cout << ans[i][j] << (j + 1 == N ? '\n' : ' ');
}
}
}
int main() {
while (true) {
std::cin >> N;
if (N == 0) break;
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < N ; j++) {
std::cin >> A[i][j];
}
}
solve();
}
}
```
</details>
## D - Efficient Problem Set
「上界・下界を与える」といった手法の問題。例えば以下のような例題がある。
- 順列が与えられるので、ソートするのに必要な隣接swapの最小回数を求めよ
- https://atcoder.jp/contests/arc119/tasks/arc119_b
<details>
<summary>解法</summary>
$1, 2, 4, 8, 16, \dots$ 点と余った点からなる問題セットは$0, 1, 2, \dots, N$点全部達成することが可能である。この問題セットは$O(\log N)$問から構成される。実際に構築してみると、$N = 100$では$1, 2, 4, 8, 16, 32, 37$点の$7$問で、確かに$0$点から$100$点まで全部構成できている。
- なんで全部達成できるのか？ -> 二進数表示を考えてみよう
つまり、$6$問以下で条件を全部満たすことができるか判定すれば良い。合計$N$点でかつ$6$問以下の問題セットを全探索すれば良い。
- 写像12相の「分割数」。前の課プロでやった[Stone XOR](https://atcoder.jp/contests/abc390/tasks/abc390_d)と同じように再帰関数を書くと全探索しやすい
下の解答例では、bitsetを用いて条件を満たすかの判定をちょっと高速化して、ダメ押ししている。(実装量も減っている)
```cpp=
#include <iostream>
#include <vector>
#include <bit>
#include <bitset>
#include <algorithm>
const int MAXN = 101;
using bitset = std::bitset<MAXN>;
int N, BOUND;
std::string S;
bitset S_BIT;
// num: 現在の問題セットの問題数
// sum: 現在の問題セットの満点
// max: 現在の問題セットで一番点数が高い問題の点数
// dp : 実現可能な点数
int dfs(int num, int sum, int max, const bitset& dp) {
if (num >= BOUND) return BOUND;
if (sum == N) {
if ((S_BIT | (S_BIT ^ dp)) == dp) {
return num;
}
else {
return BOUND;
}
}
int res = BOUND;
for (int i = max ; i <= N - sum ; i++) {
bitset next_dp = dp | (dp << i);
res = std::min(res, dfs(num + 1, sum + i, i, next_dp));
}
return res;
}
int solve() {
// 解は必ずBOUND以下
BOUND = std::bit_width((unsigned)N);
// std::bitsetのデフォルトコンストラクタは全部falseで初期化
S_BIT = bitset{};
for (int i = 0 ; i <= N ; i++) {
S_BIT[i] = S[i] == 'o';
}
bitset start{};
start[0] = 1;
return dfs(0, 0, 1, start);
}
int main() {
while (true) {
std::cin >> N;
if (N == 0) break;
std::cin >> S;
std::cout << solve() << '\n';
}
}
```
</details>
## E - Tempered Record
<details>
<summary>解法</summary>
$\text{dp}[i][j]$ を $i$ 人目まで条件を満たしながら $j$ 個の要素を変更して並べるとき、$i$ 人目の最高スコアとする。
$O(N^2)$
```cpp=
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
struct grade {
int morning = -1, afternoon = -1;
bool valid() const {
return morning != -1 and afternoon != -1;
}
};
bool operator==(const grade& p, const grade& q) {
return p.morning == q.morning and p.afternoon == q.afternoon;
}
// pがqより成績が良いか？(一緒も許容)
bool compare(grade p, grade q) {
if (p.afternoon != q.afternoon) return p.afternoon > q.afternoon; // 午後の成績
else if (p.morning != q.morning) return p.morning > q.morning; // 午前の成績
else return true; // 一緒の成績
}
void chmax(grade& p, grade q) {
if (compare(q, p)) p = q;
}
int N;
int solve() {
// dp[i][j] := 上からi人まで矛盾なく並べる方法であって、j個の要素を変更したときの最下位の最高スコア
std::vector<grade> dp(1, {N - 1, N - 1});
for (int i = 1 ; i <= N ; i++) {
std::vector<grade> next(2 * i + 1);
int X, Y;
std::cin >> X >> Y;
for (int j = 0 ; j < std::ssize(dp) ; j++) {
if (!dp[j].valid()) continue;
// 一つも変えないケース
if (compare(dp[j], {X, Y})) chmax(next[j], {X, Y});
// 午後を変えるケース
if (compare(dp[j], {X, dp[j].afternoon - 1})) chmax(next[j + 1], {X, dp[j].afternoon - 1});
if (compare(dp[j], {X, dp[j].afternoon})) chmax(next[j + 1], {X, dp[j].afternoon});
// 午前を変えるケース
if (compare(dp[j], {N - 1, Y})) chmax(next[j + 1], {N - 1, Y});
else if (compare(dp[j], {dp[j].morning, Y})) chmax(next[j + 1], {dp[j].morning, Y});
// 両方変えるケース
if (compare(dp[j], dp[j])) chmax(next[j + 2], dp[j]);
}
dp = std::move(next);
}
for (int i = 0 ; i < std::ssize(dp) ; i++) if (dp[i].valid()) {
return i;
}
assert(false);
return -1;
}
int main() {
while (true) {
std::cin >> N;
if (N == 0) break;
std::cout << solve() << '\n';
}
}
```
</details>
## F - Villa of Emblem Shape
<details>
<summary>解法</summary>
筆者は解説見ながら通しました。
多角形から凸包を構築します。最終的に作られる凸多角形はこの凸包に似た形になることがイメージできます。凸包の各辺について、両端点について、その点を被うように多角形の辺が存在するならばokです(ちょっとだけ平行移動したものを重ねまくることで凸包の辺を穴全部カバーできる)。
解答例 (main関数は450行付近にあります)
```cpp=
#include <bits/stdc++.h>
#include <cstdint>
#include <cstddef>
namespace zawa {
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using usize = std::size_t;
} // namespace zawa
#include <cassert>
namespace zawa {
namespace geometryZ2 {
using Zahlen = i64;
namespace internal {
constexpr i32 positive{1};
constexpr i32 zero{0};
constexpr i32 negative{-1};
} // namespace internal
constexpr i32 Sign(Zahlen value) {
if (value < 0) return internal::negative;
if (value > 0) return internal::positive;
return internal::zero;
}
constexpr bool Positive(Zahlen value) {
return Sign(value) == internal::positive;
}
constexpr bool Zero(Zahlen value) {
return Sign(value) == internal::zero;
}
constexpr bool Negative(Zahlen value) {
return Sign(value) == internal::negative;
}
constexpr Zahlen Abs(Zahlen value) {
return (value > 0 ? value : -value);
}
constexpr Zahlen Square(Zahlen value) {
return value * value;
}
} // namespace geometryZ2
} // namespace zawa
#include <algorithm>
#include <iostream>
#include <limits>
namespace zawa {
namespace geometryZ2 {
class Point {
private:
Zahlen x_{}, y_{};
static constexpr i32 origin{0};
static constexpr i32 firstQuadrant{1};
static constexpr i32 secondQuadrant{2};
static constexpr i32 thirdQuadrant{-2};
static constexpr i32 forthQuadrant{-1};
public:
/* constructor */
Point() = default;
Point(const Point& p) : x_{p.x()}, y_{p.y()} {}
Point(Zahlen x, Zahlen y) : x_{x}, y_{y} {}
/* getter setter */
Zahlen& x() {
return x_;
}
const Zahlen& x() const {
return x_;
}
Zahlen& y() {
return y_;
}
const Zahlen& y() const {
return y_;
}
/* operator */
Point& operator=(const Point& p) {
x() = p.x();
y() = p.y();
return *this;
}
Point& operator+=(const Point& p) {
x() += p.x();
y() += p.y();
return *this;
}
friend Point operator+(const Point& p0, const Point& p1) {
return Point{p0} += p1;
}
Point& operator-=(const Point& p) {
x() -= p.x();
y() -= p.y();
return *this;
}
friend Point operator-(const Point& p0, const Point& p1) {
return Point{p0} -= p1;
}
Point& operator*=(Zahlen k) {
x() *= k;
y() *= k;
return *this;
}
friend Point operator*(const Point& p, Zahlen k) {
return Point{p} *= k;
}
friend Point operator*(Zahlen k, const Point& p) {
return Point{p} *= k;
}
Point& operator/=(Zahlen k) {
assert(k);
assert(x() % k == 0);
assert(y() % k == 0);
x() /= k;
y() /= k;
return *this;
}
friend Point operator/(const Point& p, Zahlen k) {
return Point{p} /= k;
}
friend bool operator==(const Point& p0, const Point& p1) {
return p0.x() == p1.x() and p0.y() == p1.y();
}
friend bool operator!=(const Point& p0, const Point& p1) {
return p0.x() != p1.x() or p0.y() != p1.y();
}
friend bool operator<(const Point& p0, const Point& p1) {
if (p0.x() != p1.x()) return p0.x() < p1.x();
else return p0.y() < p1.y();
}
friend bool operator<=(const Point& p0, const Point& p1) {
return (p0 < p1) or (p0 == p1);
}
friend bool operator>(const Point& p0, const Point& p1) {
if (p0.x() != p1.x()) return p0.x() > p1.x();
else return p0.y() > p1.y();
}
friend bool operator>=(const Point& p0, const Point& p1) {
return (p0 > p1) or (p0 == p1);
}
friend std::istream& operator>>(std::istream& is, Point& p) {
is >> p.x() >> p.y();
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Point& p) {
os << '(' << p.x() << ',' << p.y() << ')';
return os;
}
/* member function */
Zahlen normSquare() const {
return Square(x()) + Square(y());
}
bool isNormSquareOver(Zahlen d) const {
assert(!Negative(d));
auto [mn, mx]{std::minmax({ Abs(x()), Abs(y()) })};
if (mx and mx > d / mx) {
return true;
}
long long s1{Square(mn)}, s2{Square(mx)};
if (s1 > d - s2) {
return true;
}
return false;
}
bool isNormSquareOverflow() const {
return isNormSquareOver(std::numeric_limits<Zahlen>::max());
}
i32 area() const {
if (x_ == 0 and y_ == 0) return origin;
if (x_ <= 0 and y_ < 0) return thirdQuadrant;
if (x_ > 0 and y_ <= 0) return forthQuadrant;
if (x_ >= 0 and y_ > 0) return firstQuadrant;
return secondQuadrant;
}
/* static member */
static bool ArgComp(const Point& p0, const Point& p1) {
if (p0.area() != p1.area()) return p0.area() < p1.area();
Zahlen cross{Cross(p0, p1)};
return (!Zero(cross) ? Positive(cross) : p0.normSquare() < p1.normSquare());
}
/* friend function */
friend Zahlen Dot(const Point& p0, const Point& p1) {
return p0.x() * p1.x() + p0.y() * p1.y();
}
friend Zahlen Cross(const Point& p0, const Point& p1) {
return p0.x() * p1.y() - p0.y() * p1.x();
}
};
using Vector = Point;
} // namespace geometryZ2
} // namespace zawa
#include <vector>
namespace zawa {
namespace geometryZ2 {
using PointCloud = std::vector<Point>;
void ArgSort(PointCloud& p) {
std::sort(p.begin(), p.end(), Point::ArgComp);
}
} // namespace geometryZ2
} // namespace zawa
namespace zawa {
namespace geometryZ2 {
enum RELATION {
// p0 -> p1 -> p2の順で直線上に並んでいる
ONLINE_FRONT = -2,
// (p1 - p0) -> (p2 - p0)が時計回りになっている
CLOCKWISE = -1,
// p0 -> p2 -> p1の順で直線上に並んでいる
ON_SEGMENT = 0,
// (p1 - p0) -> (p2 - p0)が反時計回りになっている
COUNTER_CLOCKWISE = +1,
// p2 -> p0 -> p1、またはp1 -> p0 -> p2の順で直線上に並んでいる
ONLINE_BACK = +2
};
RELATION Relation(const Point& p0, const Point& p1, const Point& p2) {
Point a{p1 - p0}, b{p2 - p0};
if (Positive(Cross(a, b))) return COUNTER_CLOCKWISE;
if (Negative(Cross(a, b))) return CLOCKWISE;
if (Negative(Dot(a, b))) return ONLINE_BACK;
if (a.normSquare() < b.normSquare()) return ONLINE_FRONT;
return ON_SEGMENT;
};
} // namespace geometryZ2
} // namespace zawa
#include <iterator>
#include <type_traits>
namespace zawa {
namespace geometryZ2 {
class Polygon {
private:
std::vector<Point> data_;
public:
usize size() const {
return data_.size();
}
/* constructor */
Polygon() = default;
Polygon(const Polygon& polygon) : data_{polygon.data_} {}
Polygon(const std::vector<Point>& data) : data_{data} {}
Polygon(usize n) : data_{n} {
assert(n >= static_cast<usize>(3));
}
/* operator */
Polygon& operator=(const Polygon& polygon) {
data_ = polygon.data_;
return *this;
}
Point& operator[](usize i) {
assert(i < size());
return data_[i];
}
const Point& operator[](usize i) const {
assert(i < size());
return data_[i];
}
friend std::istream& operator>>(std::istream& is, Polygon& polygon) {
for (size_t i{} ; i < polygon.size() ; i++) {
is >> polygon[i];
}
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Polygon& polygon) {
for (usize i{} ; i < polygon.size() ; i++) {
std::cout << polygon[i] << (i + 1 == polygon.size() ? "" : " ");
}
return os;
}
/* member function */
void reserve(usize n) {
data_.reserve(n);
}
void pushBack(const Point& p) {
data_.push_back(p);
}
void emplaceBack(Zahlen x, Zahlen y) {
data_.emplace_back(x, y);
}
template <class RandomAccessIterator>
void insert(usize n, RandomAccessIterator first, RandomAccessIterator last) {
assert(n <= size());
data_.insert(std::next(data_.begin(), n), first, last);
}
void orderRotate(usize i) {
assert(i < size());
std::rotate(data_.begin(), data_.begin() + i, data_.end());
}
template <class F>
void normalForm(const F& func) {
auto index{std::distance(data_.begin(), std::min_element(data_.begin(), data_.end(), func))};
orderRotate(index);
}
void normalForm() {
auto index{std::distance(data_.begin(), std::min_element(data_.begin(), data_.end()))};
orderRotate(index);
}
template <class F>
Polygon normalFormed(const F& func = [](const Point& a, const Point& b) -> bool { return a < b; }) const {
Polygon res{*this};
res.normalForm(func);
return res;
}
Polygon normalFormed() {
Polygon res{*this};
res.normalForm();
return res;
}
bool isConvex() const {
assert(size() >= static_cast<usize>(3));
for (usize i{} ; i < size() ; i++) {
if (Relation(data_[i], data_[i+1==size()?0:i+1], data_[i+2>=size()?i+2-size():i+2])
== CLOCKWISE) {
return false;
}
}
return true;
}
Zahlen areaTwice() const {
assert(size() >= static_cast<usize>(3));
Zahlen res{};
for (usize i{1} ; i < size() ; i++) {
res += Cross(data_[i] - data_[0], data_[i+1==size()?0:i+1] - data_[0]);
}
return res;
}
Polygon subtriangle(usize i, usize j, usize k) const {
assert(i < size());
assert(j < size());
assert(k < size());
return Polygon{std::vector<Point>{ data_[i], data_[j], data_[k] }};
}
};
}
} // namespace zawa
namespace zawa {
namespace geometryZ2 {
template <bool strictly>
Polygon ConvexHull(const PointCloud& p) {
PointCloud cp{p};
std::sort(cp.begin(), cp.end());
cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
if (cp.size() <= 2u) {
return Polygon{cp};
}
PointCloud lower;
lower.reserve(p.size());
for (auto it{cp.begin()} ; it != cp.end() ; it++) {
lower.push_back(*it);
while (lower.size() >= 3u) {
if (Relation(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1]) == COUNTER_CLOCKWISE) {
break;
}
if constexpr (!strictly) {
if (Relation(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1]) == ONLINE_FRONT) {
break;
}
}
std::swap(lower[lower.size() - 2], lower[lower.size() - 1]);
lower.pop_back();
}
}
PointCloud upper;
upper.reserve(p.size());
for (auto it{cp.rbegin()} ; it != cp.rend() ; it++) {
upper.push_back(*it);
while (upper.size() >= 3u) {
if (Relation(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1]) == COUNTER_CLOCKWISE) {
break;
}
if constexpr (!strictly) {
if (Relation(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1]) == ONLINE_FRONT) {
break;
}
}
std::swap(upper[upper.size() - 2], upper[upper.size() - 1]);
upper.pop_back();
}
}
Polygon res;
res.reserve(lower.size() + upper.size() - 2);
res.insert(res.size(), lower.begin(), lower.end());
res.insert(res.size(), std::next(upper.begin()), std::prev(upper.end()));
return res;
}
} // namespace geometryZ2
} // namespace zawa
using namespace zawa::geometryZ2;
int N;
bool solve() {
PointCloud p(N);
for (int i = 0 ; i < N ; i++) std::cin >> p[i];
Polygon poly = p, ch = ConvexHull<true>(p);
std::vector<bool> ok(ch.size());
// ch[0] -> ch[1]の被覆
for (int i = 0 ; i < std::ssize(ch) ; i++) {
bool cur = false;
for (int j = 0 ; j < N ; j++) if (ch[i] == p[j]) {
for (int k : {-1, 1}) {
cur |= ch[(i+1)%ch.size()] == p[(j+k+N)%N];
cur |= Relation(ch[i], ch[(i+1)%ch.size()], p[(j+k+N)%N]) == ON_SEGMENT;
}
}
ok[i] = cur;
}
// ch[1] -> ch[0]の被覆
std::vector<bool> ko(ch.size());
for (int i = 0 ; i < std::ssize(ch) ; i++) {
bool cur = false;
for (int j = 0 ; j < N ; j++) if (ch[i] == p[j]) {
for (int k : {-1, 1}) {
cur |= ch[(i-1+ch.size())%ch.size()] == p[(j+k+N)%N];
cur |= Relation(ch[i], ch[(i-1+ch.size())%ch.size()], p[(j+k+N)%N]) == ON_SEGMENT;
}
}
ko[i] = cur;
}
return (int)std::ranges::count(ok, true) + (int)std::ranges::count(ko, true) == 2 * std::ssize(ch);
}
int main() {
while (true) {
std::cin >> N;
if (N == 0) break;
std::cout << (solve() ? "Yes\n" : "No\n");
}
}
```
</details>
Sign in with Wallet
Connect another wallet