WUPC4th を開催しました
2020/9/12に行われた、WUPC4thの運営側目線の感想です！ 早稲田大学の競プロコミュニティは、現B2が今一番ホットになっています。彼らが今回主催となってWUPCを開催しようとしているところにのっかる形で参加することになりました。AOJや告知はadminのHyadoくんや、同じく現B2のかっつくんに任せて、僕は高学年なことをいいことに、いろいろ口出しをしたり邪魔していました。
これが理由で、実はWUPC3とはメンバーが大幅に変わっていて、yamadさんと自分以外は新規メンバーです(WUPC3のお話はこちら)。
以下、writer&tester陣の紹介です: 今回は、5時間で13問という形になりました。 簡単枠です。昨年のWUPC3rdよりは簡単になったかと思います。 少し簡単めの構築枠で、当初はこれがAに置かれていました。 奇数列目を最大化、偶数列目を最小化すればOKです。あとはどれだけ答えに寄与するか、を計算できればいいのですが、実は二項係数になっています。 自分の問題1つめです。 問題を見ると約数包除をしてください、と書いてあるので約数包除をします。 2で割れる回数を固定したとき、その中で取れる最大の数が答えの候補になります。あとは全探索です。 01ナップサックと、個数制限ナップサック両方をやるという問題です。帰着できればすごいサクサク解けてシンプルですがハマると…？ 木の直径が奇数かつ3の倍数 + 一定の条件を満たしたときのみ、他と比べて少しペナルティが大きくなる、それ以外は適切に構築すると最高効率で構築できる、という問題です(簡単に説明するのは難しいので解説を見てください)。 桁ごとに見て、マスの行と列の差の絶対値が1以内の部分に立っているビットがあるかどうかを見ればよい、という問題です。気づいたり証明したりするのは難しいかもしれませんが、気づけばそこまで数えるのは難しくないです。 一度クエリでYESとなった島は、それ以降常にYESなので、そこを探索しないようにうまく見ていきます。 ミラー戦法をベースにやると、あとは細かい場合分けです。 蟻本239ページを一般化すればよいです。全然しらなかった、面白いです。 B2が主体となって進めてくださったので、あとはただその流れに乗るだけでした。 途中、ジャッジが一時期詰まるという事態が発生しましたが、それ以外は特にトラブルなく進みました。 改めて、参加してくださった皆様、主催してくれたひゃどみん、一緒に準備した皆、サイトを提供してくださったAOJの方々、外部テスターとして参加してくださったSSRSさん、物理好きさん、その他大勢の皆様、本当にありがとうございました！
コンテストサイト
運営陣について
yamadさん
しろくん
sutaくん
Senくん
かっつくん
Hyadoくん(admin)
ばやしこくん
hotmanくん
オウコウくん
suzukenくん
よぴぱくん問題セットについて
A: Prime Number Sum 2
基本区間の幅の偶奇を見ればいいのですが、、すなわち素数の"2"が含まれている場合だけ、答えが逆になります。
他の問題だけだと序盤から解けなくて詰まる人がいるのではないか、ということから最後に生えた問題です。B: Canceling Sequence
と
番目の要素に分割し、それぞれの係数をうまく組み合わせて0にすればOKです。緩めの制約にしてあるため、適当につくっても問題の条件を満たします。
僕は構築が苦手なので、この問題を解くのに少し時間がかかりました...C: Flip Difference Sequence
問題ができた当初、割と最近のAGCでこれ(ネタバレ注意)が出題されていたので意外と解かれるかも…？と思っていました。D: Treasure Mountains
指数部分について、区間積を計算し、の逆元を計算すれば、
を累乗するだけで簡単に
が求まる、という問題です。
これは、自分が参加したCTFで似たようなことをする問題があり、それが面白いと感じたことから作問しました(元ネタを知りたい方は、 cryptctf three ravens で検索してみてください)。
この問題を作成した時点では作問が閉め切られていたのですが、追加枠が発生したのでそこに滑り込ませました。
数学系の問題を作るのは初めてで、証明をなんども反復して行ったりと不安要素が多かったです。E: LCM Count
考え方は蟻本のとほぼ同じで、あとは数列の並べ方を気合で数えます。
問題や入力がシンプルかでかつ解法が面白いので、結構好きです。F: Abyss and Coins
結構アドホック要素多めですが実は素直に見ればいいという問題でした。(僕らの想定では)C以降で一番簡単枠、でした。G: Fitness
もちろん元ネタはこれです。少し前は諸事情でできなくて、最近再開したのでのんびり頑張ります。
典型 + 典型 で解法も実装もシンプルなので、結構好みです。H: RGBtree
個人的に圧倒的ボス問でした。こういうの解けるようになりたいですね…
yamadさんがすごい不安がりながら何回もこの問題を証明し直してるのを横目に、自分もD問題の証明を必死になって反復していました。I: Magical Matrix
これ結構すごいと感じました。作問スキルいいな～。J: Meet on the Island
今いる頂点も、既に探索済みであれば探索しない、ということをしないとコーナーケースにハマってしまうのでご注意を！！K: Rectangle Game
リアクティブ問題にして実際に構築、等々いろいろ考えましたが難しくて断念しました。
割と最近、こんな問題があり、ビクビクしていました。L: Count Pow Sum
M: Star Gazer
suta-Gazerってね。
気合で全方位木DPが最初の想定でしたが、より軽い実装もあります。
木の問題が作りたいなーと言ってるときに生やしました。距離が計算式にあるのに距離を全く使用しなくても解ける、というのが当時のポイントです。準備について
既出等が見つかっても、代理問題を準備できたのでよかったですね。
テストケースが弱くなってしまいがちな問題が今回も多かったので、全員で協力していろいろ作成できたので安心でした。
今回、作問陣だけでは不安が残るということで、外部テスターとして物理好きさん、SSRSさんのお二人に参加していただきました。内容は、完成したセットをバチャ形式で一通り解いていただく、というものです。
お二人とも得意分野が違っていて、解く順序やスピードが異なっていて面白かったです(内部では順位表を見てワイワイしていました)。
特に物理好きさんは、解くたびに問題面白い、とコメントをくださっていて、内部で喜んでいました。本番
問題文の訂正が一つだけありましたが、後はなんとかなったのでよかったです(B2陣、すごい)。
自分達が用意した問題で詰まったりケースで落ちるのを見るのは最高ですね！！！終わりに
