ごりちゃんがゆく

競プロをするゴリラの精進記録

ゆるふわオンサイト#2 ゴリラの挑戦状 でwriterをした話

どうも〜 prd_xxx ですゴリ〜〜
9/14(土)に、「ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状」というイベントで、writerをさせていただきました！

コンテストページ
解説スライド

初作問チャレンジではあったのですが、第1回の作問を全て務めたmatsu7874氏のノウハウもあって、無事に成功に終えることができました！

本番までの準備など (時系列)

A〜K問題(11問) の原案と問題文とテストケースを作成しました。

5月頃

会社slackの競プロ部チャンネルで、作問者募集がかかる。
絶対やってみたかったので迷わず手をあげる。
300〜400点ぐらいの原案を空き時間で考えはじめる。

6月頃

引き続き、空き時間で原案を考える。
実際のG問題までの原案がだいたい揃う。
緑コーダーが5,6完できる水準をイメージしていたので、それはだいたいクリアできた認識。

〜7月中旬

500点以上の問題が作りたい気分になる。
I問題とJ問題の原案ができる。
ここまで原案9問、あとmatsu7874氏も作問するので一旦十分かな〜という気分になる。

7月下旬

日付が9/14に決まり、イベント告知。(JAG合宿とかぶった件はごめんなさい)
予想を上回る応募の多さにゴリのテンションMAX！ (定員で来れなかった方はごめんなさい)
幅広いレート帯の方に参加いただけるようで嬉しかった！
ところがある懸念も同時にあって、それは
トップ層が30分で全完して90分暇になったらどうしようと思った ゴリ怖かった
というのも自分よりレートが上位の方もおそらく半数ぐらいいらっしゃって、全然ゆるふわじゃない この人たちにも楽しんでもらいたい という気分になった。
あの けんちょん氏を60分は全完させないぞ！というつもりで張り切って問題を作ることになる。

8月上旬

matsu7874氏にプライベートリポジトリを作ってもらい、過去の作問リポジトリも見せてもらった。
それとbeet氏の記事であるところの Rimeの使い方 - beet's soil を参考にする形で、粛々とテストケースを作っていった。
結構大変な作業だなと思いながらも、最初の7問 (A～G)は詰まるところなくできた。

8月中旬

J問題のテストケースを作りたいと思っていたが、中だるみというか急に乗り気がしなくなってテストケースを作る手が1週間ぐらい何も進まなかった。
代わりにいくつか問題案を生やすことをしていた。
問題案を考えるのは楽しくて、テストケースを作るのはつらい、ってのを肌で感じていた。
ただそんなことも言ってられず、testerに見てもらう期間をとるため、作問作業は8月いっぱいで終えることにした。

8月下旬

駆け込みの時期。IとJのテストケースを完成させた。
H問題を追加したのと、K問題(の前身のすがた) のテストケースを生むために、8月いっぱいでやるはずだった予定を少しすぎてしまった。

9月1週 (2週間前)

testerのkyuridenamida氏とrian_tkb氏を作問slackに招待し、その時点でできている問題を解いていただいた。
ほとんどの問題で問題なく解いて頂けたので一安心。
問題文はいくつか指摘いただけて、こうやって曖昧さを消していくんだな～と勉強になった。

9月2週 (1週間前)

K問題を改題するモチベーションだったので、改題して最終形にした。(これはあとで書きますがめっちゃ苦労した)
あとは解説スライドをがんばってつくった。
結構気合入れて作っていて、修正や加筆は当日まで重ねた。

本番前日

HackerRankに問題を登録する作業をした。
結論から言うとこれは前日にやるべきでない作業だった。慣れてない状態だと特に、とても焦るので。
この辺の知見は別記事で残したい気持ちある (いつ書くかは未定... )
前日でやることになったのは、ちょうどお仕事で残業もあったのでやれなかったという事情があり。(仕方ないね)
一番焦ったのが、登録した問題でAC確認しようとしてて、午前3時ごろにやばい事態になってた。

何が起きたかと言うと、1問目を除いて、提出時に選ぶ言語が Ada しか選べなくなっていた...
というかAda って知ってますか？？ 下手したら全員 Adaで解かされるところだったので本当に焦った
原因はどうもHackerRankのバグっぽくて、使える言語の選択を選べる限り全部にチェックしていたらなぜかそうなってしまった。 デフォルトと同じにしたら got a kotonaki.

本番当日

あんまり寝ずに賞状を作って即コンビニプリントした。印刷がかすれてしまったの許さん。
副賞のバナナはmatsu7874氏が買ってきてくれた。
matsu7874氏が作ってくれた名札をチョキチョキしたりした。
会場の設営とかがんばった。
あとはHackerRankのトップページをいじったり、Twitterに告知したりした。

HackerRankのトップページ、何書いて良いか分からなくて適当を書いた。
上の英文2つは消せなかったのでシュールな感じになった。

本番中

コンテスト開始後はwriterルームからslackやTwitterや提出一覧を監視していた。
slackがclar地獄になったらどう対応しよう... みたいな状況も想像していたが、思いのほか至極平和で、若干手持ち無沙汰気味だった。
matsu7874氏はこのタイミングで解説スライドを書き始めて流石経験者だなと感じた。
全完もオンサイト・オンライン1名ずつでいい感じに時間いっぱい使ってもらったのでいい感じだった。(語彙)
何よりなんとか平穏無事に終わってよかった。

解説

12問ぶっ続けて喋ったのでめっちゃのど乾いた。
それよりもマイクがなくて聞こえづらかったみたいで本当にごめんなさい(事故だったのでは...)(教えて欲しかった...)

懇親会

たのしかったー！！
ほんっとうにポジティブな感想しか聞けなくて嬉しかった！！
色んな人に喜んでもらえて、がんばってよかったです

打ち上げ

おいしいお肉を食べ放題した！！！
直前でピザ食ったの忘れてたの、あたまわるかった！！

問題ごとの思い入れとか裏話とか

A - honda's janken

ABC-A を意識した。5分で生やした問題。
Twitterの某じゃんけん企画で本田の勝率が異常に高かったのでそのネタを利用。
問題文に「hondaは決して負けることはない」って書いたのにクスっときましたか？きてほしかった。

B - sentouryoku

これもABC-Bを意識した。5分で生やした問題。
肩慣らし的に、for文を回して問題文の通りにやらせるのがしたかった。
特に元ネタはないですがドラゴンボールの戦闘力はマジでインフレしすぎですよね。

C - mosaic tile art

もともと原案はN-Rook問題だった。
300点問題を作りたいなーと思って、N-Queenは実装重めなDFSっぽいけど、斜めの動きを封じるとただのN!になるよねーと気づいて出そうとした。
まあでもN-Rookってググると普通にN! だよと出てくるので、そうとバレない工夫が必要だった。
それでタイルの色ってことにして、N-1個の部分にフォーカスさせるような誘導を問題文で試みた。
白黒ではなくて白青なのはちょっとした狙いがあって、白vs黒だと色を対等に見られがちだけど青ってすると青のほうに注目するんじゃないかなーと。(根拠ないけどなんとなく心理的に)
ちなみにN*Nの正方形でなくN*Mの長方形だったら400点になって教育的にも良さそうだったけど、逆元の説明はめんどくさそうだったのでこれで。

D - n-dwich box

これはいつかローソンで買ったサンドイッチが、ここでいう2-ドイッチと3-ドイッチが入っていたことがあって、つまり|#||#|#| となっていて、3-ドイッチを2-ドイッチだと思って具の部分に指を突っ込んでしまい、ちょっとした怒りを覚えた体験が元ネタ。
この製品は2-ドイッチと3-ドイッチです、みたいに書いてほしいよね。
n-ドイッチという呼び方は私のお気に入り。

ありがとうございます。

E - usagi vs kame

性質の違う何かを競争させたい気持ちになって、うさぎとかめの童話を思い出して生やした問題。
なぜゴリラではないのか、とわりと疑問に思われたみたいだけどそんな理由でした。
kameを毎秒シミュレートするとTLEするけど、それをさぼれることに気づくと貪欲で解けるのがお気に入り。

F - mneme game

どうやって思いついたかあまり覚えていない。
mnemeという英単語は記憶能とかいう意味らしい。(なじみのない単語だったけど使ってみた)
想定解は二分探索だけど、別の賢い方法があればそれで解けてもいいかなと思っていた。
rian_tkb氏に、E問題と同じ解法で解けることを指摘いただいたが、私はそれまで気づかなかった。(目からうろこだった)
EとF、どちらも350点ぐらいの評価だったのであえてEを300、Fを400で出してみた。

G - double range queries

最初の原案は、重なる長方形領域というよりは、幅1の四角い輪っかだった。
ただ輪っかってことにしちゃうと愚直に外周をなぞるとカウントできてしまって、O(Q(R+C)) ぐらいで普通に通ってしまう。
どうせ2次元imosを使わせる想定なら、輪っかの形に限定しなくてもいいんじゃないかと気づいて、出題された問題になった。
2つの領域を裏返すと、結果はXORのような領域が裏返るため、あえて問題文は「Aに含まれてBに含まれない」「Bに含まれてAに含まれない」みたいにした。
あと解説スライドの2次元imosの図、地味にがんばった。

H - gori uho game

朝のゴリラジオ体操でARC038をやった回があり、 B - マス目と駒 を解いたときに、末尾から結果が決まる系のゲームDP、最近AtCoderで出てないな～と思って出題しようと思った。
状態をbitで持たせようと思ったのと、手でテストケースを作って検証するのを楽にしようとサイズは5x5に固定した (それでも正しさの検証はそこそこ大変だった)
Nは10じゃなくて12とか15とかでも良かったかも。まあいいか。

I - pino assort

全問題の中でwriterお気に入り。
実際に売られているリアルのピノアイスを制約に使うことにこだわった。
画像
この制約を使ってガチガチのナップサックDPを作りたかったがうまく作れず、制約をいじるという暴挙にでたｗ
少なくとも2つの味は1 、って制約をつけると貪欲に解けるようになることに気づいたので、それをそのまま出題した。(全然DPじゃない)
ちなみにwriter想定は400点だったがrian_tkb氏の見立てでは500点評価だったので、前日まで400点として出すか500点として出すか迷った。
当日は意外とさくっとACが出なかったので、500点で良かった。

J - swapping paths

これはDPの問題を作ろうと思ってうまくできたほうの問題。
横幅はだだっ広くする意味は特になくて、考察と実装を1ステップ加えるためだけについた制約。
自分で問題を設定して、それがギリギリ自力で考察できたときは何とも言えない嬉しさと楽しさを感じた。
横幅のめんどくさい制約を除くと正統派DPだと思っているので、よければ練習にどうぞ。

K - fuzzy search queries

これは一番の意欲作で、最も労力を割いた問題、に結果的になってしまった。
最初はsimple search query という題目で、部分文字列が含まれるかどうかのYES/NOだけだった。しかも制約も|S| <= 1000 だった。
題意としてはSAでもロリハでもいいからいい感じの文字列アルゴリズムを貼れば楽勝、みたいにするつもりだった。
制約が|S| <= 1000というのは私がSuffix Arrayというものをとんでもなく勘違いしていて、なんと全てのsuffixを配列に詰めてソートしただけだと思っていた！ｗ
実際は線形メモリで作れるんだよとkyuridenamida氏 に教えていただき、ありがたかったです (蟻本を読みましょう！ｗ)
それならばということで制約を30000にして、さらにせっかくSAを想定解にするのだからSAの旨味を使った問題にしようと改題を試みた。
蟻本のSAのページも読んでいなかったので、ちゃんと読んで理解することにした(それがなんと1週間前！)
クエリと同じ長さかつ、辞書順でクエリの直後に来る部分文字列を出力する、ってのがその部分で、改題案自体はすぐに思いついたけど、ちゃんと解くにはめちゃめちゃ頭つかった。
解説スライドにも書いた、愚直に文字数チェックしていくのは間に合うか？という問題が愚直では間に合わないと思っていて、BITと二分探索を駆使して無駄に高速化を試みたけど2時間以上バグらせまくりでつらかった。
それを作問slackで相談したら実は愚直で大丈夫ってことをkyuridenamida氏が指摘してくれて、got a kotonaki.
(結局自力でそこまでは考察しきれなかったな～って感じ。計算量の見積もりはちゃんと考えましょう)
すごく勉強になって得るものが多かった問題。

L - rivals

matsu7874氏の作問。
問題案を見た時にまったく解法が見えなくて、2週間ぐらい解けなかった。
2週間ぐらいたった時に見直して、累積和を使ってがんばったら解けた。
これはLやRが1000以下であるから解けるやり方で、10^5 だとこのやり方はだめだった。
writer解はセグ木なのでたぶん10^5 いけたと思うのですが、そうしなかったのはやさしさだなぁと思った。

おわりに

#ゆるふわオンサイト タグ、もう本当に嬉しい反応しかなくて、感激です
#ゆるふわオンサイト - Twitter Search

お忙しい中testerを引き受けてくださった、kyuridenamida氏、rian_tkb氏には本当に感謝です。 おかげさまで、問題の質がブラッシュアップされていきました！
matsu7874氏は会場の手配、ピザや飲み物の手配から、諸々の調整、slackやGitHubの環境、作問ノウハウの提供などありがとうございました！

最後に、実際に参加してくれたり、Twitterで感想書いたり、ブログ書いたりしてくれた皆さん本当にありがとうございました！！！