【競プロ】作問振り返りメモ - あめんばーどのバーチャル日記

無事コンテストが終わることができて良かったですが、その上で反省点も非常に多い作問でした。思い出としての振り返りもいっぱいあるんですが、それは別の記事にすることにして当記事につきましては作問にあたっての反省点や留意点をまとめていけたらと思います。

反省と言う割には、結構文章は適当です。~~苦手なので。~~ どちらかというと自分のメモ向きに書いたので、他人に見せる感じではありません。ご了承ください。

謝辞

コンテストに参加してくれた皆様、後押しをたくさんしてくれたVRC競プロ部の皆様。何よりも無茶を言いながらもTesterを務めてくださったtatyamさんとテッドさんには大いなる感謝を述べたく思います。今回のコンテストが無事に終わって本当に良かったと思っております。問題を作ると言うことは非常に楽しいことでありながらも、非常に多くの人の支えがあってこそと言うことを片鱗ながらも感じさせていただきました。本当にありがとうございました。

文章を作ると言うこと

正直、テストケースや問題構成とかやることはたくさんありましたが、これが一番課題だと思いました。

私は言葉を連ねることが非常に苦手です。嫌いではないのですが、非常に苦手です。文章でも会話でもとにかく支離滅裂な順序になったり、助詞を適当に処理してしまったりする頻度の高さが非常に大きいです。文章を長い時間連ねていると突然頭の中が真っ白になり、順序関係や事実が頭から飛んでしまうことすらあります。

そのせいか最初に作問した時はだいぶ文章が破綻していてお二人揃って結構指摘されてtatyamさんが文章の大半をわかりやすく書き換えてくださったこともあり事無きを得た感がありました。本当にここばっかりは感謝を申し上げるばかりです。

内容は100%伝わらなければならない

当然と言えば当然なんですが、日常では意外とやらない。数学界隈では日常的にやるんですが。~~苦手だったからどうしても書かなきゃいけない時以外は結構サボったりノリで書いてた。~~

表記方法の工夫

数は全て数式に入れる
数式の中に日本語は入れない
鉤括弧やcodeで重要な単語はしっかり囲む
条件の整理や挙動についてを箇条書きを使ってしっかりと用いる

定義や数式を見えやすく表現する

論文の書き方をまるで覚えていないのが露呈していましたが、さまざまな書き方の工夫を提案されました。

マンハッタン距離を式まで書いて正確に定義する
数列や集合に対してカッコをしっかり使い分ける
重要性のなかったり選択を留意するなど扱いの違う数値は注釈する
フレーバーやシチュエーションの定義などでも厳密に定義しておく
LCMの非斜体化を面倒くさがらない
制約は出力の定義も全力で厳密に

誤読や誤解させる情報に注意する

Bは最初「格子点の上空にカメラを置く」という設定だった
二次元なのに三次元の話をされ、マンハッタン距離の意味がわからなくなる
Gで連携力を二重に計算してしまいそうな気持ちになりそうという指摘があった
Aもサンプル見るまでわからなかったという指摘

なおF問題で10⁴を10⁵と読み間違えた人に関しては狙ってやったことなので知りません。

問題と解答の重要度

当たり前ですが問題文はコンテストの進行に関わるためどちらが重要かと言われれば、当然前者です。でも終わった後の感想を見た後でも結構E問題の記号の意味がわからないなどの感想をちらちら見かけました。具体的に何かということではないのですが、どちらの文章を充実させるかの優先度は早めに見切りつけたほうが良かったなと。

フレーバーの結局

Testerのテッドさんは「やるなら全部フレーバーかけ」とのことなので全部の問題にエトワーニュくんが登場しました。ただそこで議論として出たのは

フレーバーと問題文はわかりやすく分ける
フレーバーだとしてもある程度シチュエーションはしっかり書く

テストケース

想像はしていましたが問題を作るにあたって重い作業でした。

自分を殺すこと

実はF問題は二転三転としたんですが、原因はテストケースに自分のケースが落ちたことなんですね。当初は平方分割が想定解だったのですが、場合分けするときの処理が

Listを参照するだけ
Dictionaryを参照していろいろする

どちらも $O(1)$ なんですが、定数倍が違いすぎて後者が全力で重くなるテストを作り忘れていたままだったのですが、ふと思い出して作ったところ死亡。そこから二転三転が始まりました。

結果的にbitsetでも解けて、平方分割でも場合分けした時の定数倍の違いがほとんどなくすことができるデータ構造を定義できるようにできましたが……。自分のテストケースは全力で殺しに行かないと、自分が見落としているところって結構あるんだなと感じました。

Hのテストケース

幸いなのがこの問題は考察パートが中心であることと、辺の種類の制約が結構でかかったので大きな問題は出ませんでした。

負の辺のDijkstraが通っちゃったらしい。反省
testerの指摘で、Dijkstraで必要な「既にもっと小さい長さになってたら更新しない」の処理を入れなくても動く
これはLRのコストがC固定なので、防ぎようがない
グラフのテストケース作るのは難しい

C,Fのテストケース

ランダムで作るとまずNoの答えになるのが癖モノでした。解決方法はいろいろありました。

YesかNoを先に決めた後に、条件を満たす組み合わせを探す
探すことが計算量的に難しい場合はスモールケースで行う

Dのテストケース

これはDPのランダムケースしか作っていなかったのですが「分枝限定法」で解かれるのは防ごうということになりました。あんまり調べてもどうすれば……？となることは多かったのですが、ひとまず平均的な重量を決めた後に、重量と価値を比例してランダムを交えつつ微増減させるケースを作りました。全部似た値になることで防ぐことができますね。

なんとなく、ランダムな一様分布に増減させるのは怖かったので、一様分布をいくつも重ね合わせて疑似ガウス分布を作れば、もっと似た値になってくれるよなぁと思いながら作りました。

Eのテストケース

これは楽しかったです。最悪ケースはサンプルでも入れましたが、とにかく最悪に近いケースを片っ端からぶち込んでいました。

約数の多いベストいくつか
最大の素数
$2$ や $10^{12}$
約数の数と素因数の数の積が最大
遷移数が最大
$2$ の累乗最大

Gのテストケース

未だにこの問題のキルケースの作り方がわかりません……？とりあえず作ってみたものはあるものの……有識者求む

$20$ 層に分かれて $3$ つずつ頂点が存在するグラフが作られるようにする
二人だけ
これの見様見真似

ジェネレータについて

意図が残せるので作った方が絶対良い。

C++のランダムはstd::random_deviceで
複数の意図がある場合は切り替えが容易にできるように
ランダムをそんなに信じなくていい

バリデーションについて

最初は問題の作り方を読んで「急いで作らなくていいなら作らなくていいかな」と思っていたのですが、tatyamさんにHを見せたところ即刻作ってもらえました。すごく参考になりましたし、絶対にあったほうがいいと思います。

事故率が大きく減る
制約を変えたい時にも気軽にチェックできる
これはこれで勉強になる

期間について

これはすごく私がわかっていなかった問題です。最初私は「問題が完全に用意できた状態でyukicoder運営に連絡して枠を貰う」ものだと勝手に思っていたのですが………。

別にそんなことなかった！！！と、雑な結論になってしまいますが、そんな感じで慎重になりすぎていました。

皆さんどんなタイミングや順番でやるんでしょうね？有識者～！~~こどふぉがよく延期するのってこれ関係ある？~~

問題文を作成する
テストを作成する
Testerをお招きする
コンテストの枠を取る
問題文をfixする

Testerお願いについて

今回は全部の問題をほぼ同じ人に投げてしまいましたが、それ以外についてはどうしてるのかも暇があったら情報集めたいなぁと思いました。

問題別指摘された点や振り返り

A:Backflip

さすがになかったですね………私としてもどうふざけるかとしか考えていなかったので………

B:Flying Camera

マンハッタン距離の定義方法

実は最初マンハッタン距離って言葉で書いていただけだったのですが、最初にテッドさんに指摘されてマンハッタン距離の定義を入れた上に、最終的にtatyamさんの校正で $\sum$ も用いた厳密な合計の定義まで行いました。ホントすごい

誤解や疑念を与える問題文

こちらの問題、公開間際までは「ドローンが二次元座標上の上空にある」という表現でした。ここで指摘受けたのが「三次元になってる」ということです。さらに上空にあればマンハッタン距離の軸も増えてしまいますね。実は間際まで「確かにそこの厳密さは正しいけど、文章の書き方で何とか伝わらないのかな……」と思っているフシもあったのですが、後ほど書くG問題で受けた指摘を思い返すと掘り固めていて大正解だったと思いました

C:Freight Train

先述の通り、テストケースが作成が結構難しかったです。基本的にNoが帰ってきてしまう上に、条件を満たす列の作成もちょっと面倒でした。とはいえA問題に並んで大きな問題はそんなになかった………かな？

D:ExpressionMenu

こちらも先述の通り、DPのケースを考えるのにいろいろ調べるのが難しかったです。

E:Phys Bone Maker

表記の省略は論外

実はこの問題は急遽追加した問題だったのでとりあえず問題文とテストケースだけササッと作っていろいろな表記を抜いたところテッドさんにめちゃくちゃ読解難をさせてしまった初期値などの設定もせず、不等式の部分だけで一応意味は伝わるやろ！エイ！とやって大変なことになりましたのでここに懺悔

F:Friends+

今回の作問の反省点のたまり場

問題の趣旨に関係ない実装難は害

実はこの問題、最初はjoinコマンド以外にも下記のコマンドがありました。上の方ほど最後まで生き残っていました。

newinstance（誰もいない場所に移動する）
friend（フレンドになる）
block（フレンドを解除した上でその後フレンドに慣れなくなる）

newinstanceはまだ一考の余地があったのですがblockに至ってはお前何をさせたいんねんというめんどくさい読解難実装難を呼ぶだけのものでした。一瞬でもこれを考えて問題文に入れてしまった自分がなかなかに恐ろしいと感じてしまった。~~あとブロックでギスギスしてるエトワーニュくんとか解釈違いなんで~~

もちろん、実装難を意図した問題もアリとは思いますが、変な全部盛りはやめましょう。たのしくない。

ちなみに自分自身にフレンドは元ネタ記事でも言いましたが、Testerによる追加お遊びです。途中までは自分がフレンドはアリなのかだいぶ迷っていたり同じ場所にいたらどうしよう……と思っていたところに追加したのが「同じ場所にいたらjoin不可」でした。これは別に強い実装難にするものではなかったので、いいところに落ち着けたと思います。

最も殺すべきは自分の解答

これについては先ほども述べたため省略。自分で作った解法が通らない事態にまで陥りました。自分の理解力の少なさも顕著に出ました

元ネタから難問作るのは難しい

全体を通してもFriends+という仕様から難しい問題に結びつけるのは結構難しかったです。日常のあらゆるところから問題に結び付ける遊びは結構しますし面白いんですが、だいたいいい問題に落ち着くかと言うと自分でもわからんか、簡単か、NP完全なんですね。

楽しい行為ではありますが明らかに他の問題と比べて作問効率が非常に低かったので覚悟はいるな、と思いました。

Testerマジックは起きる

というわけでコマンドを消しまくったり自分の解答が死んだりと踏んだり蹴ったりな状態だった上でどうしようかと音を上げたところ最後の問題に至りました。

ちょっとテッドさんと相談できる機会があったので話したところ、解説でも書きました通り最初は定数倍の重い処理を避けたクエリ平方分割でなら綺麗な形にできる！と思い実行しました。

そしてtatyamさんがbitsetでぶち殺しました。

私が求めていた難易度になりました

さいこう！

G:Game World for PvP

最初は「敵対している同士の最低値を求めろ」としていたのですが、Testerの提案で今回の問題に変更しました。私の意図としては最大値を求める方がよかったが、Hのヒントにならないかと不安だったのでこちらにしていた感じでしたね。

「大丈夫だと思います！」と言われたので結構喜んで変えたりしました。

誤読を与えかねない表現はモニョる

終了後指摘ツイートで見かけたのが「連携度を二重に数えるのか迷ってしまう」という指摘がありました。これを見て今までTesterのお二人にたっぷり添削を受けていた件についてヒエッと思いました。今回は幸い質問は来なかったものの、間違えていたらたくさん迷惑をかけていたのだろうなと……。 ~~あとその翌日のABCで「消費したらなくなるんですかー！？」って質問平然と送ったりした自分もいたしな！！！~~

たぶん大丈夫だろうは絶対ツッコまれるのだと思えました

H:Continuous Flip

こういう問題どんどん作っていける人間になりたいなぁと真に思えました。思い出話しないと言っていたんですが、これをtatyamさんに見せた時にいただけた言葉とかしてもらえたこととか、すごく嬉しかったんですよ。加えて終わった後もレッドコーダーの方にめちゃくちゃ褒めてもらえて。本当に作ってよかった。

こちらは初めても初めての作問だったので結構基本的な表記についても指摘されてしまい。あとDijkstraの殺し方も即刻指摘されました。さすがでした。

数式の前後にはスペースを入れる
数は全部数式に入れる
数式には日本語は入れない
左から $i$ 番目とかじゃなくて、ちゃんと番号を付けたほうが読みやすいし大抵短い

最後に

またH問題のような問題が次も浮かぶかとか、ARC-likeなことができるかと言われると無理だと思います。

それでもレッドコーダーの方々に「H問題が面白かった」と言ってもらえたり「典型みを感じるたのしいセットだった」と言ってもらえたりと私が描いていた通りの感想を言ってもらえて。あとA問題が最速22秒だったりE問題で皆さんの手が突然止まったりF問題が平方分割組がバグりまくってたりH問題が最短経路まで気づいた人を見ては「がんばれー！」って思ったり。

とてもとても楽しかったです。何回でも言いますが問題だらけだった文章をここまで変えてくれたTesterのお二人には感謝しきれません。

今は無理でも、また皆さんを楽しませることができるような問題が作れる日が来たらいいな。と思いました。強くなれる理由がまた一つ増えました。

また機会がありましたらよろしくお願いいたします。