ゆきこ 352 Writer 記

ゆきこ 352 の Writer をやっていました。

みなさん参加ありがとうございました。

各問題（作問・総評）について

一部ネタバレを含みます。ご注意ください。

B問題

よくあるちょっと計算すればソート条件が分かるパターンですが、★ 1.5 にしては難易度が高いんじゃないかという反応が多かったようです。 *1

C問題

最適化問という意味で B と若干かぶるかなと思ったけど、個人的に設定・解法とも気に入ってたので強行で出してしまいました。ただかぶっているという反応は確認した範囲ではなさそうでした。こちらも ★2 の割に難易度がむずいんじゃないかという反応が多かったようです。「飲酒プログラミング」がはやっていた時期に考えていた問題ですが、タイムリーではなくなったかもしれません（？）。 *2

あとサンプルの説明に不備がありました。ごめんなさいです。。

D問題

幾何は苦手な人が多いですが *3 、典型に入れても良さそうなのに過去に出題を見たことがなかったので出してみました。知らない人は覚えておくと使えることがあるかも。

E問題

個人的には目玉問題でした。一見、「これ解けるの？」という気になりますが、「解けるならこうなっているはずだ」「こうなっていると嬉しい」みたいなところから絞っていくと道筋が見えてくるはずです。解けたときの爽快感を味わって頂ければ嬉しいです。 Fav も一番もらえていたようでありがとうございます *4 。

F問題

知ってればやるだけな気もしていましたが、コーナーケースの処理などで苦戦している人も多かったようです。

G問題

一番アルゴ問っぽい問題かなと思っています。最終問にしていますが、数え上げ・確率が得意な人は考察しやすかったんじゃないかなと思います。

賞金について

いろいろあって賞金を出すことにしてみました。思ったより考慮することが多くて大変でした。

考慮するべきルールなど

当選者数・金額
応募方法・本人確認方法
抽選方法
応募者の当選結果を公開するかどうか
非応募者の当選結果を公開するかどうか
個人情報の管理
賞金の送付方法
未成年の保護者同意確認
運営さんへの謝礼

満たしたかった条件

テスターさんには無償でやってもらっているのと、テスターをやってもらった時点では賞金の話もしていなかった *5 ので、賞金対象から除外するのはないかなと思っていました。一方、 1 位から順に賞金を出す方式はテスターさんが有利になりすぎるかなと思いました。また当選の番号を予め決める（例えば「10 位が当たり」とする）みたいなのは、わざと順位を下げるモチベーションができてしまって、競技としていまいちな気がしました。結果として、上位ほど有利になる抽選が無難かなという結論になりました。

ただ、私自信が参加者に知り合いが多いので、こっちが恣意的に当選者を決めていると思われると面白くないかなと思いました。そこで、当選順位は予め分かっていないが、機械的に当選者が決まり、かつ公正に決めたことが参加者から確認できるようにルールを作りました。

RSA 暗号もどき

競プロをやっている人なら簡単に確認できる *6 方式として RSA 暗号もどき *7 を使うことにしました。

大きな素数 $p,\ q$ を適当に決めて、 $M=pq$ を法として $e$ 乗根を求めるような操作 *8 は、 $p,\ q$ を知っていないと難しいけど、確認は誰でも簡単にできるという条件を満たすので、今回のニーズにぴったりでした。

ランダム性のある Key

当たり確率を適当に決めて、順位表からある程度ランダム性のあるものを Key とする方式にしました *9 。

掲示板方式

当初考えていた方式として、「掲示板方式」がありました。これは順位表から得られるランダムな整数を Key として、そこから得られる $mod M$ の数をひとつだけ決める方式です。これを例えば $5$ 桁の数字がたくさん並んでいると思って、前から見て「当たり番号」が最初に出た 5 人が当たりという方式です。「当たり番号」は順位の重みの分だけ発行されます *10。これだと抽選作業がラクになる（ひとつだけ $e$ 乗根を計算すれば良い）という意味では良いんですが、応募していない人の当落情報を公開してしまうことになるのでよくないかなと思って断念しました *11 。

あまり大きな問題にはならないかもですが、アンケートによると（賛成票が多いものの）否定派の人もいるようなので、勝手に情報公開するのは良くないかなと。

そういえば yukicoder で（公式さんと相談したうえで）個人的に賞金を出す案を検討しているんだけどどうでしょう？
コメントなどあればリプでお願いします
— きり (@kiri8128) June 13, 2022

個別抽選方式

結果的に採用した方式です。

参加者ごとに RSA 暗号もどきで抽選をします。これなら応募者のみ抽選すれば応募していない人の情報は漏れることがありません *12 。この場合の問題として、当選人数を固定にしづらいというのがありました。

予算は適当だったので、期待値 5 人ぐらいで多少ぶれても良いかなということで、上限を決めたうえであとは個別ランダムにしました。少なすぎても多すぎても微妙でしたが、結果的に 4 人当選ということでちょうど良かったかなと思っています。

暗号理論をうまく駆使すれば応募していない人の情報を公開しないかつ当選者を固定人数にする方式もありそうでしたが、そこまで考えられませんでした *13 *14 。

応募方法

掲示板方式なら応募は不要（当選者にこちらから DM すればよい）ですが、個別抽選方式なら応募は不可欠です。専用のサイトを作る手もあったのですが、めんどくさいので Twitter 上でツイートへのリプを送って応募するという形式になりました。 TL で盛り上がるといいなというのも少しありました。

本人確認

金銭が発生するので、本人確認は最低限する必要がありました *15 。 yukicoder には Twittter ID を登録する機能があったので、それをベースに本人確認を行いました *16 。

Twitter ID を登録していなかった人にはお手間をかけてしまいましたが、なりすましによる応募を防げたので良かったかと思います。

SSRS です。
— ながたかな@ゆうさんは私のハンドルネームを親近感をお持ちになります (@ngtkana) July 15, 2022

重大なミス

RSA 暗号もどきの Key として、当初は順位を使っていたのですが、それより得点にした方が参加者による裁量 *17 が大きくなって面白いかなと思って得点（を整数に丸めたもの）を Key にすることにしました。実はこれが大きなミスでした。 yukicoder では同じ問題でも解いた順番によって得点が違うものの、ある程度の順位からは同点となる参加者が多くいます。順位によって当落条件は若干違うとは言え、場合によっては同点メンバーがまとめて当選してしまう可能性がありました。例えば 52 点の参加者は 24 人いましたが、 10 人を超えて当選した場合は 10 人分の賞金を山分けするような例外を公開していたので、仮に当選しても半分以下しかもらえないという可能性がありました。結果的に同点当選はなかったのでことなきを得ましたが、設計上の不備となっていました。 *18

個人情報の管理

基本的には個人情報を集めると管理上の責任が出て大変なので、極力個人情報を持たないことにしました。アマゾンギフト券の送付も（メールアドレスを聞かずに） Twitter の DM 上で行いました *19 。

FAQ

Q: A 問題、簡単すぎじゃない？

A: 賞金チャンスをたくさんの方にという理由で、 A 問題のハードルは極力下げてみました。実際この問題だけだと楽しみ要素は少ないんですが、 E 問題への布石になっているので（まだの方は）ぜひ E 問題と一緒に楽しんで頂ければと思います。

Q: E 問題のタイトル名、 Hard じゃないんですね？

A: 結構迷いました。タイトルからは GCJ とかの Hidden *20 のことをイメージする人もいたかもですが、入力が Hidden になっているというパターンも面白いかなと思ってこちらにしました。

ちなみにツイートで類題 *21 を出したことはあります。

正の実数 s があります（与えられるとは言ってません）。 tan x = s となる正の実数 x を1つ出力してください。正しい解との絶対誤差あるいは相対誤差が 10^-6 以下であれば正答とみなします。

入力: 本問では入力は与えられない
— きり (@kiri8128) October 14, 2020

Q: 賞金を出した理由は何ですか？

A: 特に理由はないです。しいて言えば yukicoder がさらに盛り上がると良いかなというのはありました。 yukicoder 上で賞金を出すならどういう形式になるんだろうと思って考えていたら、いつのまにか出すことになっていました。

Q: 賞金を出したら参加者数増えましたか？

A: コンテスト終了時点でサブミッションは 172 人（うち正の得点 167 人）でした。直近だと 110 人台ぐらいの回が多かったので 50% ぐらいは増えたと言えそうでしょうか。

Q: Key に $10^{60}$ を足したのはなんでですか？

A: ふつうに整数範囲で $3$ 乗根が存在する可能性があったので、それを排除するためにある程度大きい立方数を足してみました。

Q: 最近は $998244353$ で割った余りを求める問題をよく見ますが、 B 問題で $10^9+7$ にしたのはなぜですか？

A: これ作ったのだいぶ前で、まだ $998244353$ がそこまで主流じゃなかったときに作ったものなんですよね。。

Q: こどふぉとかぶってませんでした？

A: これはまじで未確認でした。ごめんなさい＞＜

こどふぉノーチェックだったの反省ですごめんなさい・・
— きり (@kiri8128) July 15, 2022

Q: 作問でこだわったところはありますか？

A: 一番こだわったのは E 問題ですね。いかに見つけづらい感じにするかはこだわってました。単にそれっぽいのを掛け合わせるだけだとだめで、「反例」が出るのもある程度大きいところで出るように調整しました。 $10^7 \le M \le 10^{18}$ の条件もなるべくさりげなく入れるために A 問題で同様の設定にしたりしてみました。

制約の $5000$ 以下という制約も、普通は計算量を $2$ 乗に抑えないといけないみたいな意味に捉えられがちですが、そもそも $5000$ を超えると成立しないというパターンにしてみました。

Q: 逆に作問で不安なところはありましたか？

A: たくさんありますが

E のスペシャルジャッジが合ってるかが一番不安だったのでランダムテストたくさんやるなど確認しました。
E はテストケースも大事なので、いろいろためしてちゃんと落ちるか確認してました。
G でより計算量が良いのがあるかも気にしてました（最悪 log 1 つはありそうだなと思ったらあったようですが、まあ許容範囲かなと思ってます）
F のマラソンは落としたいと思ってました。
小数問題が多かったので、誤差が大丈夫か（特に想定解が死んでないか）は注意して確認しました *22 。
あまり例を見ない問題（特に D と E）もあったので、難易度が妥当かどうかは心配でした。 D、E、F は同じにして「逆転」が起きてもいいようにしてましたが、 B や C も外れていたようで反省です。

Q: 参加者にしてほしいことはありますか？

A: 解いた感想や、どういう思考で解法にたどり着いたかを教えてもらえると嬉しいです。別解法がある場合は、ユーザー解説も書いてくれると嬉しいです。面白い問題だと思ったら Fav も付けてくれると嬉しいです。

Kiri8128の日記