heno239’s blog

まとめたいことをまとめる

KUPC2021参加記 運営視点

  • はじめに

10月31日にAtCoder上にて

京都大学プログラミングコンテスト 2021

が開催されました。(https://atcoder.jp/contests/kupc2021 )

私は一昨年、去年に引き続き運営側として参加し、コンテストの準備をしました。

今回は今までの中でも自分が一番関わったコンテストになりました。

 

  • 運営について

3月下旬から問題の選定をはじめ、7月末には問題案が決まり、8~10月で問題の準備をしました。

問題の選定は私が主導して行いました。メンバーの皆さんが次々と問題を投げてくださったので、あまり問題案不足に悩むことなく、問題の選定を終えることができました。

 

コンテスト開催にあたって、AtCoder様にはたくさんご協力をいただきました。ここに多大なる感謝を申し上げます。

 

  • 問題について

 

  • A問題

はじめは T の倍数の撤去という制約がなく、各 i について[S_i,T_i]に設置されるので、"1度だけ"京都大学を訪れ、見れる立て看板の数を最大化してください、という問題でした。

atcoder.jp

↑上位互換です。本当にありがとうございました。

 

次案として「全ての看板を見ないといけないが、そのときに訪れる必要のある回数の最小値」となりました。(要するに、いまのA問題から"Tの倍数"という部分を抜いただけ。)

 

ただこれだとA問題にしては難しすぎるという話になり、最終的に"Tの倍数"という条件が付きました。

 

  • B問題

去年のKUPCの没案だったりします。みんな大好きパズルです。

想定解は2通りあり、解説に両方載せています。

 

  • C問題

僕はあんまり関わってません。はじめB問題に置かれていましたが、かなり難しいということが判明して後ろに飛ばされました。

準備側の気分次第でDにもEにも飛ぶんだぞってことで

 

  • D問題

僕はあんまり関わってません。みんな大好きゲームです。

 

  • E問題

これも去年のKUPCの没案から。まともな問題でも、「似たようなジャンルの問題がたくさんある」という理由で結構没になるんですよね・・・

出力形式については完全に忘れてました。ごめんなさい。

 

  • F問題

僕がはじめに出す予定だった問題が没になり、代わりに入れられました。

結構好きな問題です。

準備してくれた人がナップサック近似アルゴリズムを倒すのに苦心していました。(その余波でテストケースがたくさんあります。)

 

  • G問題

好きな問題です。面白いと思います。原案見て1秒で採用でした。

 

  • H問題

答えが有理数になるのが面白いと思います。これも原案を解いてすぐに採用しました。

 

  • I問題

原案は全然違う形だったのを、僕がこの形にしました。結構教育的な問題にもなったんじゃないかなと思います。

 

  • J問題

原案はN<=2000だったのをN<=200000にしました。

好きな問題です。面白いと思います。是非証明も併せて考えてみてください。

 

  • K問題

3月に僕が投げた原案そのままです。

枝刈り全探索を落とすためにテストケースを頑張って作りました。

でも一部通ってるっぽくて悲しいです。

 

  • L問題

面白いと思います。

想定解もテスター解も数回WAになりました。

このセットで最も難しいと思います。

 

  • M問題

はじめN<=10^5で提案されていた問題を、N<=10^18に改造しました。

去年のM問題に引き続き、想定以外の解法でたくさん解かれてしまいました。

想定解では、「i 文字目は文字C_iでないといけない」という条件を10000個ほど追加しても解けます。

↑が思いついたのがコンテスト開始直前とかだったので、準備が間に合いませんでした。

 

また、10/30に

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2789

(ICPC模擬地区予選2016J問題)

に出会い、解説を読んだらかなり本質的なことが書かれていました。

 

  • 没になった問題

F問題の説明にもありますが、問題が1つ準備してから没になりました。

これからもあんまり出題できそうにないのでここで公開します。

長さNの順列が与えられます。
あなたは各要素について、-2<=x<=2を満たすxをえらび、その要素に値をx足します。
こうしてできあがる数列は5^N通りありますが、そのうちの転倒数の最小値と最大値をそれぞれ求めてください。
 
制約:1<=N<=10^5

別のコンテストサイトで0<=x<=1版が出たので没になりました。

 

  • 最後に

来年も是非開催できたらいいなと思っています。

あらためて、コンテストの運営を一緒に行ってくださった皆様、コンテストの準備に多大なるご協力をしてくださったAtCoder社様、そしてコンテストに参加してくださった皆様、本当にありがとうございました！！