---
title: yukicoder contest 482 開催記
---

# yukicoder contest 482 開催記
2025/09/12 に初めて yukicoder でコンテストを開催したので， writer としての感想を残しておこうと思います．
まだ問題をご覧になっていない方は，この先を読む前にぜひご覧になってください．お時間のある時に取り組んでもらえるとさらに嬉しいです．
[問題一覧はこちら](https://yukicoder.me/contests/562)

# 目次
- [開催までの経緯](#開催までの経緯)
- [準備期間について](#準備期間について)
- [コンテスト中について](#コンテスト中について)
- [各問題について](#各問題について)
- [その他感想](#その他感想)
- [謝辞](#謝辞)
- [参考資料](#参考資料)

:::warning
:warning: 「各問題について」の節は問題のネタバレを含みます．
:::

# 開催までの経緯
これまで作問の経験は全くなかったのですが，今年の 4 月から某所で作問の機会を頂いたので，何問か作っていました．（問題やジャッジは非公開です．）そこでの没問を集めて公開した，というとあまり正確ではないですが，大体そんな感じです．今回の 7 問のうち 2 問がそれに該当します．

その 2 問が先にあって，「意外と悪くなさそうだし公開するか」と思って，突然コンテストを開催したい気分になったのが 6 月の下旬だったと思います．続く一ヶ月で残りの 5 問を用意して， 7 月の下旬に tester を募集しました．（このためだけに全く投稿していなかった SNS のアカウントを動かしました．）

tester が集まるかどうか不安でしたが 2 日くらいで見つかり，[遭難者さん](https://x.com/nasya_AC)に全問引き受けて頂くことになりました．本当にありがとうございました！

# 準備期間について
問題文と解説は yukicoder のサイト上で，テストケースは [rime](https://github.com/icpc-jag/rime) 上で準備しました．

yukicoder の作問側を触るのは初めてでしたが， UI も含めて非常に使いやすくて良かったと思います．特に気に入ったのは問題文から（？） input validator を自動で生成してくれる機能と，アップロードしたテストケースをファイル名の正規表現で削除できる機能です．準備には関係ないですが，告知時に問題名を隠す機能など（一旦ログアウトする必要がないということです．）細かいけど便利な機能があって感心していました．

rime は某所である程度使い慣れていたので特に新しいことはなかったと思いますが，改めて機械的なジャッジ環境の重要性を実感しました．

問題文と解説について，この種の文章を書いた経験があまりなかったので非常に苦労しました．
特に解説について，読みやすさと厳密な表現を両立するのは今の自分には難しすぎたようで，かなり時間をかけた割に両方の点で微妙なものになってしまったように思います．また，前者を補うために何個か図を作っていたら，そこでも結構な時間を使ってしまいました．（図を全て TikZ で作ったのが原因かもしれません？）

問題文の作成では[競プロ作問チェックリスト (初心者向け)](https://drive.google.com/file/d/1kTfrNKGXMhJOgUdyDhYo2dswbwPAhZ7a/view) がとても参考になりました．また，tester 時に細かい箇所をいくつか指摘していただいて助かりました．

# コンテスト中について
運の悪いことに開始早々ジャッジが詰まってしまい，自分が何かやらかしたのではと不安でした．詰まりの原因は特定されたようで，最後の 10 分ほどは正常に動いていたのは良かったと思います．長時間対応していただき，時間延長の対応もしてくださった運営の yuki2006 さんと，ジャッジが動かない中で諦めずに提出してくださった参加者の皆様に感謝です．

ジャッジ復活の期待も込めて（D 以降の提出が少なめだったのもありますが）こちらから延長をお願いしました．元々は 120 分の予定だったのですが，ジャッジの詰まりとは関係なく短かったような気もします．全体テスターを募集した方が良かったかもしれません．

問題の不備や clar はなかったので，tester 時にしっかり確認してくださったおかげだと思います．ありがとうございます！

# 各問題について
:::info
:information_source: 各種統計はジャッジ詰まりの影響を大きく受けていますので，ほとんど参考にならないと思いますが一応載せておきます．
:::

## A: PQ Straight (★2.5)
- 54 solves / 62 tries
- first AC: ococonomy1 さん (00:02:24)

何らかの構築が作りたいと思って適当に考えていたら生えました．writer 解，tester 解ともに偶奇と半分より大きいかに着目する方針です．writer は偶然にも一瞬で（全探索を書く前に）解けてしまったので最初 ★1.5 になっていました．contestant 的には実験すれば何とでもなるのでしょうか，かなり早いペースで解かれていたと思います．★2 でも良かったかもしれません．ほぼ全員がどちらかの解法だったと思いますが， writer 解の方が多かった印象です．

[この問題](https://atcoder.jp/contests/utpc2023/tasks/utpc2023_e) や [この問題](https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_e) で既出（しかも部分問題）でした，すみません．準備段階では全く気が付かなかったので，問題を解く側としての経験が浅いですね．
https://x.com/sad_eight/status/1966514279093305621
https://x.com/sad_eight/status/1966518766377812325
ご指摘ありがとうございました．

## B: As Seen in Toasters (★2.5)
- 27 solves / 39 tries
- first AC: hitonanode さん (00:07:07)

問題文だけ見るとタイトルが意味不明ですが，部屋にあった（ゼンマイ式のタイマーを回すタイプの）トースターを見て作った問題です．「 $T$ 未満に設定するときは， $T$ 以上に回してから合わせてください．」みたいなことが書いてあると思いますが，その制約をつけた際の $x$ - $y$ 間の移動距離を $f(x,y)$ としたつもりでした．問題文を簡潔にするために， $x,y < 0$ を含めて $T = 0$ にしました．これに気づいた方はいらっしゃるのでしょうか...

解説にあるような図を描くか，実験するとわかりやすいと思います．結局最小値をとる $A$ は 2 パターンに限られ，サンプルにはどちらも入っているはずですが，全て $A_i \leq 0$ の場合などで WA が何件か出ていました．

現実の題材から作った割には自然で，程よい考察要素がある問題になって個人的にはお気に入りですが，終了 10 分前に WA が返ってきた contestant の皆様にとってはそうではなさそうです．残念．

最初は ★2 想定でしたが，tester 時の提案で ★2.5 になりました．ありがとうございます！

サンプル 3 の出力はコンテスト開催日の日付にしました．

## C: Leq-K Partition (★3)
- 16 solves / 27 tries
- first AC: noya2 さん (00:14:45)

問題設定も使うアルゴリズムも決めずに適当に考えていたら生えました．想定解は平方分割 + 二分探索で，その通りに解いた方が多かったですが，
- 二分探索 + 調和級数 + Wavelet Matrix で $O(N \log^3 N),$
- Segment Tree 上の二分探索 + 調和級数 で $O(N \log^2 N)$

といった，想定外の準線形解法があって驚きでした．writer も tester も最初に書いた C++ の $O(N \sqrt{N \log N})$ が 1.6 sec くらいで動いたので，二乗の定数倍高速化を恐れてこの TL になりました．一応同じ計算量で PyPy3 が通ることは確認したのですが，TLE した人がかなり多かったです，すみません．平方分割の閾値をサボった $O(N \sqrt{N} \log N)$ だと C++ でも怪しくなってくると思います．feedback がない中で一発で通せ，となると余計に不快だったかもしれません．そもそも，sqrt-log 系と 二乗を区別する問題を出すことにもっと慎重になるべきだったとも言えそうです．

[このブログ](https://codeforces.com/blog/entry/134445) で既出でした，すみません．しかも $O(N\sqrt {N})$ になるようです．実は writer も似たコードを書いていて，「なんか速いな...」と思っていたのですが，計算量解析ができず放置していました．勉強になります．
https://x.com/torii_kyopro/status/1966514106036302232
ご指摘ありがとうございました．

## D: No Coprime Cycles (★3)
- 5 solves / 13 tries
- first AC: hitonanode さん (00:26:19)

今回のセットで一番の自信作（のつもり）でした．最初の提出 (hitonanode さん) はかなり早かったので安心していましたが，結局あまり解かれませんでした．tester の遭難者さんもかなり早めに解かれており，「D/E/F の中で一番典型」という評価を頂いたので，すんなり解ける or 無理ゲー に二極化されやすかったのかもしれません．

この問題は某所（本記事の最初に登場する「某所」と同一です）で出会ったとある問題から作りました．ジャッジは非公開なので概要だけ紹介すると，

- $A_i$ に対応する頂点と，
- $A_i$ の素因数に対応する頂点

からなる二部グラフ（本問題の解説で登場する $b(A)$ と同一です）の上で最短経路を求める（ことに帰着される）問題です．この問題が面白いと思ったので， $b(A)$ の持つ性質について考えていたら奇跡的に生えました．元のグラフ $g(A)$ に関する条件を $b(A)$ に関する条件に帰着することが本質ですが，いい感じに $b(A)$ の存在を隠した問題になったと思います．

とはいえ，素因数に着目する意図は分かりやすいと思いますし，「適当に投げたら通った」が大量に発生するかもしれないとも想定していました．証明は結構面白いと思うのでぜひ考えてみてください！

## E: PQ Dot Product (★3)
- 4 solves / 7 tries
- first AC: Rubikun さん (01:05:31)

A と似た設定でもう一問作れないか考えていたら生えました．初めは $= K$ ではなく $\equiv K \pmod N$ で[^footnote]，現在の B と C の間に置かれていました．tester 時に，山登り法（ $P = (1,2,\dots,N)$ から始めて 2 点交換を繰り返す）が通ってしまうと指摘を受けて困っていたのですが，数日後に $= K$ の場合が解けたので出題することになりました．

$N \geq 4$ のとき最小値と最大値の間が全て達成できるのですが，想定解ではその証明がそのまま構築方法になります．writer 的には十分満足したのですが，contestant 的にはただの謎パズルだったかもしれません．コンテスト時間中に解いてくださった 4 名の皆様，ありがとうございました．

正直なところ難易度についてはよくわからなかったのですが（tester 時には ★3 or ★3.5 を提案されました），改めて見ると問題が非常にシンプルで，最初の一歩が分かりづらかったとは思います．実験しても， $K$ が最小/最大から離れると大量に解が存在するので，規則を発見するなども難しかったのではないでしょうか．

こちらも適当な山登り法 or 焼きなまし法が結構惜しいところまで行ったので，TL を 1 秒にして，そういう系の解法は違いますよとアピールしたつもりでした．本番では謎 heuristic が通るなどはなかったのでセーフでしたが，上手にやると通るのかもしれません．

サンプル 3 の出力は，No. 3271 ということで $(3,2,7,1)$ が連続部分列として現れるようにしました．$K = 123$ になったのは狙ったわけではなく，ちょっと嬉しかったです．

[^footnote]: $P = Q = (1,2,\dots,N)$ から始めて，連続する $k$ 個の数が並ぶ部分 $P = (n,n+1,\dots,n+k-1), Q = (n,n+1,\dots,n+k-1)$ の片方を 1 だけ cyclic shift すると $P = (n,n+1,\dots,n+k-1), Q = (n+k-1,n,\dots,n+k-2)$ になり，内積が $k(k-1)/2$ 減ります．これを適当に組み合わせることで $R_N - N$ から $R_N$ までの値が作れます（ $R_N$ は内積の最大値）．

## F: Separate Contractions (★3)
- 5 solves / 8 tries
- first AC: hos.lyric さん (01:12:42)

縮約という設定だけ決めて考えていたら生えました．直径・中心典型なのは分かりやすく，中心を根として考えるとスコアの差分が部分木に関する何らかの値として表せるので，あとは頑張りましょう，という感じです．結構シンプルな問題で良いかなと思っていたら，細かい場合分け + 実装重めという如何にも contestant に嫌われそうな問題になってしまいました．writer も tester もかなり手間取りました．想定解は通常の DFS だけで線形ですが，HLD や全方位木 DP を使う解法もあるようです．

見た目簡単そうなので沼にハマる人が続出すると良くないかな，と思ってこの位置にしましたが，コンテスト中の提出を見る限りでは D,E を飛ばして F から手をつけた方も何名かいらっしゃるようです．

## G: Exactly One Match (★4.5)
- 2 solves / 4 tries
- first AC: hos.lyric さん (00:36:57)

[ABC318-Ex](https://atcoder.jp/contests/abc318/tasks/abc318_h) を誤読して $P,Q$ が順列とは限らない場合について考えていたら， Functional Graph の根付き木の部分を良い感じに数え上げる方法を発見（再発明）した約 1 年半前の記憶から作った問題です．制約が大きめなのは Kinoshita-Li 合成で殴られるのを防ぐためでした．機械的に EGF 合成を用いて解こうとすると，（一般の場合の）合成が必要になって困ることを想定していました．想定解では，長めの計算は必要ですが，合成はもちろん inv / log / exp / pow も必要なく，積（畳み込み）2 回だけで実装できます．

$C$ から考えるとかなり簡単になるのは全く気づきませんでした．面白かったです．([potato167さんの解説](https://yukicoder.me/submissions/1121009))

使う道具がやや高度で，計算も重いので最近の ★4 よりは大変かな，と思って ★4.5 になりましたが，他の ★4.5 と比べるとかなり簡単な部類だと思います． ★3 × 3 と並んだので避けた方も多そうですが，こういう系の数え上げが得意な人にとっては D,E,F より取り組みやすい気もします．

サンプル 3 の $K$ は [tribonacci constant の 10 進表記](https://oeis.org/A058265) です．

# その他感想
- 原案を作り始めた時は超典型みたいな問題ばかりになるんじゃないかと思っていましたが，意外に変な問題もできて良かったです．D と E を考えている時が一番楽しかったと思います．
- 総じて「こんな問題解けるかな？」$\rightarrow$「解けました，じゃあ出題しますか」という感じで，もう少し原案の段階で精査するべきだったかもしれません．とはいえ今の自分にはこの程度の質が限界な気はします．
- D 以降は（参加者が少なかったのもあり）思ったより解かれませんでした．一瞬で全問題解かれるよりは良かったでしょうか．
- 某所での没問は D と F でした．この問題を某所（主にアルゴリズム初学者が対象）に提供することにならなくて本当に良かったです．
- 面白いという感想も何件かいただいたので，それに関しては素直に嬉しいです．

# 謝辞
AtCoder 上での writer / tester 作業でお忙しい中， 7 問全てを見てくださった tester の遭難者さんに感謝します．tester 時のフィードバックなしでは，コンテスト開催ができる程度に体裁を整えることは不可能でした．

問題公開の場を提供してくださった yuki2006 さんに感謝します．誰でも気軽に作問できる貴重な環境のおかげで，面白い経験になりました．コンテスト当日は遅い時間までジャッジ復旧の対応をしてくださり本当にありがとうございました．

コンテストに参加してくださった contestant の皆様に感謝します．ジャッジが全く動いていないことに気づいた時は絶望でしたが，その後も提出一覧が更新され続けていたのを見て感動しました．

# 参考資料
本コンテストを準備するにあたって参考にさせていただいた資料へのリンクです．
- [yukicoder Wiki](https://yukicoder.me/wiki)（yuki2006 さん等）
「作問者・テスター向けページ」の箇所にあるもの全て
- [競プロ作問チェックリスト (初心者向け)](https://drive.google.com/file/d/1kTfrNKGXMhJOgUdyDhYo2dswbwPAhZ7a/view)（opt さん）
- [Rime 1.0 ドキュメント](https://rime.readthedocs.io/ja/latest/)（ICPC Japan Alumni Group さん）
- [PGF/TikZ Manual](https://tikz.dev/tikz)（Dominik Peters さん，Till Tantau さん等）
問題文・解説の図を作成する際に参考にさせていただきました．
- [DEGwer 式作問法](https://note.com/degwer/n/n270f59cb7809)（DEGwer さん）
- [【競プロ作問】問題の原案作成のアプローチ](https://milkcoffee.hatenablog.jp/entry/2021/12/15/000338)（milkcoffee さん）