はじめに
先日，学内で小規模なプログラミングコンテストを開催しました．
コンテストに参加することは何度かありましたが，自分で企画することはおろか作問すら経験したことがなかったので，非常に有意義な時間でした．
ここでは，その反省や振り返りについて記述していきます．
コンテスト概要
振り返りに先んじてコンテスト概要を以下に記します．
全体振り返り
KPTで振り返ります．
- Keep
- オフとオンの同時開催で無事に開催できた
- 中難度問題がある程度想定通りの正答率であった
- Problem
- ある問題でジャッジに致命的なバグが存在していた
- 問題文の不備がいくつもあった(日本語や制約など)
- 想定難易度と参加者レベルが噛み合っていなかった
- 易問を想定した問題の正答率が低かった
- Try
- 運営陣を複数人としてtesterを用意する
- 参加者レベルを事前に推定する
全体として，コンテストの開催や進行は滞りなくできましたが，問題に関する不備が多かったように感じます．問題の難易度が全般的に高めに設定されていた上に，易問も比較的難しいものとなっていたため，競プロに慣れ親しんでいない方々には少し辛い思いをさせてしまったかもしれません．
最終結果では半数の方が１完となっており，コンテストとしては非常に問題だったと思われます．
問題振り返り
以下では各問題ごとの振り返りを行います．
なお，想定難易度はAtCoderの得点基準として，作問者想定(参加者体感)で記載しています．
A:Magician
難易度100 (約200)
問題概要
$(12x+6) \textrm{mod} 13$ が与えられる．$x$ を復元せよ．
解法
$x$ が高々9種類であるため全探索する．
振り返り
本問題は全員が正答を獲得しており，1問目の難易度としては適切だったと言えます．
探索要素があることも競プロの初歩問題として良かったのではないでしょうか．
B:Impartiality Candy
難易度300 (約300)
問題概要
長さ $N$ の数列Aの最大要素を $-1$，最小要素を $+1$ することを $K$ 回繰り返す．
得られた数列の(最大要素-最小要素)はいくらになるか．
解法
数列の状態が安定するまでシミュレートする．
状態が安定すると状態がループするようになるので，まとめて計算する．
毎回ソートで$O(\textrm{min}(KN^2\log N,\sum (A_i) N^2\log N))$，工夫すると $O(N)$
振り返り
本問題はシミュレートのコーディングとシミュレートを圧縮する考察を要する問題でした．さらに，平均値が整数かどうかでの場合分けが実は必要で，このケースを通すことができない参加者も見受けられました．このように易問にしては要求されている要素が多く，参加者の登竜門となってしまいました．
$K$の制約を下げ，シミュレートのみで解けるようにするべきであったと反省しています．
C:Organic Compound
難易度300 (約280)
問題概要
次数が $4,1,2$ となるノードがそれぞれ $A,B,C$ 個あるような連結グラフを構成できるか判定せよ．
解法
次数が $1$ のノードを最大限使うようにして次数 $1,4 $のノードから広義で次数 $2$ となるノードを生成する．そして，次数 $2$ のノードを連結して巨大な次数 $2$ のノードを一つ生成する．
$0,1$ 個の次数 $2$ ノードと複数の次数 $1$ ノードの問題に帰着できたので，次数 $1$ ノードの数で場合分けして判定する．
振り返り
本問題は発想力だけで勝負する問題でした．次数1のノードをどうやって処理するか，という考察が出来ると後は流れ作業で解けると考えていましたが，正答率は高くなかったです．問題性質がAGCに近いことを考慮すると，本問題は易問枠とすべきでなかったかもしれません．
また，本ブログではグラフ用語による厳密な問題文を記載していますが，本番では非競プロerへの配慮として厳密性を欠いた用語で補完していました．これが逆に問題読解の複雑さを招いてしまい，いくつか問題文に対する質問を頂いてしまいました．厳密な表現が出来る場合は補足といった形でも表記するべきだったと思います．
D:Average Filter
難易度500 (約500)
問題概要
サイズが $(2n+1)$ の正方行列に平均値フィルタを $N$ 回繰り返し適用し，最終的な中央の値を求めよ．
解法
割る操作が最後の $1$ 度のみで良いことから各マスが中央のマスにどれだけ寄与するかを考えればい良い．これは経路数問題として解くことができる．
さらに，上下と左右の移動が独立であることを利用すると計算量を一つ下げられる．
経路数問題を解くDPで $O(N^2)$，各マスの総和を取るのに $O(N^2)$，全体で $O(N^2)$
振り返り
本問題は難問枠の一つとして作問しました．視点の切り替えやDP計算量を落とす考察など有用で典型的な考察が多くお気に入りの問題でした．
競プロerにはぜひ挑戦してほしい問題の一つでしたが，難易度調整ミスによって他の問題に時間を割かれてしまいました．
E:Arithmetric Instructions
難易度600 (約630)
問題概要
数字 $0$ を持っており，A,M,?からなる命令列を左から順に実行する．ただし?は連続している．
A: $1$ ビット目を反転，M:左シフト，?:A，Mのどちらか．
命令列を実行し終えた後の数字として考えられるのはいくつあるか．
解法
左シフトの性質を考えると?に至るまでの数字が $0,1,2$ 以上の $3$ 通りで場合分けすることが考えられる．
さらに，?のAとMで数字が重複して生成される条件を深く考察すると，各場合で，「ある命令までで作れる $1$ ビット目が $0,1$ となる数字の個数」のDPが自然に構成できる．
全体で $O(|S|)$
振り返り
本問題は考察重視の難問枠として作問しており，コンテストのボス問題という立ち位置でした．必要な考察が2段階でどちらも軽くなく，正答者は0人でした．ボス問題としての役割が十分果たせたと言えます．
しかし，実は本問題は最初の場合分け後はOEISに投げることで解くことが出来てしまいます．幸い本番中に気付いた人はいませんでしたが，大規模なコンテストではとても出題することはできないでしょう．
F:Easy Problem
難易度300 (約340)
概要
最大 $2000$ 桁(整数部 $1000$ 桁，小数部 $1000$ 桁)からなる $A,B$ が与えられる．$A+B$ を計算せよ．
解法
数字を各桁ごとに配列に格納し，小数点の位置を合わせて加算する．
不要な $0$ や小数点を慎重に削除する．
振り返り
本問題は強実装問題として導入しました．非競プロerでも取り組むことができ，競プロerでも実装練習になると踏んで出題しましたが，思っていた以上にバグを誘発していたようです．
回答率はA問題に次ぐ多さでしたが，不正解率が他問題の追随を許さないほどに高くなりました．本問題に多大な時間を割いてしまったことにより他の問題の考察が出来なかった参加者も多くいたため，まさしくこの問題はコンテストにおける癌であったと言えます．
(実装力を過信していたこともあったが)コンテストで強実装の問題を出すのは良くなかったと思います．
G:Number K
難易度400 (約370)
概要
ある規則に従って，$i$ 回目の操作で $i$ 個の数をリストに追加していく．これを $N$ 回繰り返す．
各操作後でリスト内の $K$ 番目に小さい数を出力せよ．
解法
いくつもの解法が考えられる．
- 二つの順序付きリストを用意し，$K$ を堺に格納するリストを変える．$O(N^2\log N)$
- 各操作後に解が $t$ 以上であるかという二分探索を行う．$O(N^2\log N)$
- 数をセグ木に乗せて総和が初めて $K$ を超える数を二分探索する．$O(N^2\log N\log N)$
振り返り
本問題は競プロerを対象として柔軟な発想を問う問題でした．いくつもの解法が考えられるためかなり考えやすい問題だったと思いますが，そもそも問題を開いた参加者が多くなかったです．
H:Frog Jump Easy
難易度300 (約350)
問題概要
数直線で座標 $0$ からスタートし，$A$ 進む，$B$ 進む，$C$ 進む( $C$ 進めるの1度だけ)のいずれかを繰り返し実行尾する．
座標 $N$ に到達する手順はいくつ考えられるか．
解法
- 通常のDPに $C$ を使ったか使ってないかの条件を付与する．$O(N)$
- 通常のDPをした上で，$C$ を使う場所を全探索する．$O(N)$
振り返り
本問題は競プロerを対象としたド典型問題でした．コンテスト全体で発想重視の問題が多いため，バランスを取る意味で初歩的なDPを採用しました．競プロerの回答率が高く，狙い通りでした．
I:Multiple Divisor Light
難易度600 (約600)
問題概要
長さ $N$ の $2$ 進数列が与えられる．好きな数を選んでその約数と倍数番目の数を反転する，という操作が何回でもできる．
$Q$ 個のクエリに対して，数列を全て $1$ とすることが出来るか判定せよ．
解法
操作をxorとして置き換えると，各操作に対する線形結合で表すことが出来る．
操作行列から基底を取り出すことで，各クエリは高速に判定できる．
基底の計算で $O(N^3)$，各クエリの判定で $O(N^2)$，全体で $O(N^3+QN^2)$
振り返り
本問題は難問枠の一つとして出題しました．しかし，正答者曰くこの解法は典型であるとのことだったので，難問枠としては不適切であったと言えます．
J:Beautiful Range
難易度500 (約600)
概要
長さ $N$ の数列 $A$ で平均が $(r-l+1)$ となる区間 $[l, r]$ の組が丁度 $K$ 個となる数列を構築せよ．
解法
数列を全て $-1$ して考えると，総和が $0$ の区間が丁度 $K$ 個という問題に帰着できる．
区間の総和が $0$ であるとは，累積和が等しいということである．ここで，累積和が等しいものが $p$ 個あると総和が $0$ となる区間が $pC2$ 個あるこということを利用すると，$(p,pC2)$ を要素とする個数制限なしナップサック問題を解くことで丁度 $K$ 個が作れるか判定できる．このDPを復元することで対象となる数列を構築できる．
構築などで $O(N)$，DPは状態数を削減できるため $O(K\sqrt{N})$，全体で$O(N+K\sqrt{N})$
振り返り
本問題は難問枠の一つとして作問しました．問題Dと同様に，典型的な考察の積み重ねにより解くことが出来るため，問題文の通り"美しい"問題です．
かなりお気に入りの問題だったのですが，コンテスト中にジャッジシステムにバグがあることが判明してしまいました．泣く泣く問題を閉じるしかなく，当時の悲しみは計り知れないです．
おわりに
コンテスト中はいくつもの不備によってコンテスト自体破綻してしまったと思っていましたが，振り返ると無事に進行できていたようで安心しました．
しかし，問題の不備や難易度に関しては改善の予知が多く残っています．
学内コンテストの開催はこれが最初で最後のつもりでしたが，作問に対して未練しかないので，後輩らにはぜひとも来年度に主催して私を作問チームに入れて欲しいです．
