CPSCO2019 参加記(前半)
運営として参加しました。その辺も含めていろいろ書きます。
〜0日目
はにーまさんの企画を見て面白そうだと思ったのと、黄色くらいがいるといい感じに力になれるんじゃないかと思って運営として応募しました。期間が1ヶ月しかなかったのでかなりバタバタしましたがなんとか問題を完成させました。2日前に問題が変わったり1日前に配点が変わったり当日に制約が変わったりしました(は？)。
Session1
writerをしたのでそれぞれの問題について振り返ります。
A. Ajihon
・O(1)算数
・合宿に関係のある設定
・タイトルがAからはじまる
を条件に作りました。切り上げ処理が必要だったりでほどよい問題だったんじゃないかと思っています。226人が解いてくれました。
B. Beautiful Harmony
・文字列系
・s[i]-'a' とかをする感じ
・タイトルがBで始まる
を条件に考えていると新元号の英語がこれらしいので決まりました。reiwaに対する答えが”Yes”になる問題を作れてよかったです。
ここまでは参加者全員解けて欲しいなぁみたいな気持ちでした。
C. Coins
この問題は実は1番最初につくりました。evimaさんリスペクトの全探索です。
この手の全探索はかなり基本問題だと思っているんですけどそのせいで逆にAtCoderでは全然見ない気がしていて、ずっとどこかで出したいと思っていたので出しました。
難易度という意味では茶色〜緑くらいが対象だったんですが、next_permutationで組み合わせを全列挙できることは黄色レベルの人にも知られていなかったりして当初の予想以上に広範囲に刺さる問題になりました。
D. Dessert Planning
この問題はかなり直前にできました。具体的にはコンテスト7日前です。それまで入れていた問題があまり面白くないなぁと思っていたら生えたので入れ替えました。
C問題が比較的プログラミングよりだったので、D問題については
・プログラミングの知識がほぼなくても解ける
・とすると一般項が数文字で書ける数え上げとかかな
・でも階乗逆元はつらいからnCkはダメだな
みたいな条件で考えるとまぁただの階乗か累乗だよねって感じでできました。
てんぷらセットで1問も1e9+7を置かないわけにはいかないのでね。
ここまで(と後半の部分点)が〜緑パートのつもりです。
E. Exclusive OR Queries
ならし計算量の問題あんまり見ないな、なんかつくるか、で作りました。
もともとは (値, 個数) をpairで持って工夫する系で考えていたんですがxorという天啓が降ってきて個数を持つ必要がなくなりました。
setでがちゃがちゃする系もあんまり見ないしひょっとするとそんなに解かれないんじゃないかなと思っていたらやっぱり解かれませんでした。lower_boundの罠にはまる人もレート問わず一定数見かけたので出したかいがありました。
Pythonがほぼ不可能なのは申し訳なかったです(これは僕じゃなくてPythonにC++のsetと同じものがないのが悪い)。
F. Fruits in Season
にぶたんで何かって思ったら生えました。最初は絶対値じゃなくて直線だったけど探すまでもなく射撃王だったので絶対値にしてみたら判定パートが面白くなりました。
この判定パートは僕は難しいと思っていたんですがコンテストではEとほぼ同じだけ解かれてびっくりしました。Fがこれだけ解かれてEがそんなに解かれないのAtCoderっぽいなぁっていう話をしていました(これはAtCoderに対する個人的な偏見です)。
E, Fの2問が水〜青向けくらいの想定で、オンサイトだと実質ボス問になるのかなぁと思っていました。
G. Game with Division
√X で分けると幸せになれる問題を2日くらい考えていると突然できました。
個人的にはかなり好きな問題です(計算量O(N√X logX ) ってけっこうレアだし)。
個人的にはもう少し簡単な印象だったんですがコンテスト中にACしたのは黄色以上だけだったみたいです。難易度判定難しい。最初GとF逆じゃない？とか思ってた。
H. Highest and Ends
勉強用セットの最終問題って何がいいんだろう、高度典型か、うーん分割統治！で生やしました。個人的にも数列の分割統治の問題をほとんど解いたことがなかったので頑張って作りました。そしたら開催1週間前にGCJのR1Bで分割統治で解ける問題が出たり、3日前のえでゅふぉでdistinctにしただけの問題が出たりして相当慌てました。
えでゅふぉで出てしまったせいで問題設定が少し変わって(もともとmaxA_i だったところを A[m] に変えた)、結果として難易度がさらに高くなりました。
解かれないだろうなと思って出したんですけどコンテスト中のACが3人しかいないとは思いませんでした。
GとHにはそれぞれ部分点(300)をつけていて、基本的なDPとよくある累積maxだったので、〜緑対象のほどよい問題になったと思っています。実際オンサイトでもオンラインでも多くの参加者が部分点にチャレンジしてくれていました。
コンテスト全体としては、AC人数がちゃんと崖のない降順になったり最初の全完が130分(150分中)だったりと思っていた以上に綺麗な結果になってしまって、正直めちゃくちゃびっくりしました。できすぎだと思っています。clarもほとんどなく平和に終わってくれてすごく安心しました。
初心者向けにしては難しいんじゃないかという意見もあるとは思う(というか実際いただいている)んですが、session1については実質 1-2-3-3-3-4-5-6 のつもりでいて、競技プログラミングの勉強合宿として初心者に対して紹介したいのは300点くらいのところなので個人的にはこんなもんじゃないかなぁと思っています。
どちらかといえば解説を300点まわりにもうちょっとフォーカスして準備しておくべきだったので、そこの準備不足については反省しています。
AGC033
その日の晩のAGCで橙に上がっていいことづくめの1日でした。これについても後日どこかに書くかもしれません。
writer自分語りでバカみたいに長くなってしまったので2日目以降については記事を分けることにします。では。
