赤い星と強い星

ディズニーとかその他の趣味とか

RedSpica Winter Selectionを開催しました

こんにちは

 

　RedSpicaです．12月29日(木)にRedSpica Winter Selectionというコンテストを開催しました．

mojacoder.app

　非常にたくさんの方にご参加いただきました．本当にありがとうございます．せっかくなので感想的なのを書き残しておこうと思います．

 

 

 

1．You Want to Play?

　FA 0:59bayashikoさん 

　今年の夏休みは本当にずっとValorantをしていました．ずっと目標としていたゴールドに達することもできました．

　問題概要もゲーム内の設定そのままです．題名はChamberというエージェントがアルティメットアビリティを使う際のセリフ「遊びたいのか？相手になろう」の英語版"You want to play? Let's play"からとりました．リンクには今年開催されたVCT2022 Stage1 Masters-ReykjavíkでのTenZ選手の配信の切り抜きが埋め込まれています．SugarZ3ro選手がACEで試合を終わらせるすごいシーンなのでよければ見てください．

 

2．Closeness of the Day

　FA 5:12 bayashikoさん

　2問目なので簡単なループっぽい問題にしたいものの，なんか特殊な問題にしたかったのでだいぶ前にTwitterで見たものを原案にしました．

　知っていた方はTextで提出してもらっても，知らなかった方は愚直にループを回して計算してもいいです．言語によっては日付を持ってこれるライブラリがあるらしいのでそれを用いてもいいです．

　想定解はそれぞれの月の日数を手打ちで打ってループ回すみたいなのなんですが，それを手打ち(知らない場合は調べてから手打ち)するくらいの面倒くささは許してください．

 

3．Count Up Ikkyu

　FA 7:23 hourenさん

　ある数学の本を見てたら原案が生えたので解答を見たら結構きれいでびっくりしました．なんかこういうの有志コンで出たらまあまあ嫌なので出さないようにしたいなって思っていたのですが，まあいいかなと思い出しました．よかったら解説の閲覧&いっきゅうのフォロー↓お願いします．

https://twitter.com/ikkyufacku

 

4．Find a RedSpica

　FA 13:14 roarisさん

　与えられた状況を無向グラフとして見たとき，各連結成分の頂点に書かれた数字のうち1番大きなものが書かれているものが赤である頂点を数える問題です．解法はUFでもグラフの探索アルゴリズムでもなんでも解けます．ただMojaCoder上のジャッジステータスの関係でちょっと困惑した方を数名みかけました．コンテストのトップページに書いておけばよかったですね，配慮不足でした．PythonでDFSを書いた方は再帰の回数の上限を上げているかどうかを確認してみてください．

　オリヴェルっていうのは僕が小学校の頃やっていたネットゲームで飼っていたペットの名前です．特になにかを参考にしたわけではないんですが，中二感があってなんかかっこよくないですか？

　グラフの各頂点を星と見立てて，連結成分を1つの星座とみる．なんかいい感じですよね．問題名もシンプルでなんかかっこいいと思っている結構自信作です．

　リンクにはレヴュースタァライトの星見純那さんの紹介ページが埋め込まれています．「人には定めの星がある，綺羅星　明星　流れ星」というのは彼女の口上で，舞台に登場した際に発するセリフです．

　サンプル2の各星のつながれた関係は実際のおとめ座の関係を参考にしました．星の等級というのは数字が小さいほど明るいので，明るい順に暗い星の等級を振りなおしました．「頂点に立つのはただ1人」というのはこれもレヴュースタァライトの天堂真矢さんのセリフです．「This is 天堂真矢」でおなじみです．

 

5．Partition of N

　FA 5:48 17さん

　 1 \leq x \leq Nに対して，重さが x，価値が d(x)，許容容量が Nであるナップザック問題を解く問題です．

　自分が考えた問題はいくらでも簡単に見えてしまうのを考慮してなかったのですが「ナップザック問題に落とすの賢い」といった感想を何件か見たので意外とむずかしかったのかなあとこの場所/点数に設定したのが少し反省です(実際5問目と6問目の正解者数が逆転していました)．問題文が読みづらい/サンプルが少ないみたいな感じで誤読を誘っていたら本当に申し訳ないです．

　「 \{a_i\}は互いに異なる」という条件が入っているのは，これがないと 1を N個用意して Nを達成して終わってしまうからなんですね．とはいえ01ナップザック問題を解くならあまり関係ないのですが．

　リンクには12 Days Of Christmasという歌が埋め込まれています．この歌は歌詞を見ると「1,2,1,3,2,1,4,3,2,1,...」という感じで数字を数え上げるのですが，それが「互いに異なる数字を合わせる」とか「この問題の計算量が O(N^2)となる」みたいな感じで若干ヒント？でした．あとクリスマスが近かったのもあります．

 

6．Load to cocoa

　FA 9:38 17さん

　地点 1からのDijkstra法と地点 Nからのダイクストラ法で2つの配列をもつのが想定解です．頂点を3倍して1つの配列でやるみたいな解法で解いてる方もいたようです．

　問題準備が終わってから典型90問にほぼ同じ問題が出題されていることに気づいたのですが，せっかく書いたので出題しました．かなり典型テクニックということですね．

atcoder.jp

　この問題のテストケースを作ってる時に思ったんですが，

N頂点 0辺のグラフを考える．以下の操作をグラフが連結になるまで続ける．

・ 1 \leq u,v \leq Nを満たす u,vをランダムに決める．

・もし uと vが連結でないならば u,v間に辺を張り，そうでないならば何もしない

っていうのって操作回数の期待値ってどれくらいになるんですかね？テストケースを作ってる時の感じでは N=10^5の時でも結構一瞬で生成できて，個人的には「コンプガチャの要領で N \log N回くらいかな」と思ったのですが証明ができず．何かわかった方がいたらご一報ください．

　リンクには七河みこさんのユニバースの動画が埋め込まれています．彼女は世界各地に旅行をするのが好きで，いろいろな場所に1人で行くそうです．問題とかかってる部分は旅行と移動くらいなんですが，とてもいい動画なのでよければ見てください．

 

7．Knapsack Expect i-th

　FA 17:49 17さん

　左右からナップザック問題を解いて，それを利用して各 iに対して問題をうまく解けばよいです．添え字をバグらせないように注意が必要です．

　「両端からやる」「ナップザック問題を解く」というのが5問目と6問目で若干かぶるのでどういう問題配置にしようかなと思っていました．しかし感想を見ている感じこれも問題作成者はいくらでも簡単に見える理論からあまり関係なかったようです．

　コンテスト中LayCurseさんがかなりの時間この問題で詰まっていたのでこっちの不備があったのかと思って滝のような汗を流していました．無事に正解していただけてよかったです．

　リンクには北海道大学の石川先生の質問解答PDFが埋め込まれています．2年前に位相空間論の授業を受けているときにネットの海でこのPDFを見つけた覚えがあります．コンパクトの定義のたとえが結構しっかり焼き付いていたので引用させてもらいました．

 

8．MakeMany Buri-Oden

　FA 3:09 dyktr_06さん

　 \max \{ \min \{ a_i+a_j, b_i+b_j\} \}, 1 \leq i \leq j \leq Nを求める問題です．なんと既出らしい．

 

　セグ木に載せて二分探索が想定なのですが，他にもいろいろな解法で解けるようです．

　実はコンテストはこの問題を除いた8問100分でやる予定だったのですが，急にこの問題も思いついたので問題数を増やして時間も少し伸ばしました．せっかくburiodenさんから名前をお借りしたのにむずかしめの問題になってしまったのは少し申し訳なかったです．

　富山県は鰤が有名らしいのですが，卒業するまでにおいしいのを食べてから富山を出ていきたいですね．そもそも卒業が怪しいですが．

　リンクに埋め込まれているのは乃木坂46のジコチューで行こう！です．MVも曲もとても良いです．

 

9．Function Composition

　FA 6:20 LayCurseさん

　剰余を取る値が小さいのでダブリングで前計算ができます．「関数の合成がダブリングの本質ではないか」と考えているところがあり，逆にそれをそのまま出したら面白いんじゃないかと思って出題しました．

　コンテスト中にある参加者の方から「 f^{(0)}(x)は xでは？」という趣旨の質問をいただき，追加で説明を書きました．その質問をもらって急いで調べたところ， f^{(1)}(x)=f(x)と記述しているページが1番最初にヒットしたのでリサーチ不足だったかなと反省です．ただ，今回のコンテストであった不備はこれくらいだったのでよかったです．

　この問題も値を計算する際のオーバーフローで不正解となる提出がジャッジステータスが意図したものと違うものが出て困惑した参加者の方もいたようです．「解法は合ってるはずなのにACにならない」という方はオーバーフローしていないか確認してみてください．

　リンクには虹のコンキスタドールのサマーとはキミと私なりっ！！が埋め込まれています．虹のコンキスタドール通称虹コンは夏曲を全面的に押しているグループで，この曲は虹コン7年目に出された夏曲です．”何度も”が6個続いているのはこれまでの6年を表しており，この曲が7年目だよというアピールになっているようです．

 

10．その他

優勝 41:13 ei1333さん

 

全問完答者 10名

1st 41:13 ei1333さん

2nd 46:50 + 5:00 LayCurseさん

3rd 57:03 + 5:00 bayashikoさん

4th 73:57 +15:00 akuaさん

5th 80:10 + 10:00 ecotteaさん

6th 87:15 + 10:00 roarisさん

7th 99:51 + 15:00 Daylightさん

8th 99:21 + 25:00 siganaiさん

9th 114:51 + 15:00 dyktr_06さん

10th 111:14 +25:00 mikamさん

 

各問題正解者/提出者

1．You Want to Play? 58/59

2．Closeness of the Day 58/58

3．Count Up Ikkyu 49/50

4．Find a RedSpica 53/54

5．Partition of N 33/33

6．Load to cocoa 40/40

7．Knapsack Expect i-th 23/20

8．Make Many Buri-Oden 18/22

9．Function Composition 14/17

 

11．全体の感想

　改めて本当に多くの方にご参加いただきありがとうございました．夏に開催した際は30名弱の方に参加していただいたので今回もそれくらい参加してもらえるといいなと思っていたところ予想を大幅に上回る参加者でとてもうれしく思います．また，特に不備もなくコンテストを終了することができてよかったです．

　終了後の感想は(観測できる範囲で)すべて見させていただきました．「楽しかった」というものをはじめとしたさまざまな感想を寄せていただきありがとうございます．励みになります．

　開催中/開催後に思ったのですが，やはりこのセットで120分は少し短かったですね．「自分が作った問題は簡単に見えてしまう」+「ためていた原案はすべて吐きたい」+「有志コンで時間が長いと集中力が切れる/のちの感想共有の時間が深夜になってしまう」→「このセットをこの時間で行こう」というのが理由です．それでも上位勢はしっかり時間内に全問完答していてさすがだなと思いました．

　個人的にはAtCoder水色くらいで戦える典型的な問題/よく考えればわかる問題をそろえたつもりです．解説も書いたのでよければ解けなかった問題もあきらめずに挑戦してみてください．

　

　コンテストを開催するにあたり全体テスターを引き受けてくださったzeronosu77108さん

　問題文のおはなしに登場してくれた競プロ仲間のみんな

　素晴らしいコンテストサイトを提供してくださったマクタモトさん

　そして最後になりますが，コンテストに参加してくださった参加者の皆さん，この度は本当にありがとうございました．

　またコンテストを開催する機会があったときはぜひご参加ください．

 

RedSpica