yukicoder contest 352 概要

2022-07-15 21:20:00〜2022-07-15 23:20:00 (2h)のコンテストです。
参加登録などはありません。問題が公開されたら、回答を提出すれば大丈夫です。
誤回答によるペナルティーはありません。

# ナンバー 問題名 レベル 作問者 テスター Solved Fav
A 2007 Arbitrary Mod (Easy) Kiri8128 platinumplatinum 302 0
B 2008 Super Worker Kiri8128 KazunKazun 152 11
C 2009 Drunkers' Contest Kiri8128 MtSakaMtSaka 42 8
D 2010 Magical Floor Kiri8128 tarattata1tarattata1 22 1
E 2011 Arbitrary Mod (Hidden) Kiri8128 platinumplatinum 58 16
F 2012 Largest Triangle Kiri8128 noiminoimi 37 1
G 2013 Can we meet? Kiri8128 chaemonchaemon 19 0

コンテストセッター : Kiri8128

コンテスト情報

Kiri8128 が Writer のコンテストです。

★賞金について（クリックで開きます）★

参加者の中から抽選で約 55 人（最大 1010 人相当、詳細後述）に 50005000 円分の賞金（アマゾンギフト券）を受け取る権利を贈呈します。 対象者はコンテスト中に 11 問以上 AC を得た参加者とします。抽選・賞金の受け取りには応募が必要です。詳細は後述します。 Tester もこの条件を満たせば対象になります。 ただし Tester はテストを担当した問題以外でコンテスト中に 11 問以上 AC を得る必要があります。 当選者は「yukicoder スコア形式」の順位による重み付けによる抽選で決まります（高順位ほど当選確率が高くなります）。

● 【重要】応募方法（クリックで開きます）
賞金希望者は応募をする必要があります。 応募は Twitter 上で こちらのツイート に対して yukicoder のユーザー名をリプライすることにより行います。 応募期限はコンテスト終了の 48 時間後とします。 本人確認のため、賞金を受け取るためには、 yukicoder のプロフィールで Twitter アカウントの登録をしておいてください。
※ プロフィールに Twitter アカウントの登録ができない事情がある場合（クリックで開きます） yukicoder の提出に "Apply:TWITTER_ID" の形式の文字列（例： "Apply:kiri8128" ）を含む提出をしたうえで、 1 時間以内にその Twitter ID から、該当の提出コードのリンクを含めて応募してください。 提出コードの確認をもって本人確認を行ったものとします。
コンテスト後、当選結果をリプライでお知らせします（応募者の当選結果は公開情報となりますのでご了承ください）。 当選者には賞金の受け取り方法の案内をします。受け取り方法の案内から 22 週間以内に返答がない場合は受け取りの権利がなくなります。 なお当選者が未成年の場合は、賞金の受け取りには保護者の同意が必要になります。 受け取り者の居住地に制限はありませんが、お送りする Amazon ギフト券は日本国内用のものになります。

● 当選確率の重み（クリックで開きます）
順位が rr 位である人の重み f(r)f(r) は次の式で定義されます。 f(r)={240−8r(1≤r<20)120−2r(20≤r<50)35−⌊0.3r⌋(50≤r<100)9−⌊0.04r⌋(100≤r<200)1(200≤r) f(r) = \left\{ \begin{array}{ll} 240 - 8r & (1\le r \lt 20)\\ 120 - 2r & (20 \le r \lt 50)\\ 35 - \lfloor 0.3r \rfloor & (50 \le r \lt 100)\\ 9 - \lfloor 0.04r \rfloor & (100 \le r \lt 200)\\ 1 & (200 \le r) \end{array} \right.
当選確率が概ねこれの 11000\displaystyle\frac{1}{1000} 倍になるように抽選されます。
なお ∑r=2101f(r)=5003\displaystyle\sum_{r=2}^{101}f(r)=5003 であることから、 Writer 以外の参加者が 100100 人の場合、平均約 55 人に賞金チャンスがあります。

● 抽選方法（クリックで開きます）
抽選は、
  • 参加者がコンテスト中に当選順位を知ることが実質的にできない
  • 主催者がコンテスト前に当選順位を知ることができない
  • 主催者が特定の参加者を優先的に当選させることができない
  • 応募していない参加者の情報を他の参加者が得ることが実質的にできない
  • コンテスト後に、不正なく当選者が決定されたことが参加者が簡単に確認できる
を満たすように RSA 暗号を模した方法で行われます。 詳細は以下①②③④によりますが、特に興味がある人以外は読む必要はありません。

① パラメータ paramparam の決め方（クリックで開きます）
コンテストの問題数を n=7n=7 とします。 最大 2n2n 桁の整数 paramparam を次で定めます。 ti∈{0,1,⋯ ,59,99}t_i \in \{0,1,\cdots,59,99\} （i=1,2,⋯ ,ni=1,2,\cdots ,n ）を本コンテストの第 ii 問の FA （最初に出た AC） の提出時刻の秒単位（分単位以上を無視したもの）とします。 ただしコンテスト中に第 ii 問に AC がない場合は ti=99t_i=99 とします。 これらを上から 22 桁ずつ並べたものを paramparam とします。厳密には param=∑i=1nti⋅100n−iparam=\displaystyle\sum_{i=1}^{n}t_i \cdot 100^{n-i} です。 例えば第 11 ～ 55 問が開始から 55 分 2323 秒で FA が出て、第 66 問が開始から 77 分ちょうどに FA が出て、第 77 問に AC がなかった場合は param=23232323230099param=23232323230099 です。

② 順位が rr 位の参加者の xrx_{r} の決め方（クリックで開きます）
順位が rr の参加者の得点（yukicoderスコア形式での得点、順位表に示されている整数値）を scorerscore_r として、 xrx_{r} を xr=1060+param×104+scorerx_{r} = 10^{60} + param \times 10^{4} + score_r で定義します。

③ yry_r の決め方（クリックで開きます）
MM を予め決められた 251251 桁の整数 M=10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000081288128000006898487802949733593805234267558009764261129718698217542863197173772727399532406457731136167548445398811226096327004812231745425099393760732038991M = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000081288128000006898487802949733593805234267558009764261129718698217542863197173772727399532406457731136167548445398811226096327004812231745425099393760732038991 とします。 MM は こちらのツイート でも公開しています。 整数 yry_r を、 yr3 mod M=xry_r^3 \bmod M = x_r （ただし 0≤yr<M0\le y_r\lt M ）を満たすものとして定義します。 なお aa を bb で割った余りを a mod ba \bmod b と書きます。 このような yry_r はただひとつ存在することが保証されます（そのように MM を決めています）。

④ 当選条件（クリックで開きます）
順位が rr 位の場合、 yr mod 1000<f(r)y_r \bmod 1000 < f(r) を満たした場合（かつこの場合に限る）に当選とします。 yry_r は当選結果とあわせて公開されます。
ここで言う「順位」は Writer / Tester / 非応募者も含む見た目順位そのものです。 ただし同一順位の参加者が複数いる場合については次のとおりとします。
● 同一順位の参加者が複数いる場合の例外処理（クリックで開きます）
同一順位の参加者が複数いる場合、順位表に記載されている順に順位を区別します。 ただし適用する重み f(r)f(r) は順位をそのまま適用します。 厳密には、順位表の上から rr 番目にいる順位 r′r' 位の参加者は、 yr mod 1000<f(r′)y_r \bmod 1000 < f(r') を満たした場合（かつこの場合に限る）に当選となります。
● 当選者が 10 人を超える場合の例外処理（クリックで開きます）
当選人数は無制限とします。ただし予算の関係で、 当選者が 10 人を超える場合は、賞金の合計が 10 人分相当（5 万円）を下回らない範囲で賞金を一律に減額します。

［追記］難易度の変更による順位・得点修正について（クリックで開きます）
yukicoder には「難易度の変更」をする機能があるため、将来的に順位・得点が変更になる可能性がありますが、 抽選にあたっては、当初設定した難易度に基づく順位・得点を用いることとします。 具体的には、 A 問題から順に難易度は 1 / 1.5 / 2 / 3 / 3 / 3 / 3.5 です。

● 免責事項（クリックで開きます）
やむを得ない事情により賞金の贈呈ができない場合があります。 また賞金の支払方法・条件等は変更になる場合があります。 ご了承ください。
賞金を出すことについて yukicoder 運営さんには事前に相談していますが、 抽選方法などは Kiri8128 独自によるものです。 不備等があった場合の責任も Kiri8128 個人にあります。 本コンテストの開催および賞金の贈呈について、 Kiri8128 の所属会社・所属団体との関連はありません。

2022年7月12日1時20分：追記しました
2022年7月14日0時50分：応募方法について追記しました。順位について補足追加しました。10001000 以上の rr に対する f(r)f(r) が定義されていなかったので 11 にしました。
2022年7月15日0時00分：MM を公開しました。「約 55 人」の根拠を記載しました。その他、明確化のためいくつか追記修正しました
2022年7月15日23時05分：抽選の際は、コンテスト開始時に設定していた難易度に基づく順位・得点を用いることを明記しました。

2022年7月18日2時15分：応募頂いた方の抽選および当選者へのギフト送付はすべて完了しました。万一漏れなどあれば Kiri8128 まで連絡ください。