yukicoder 423-426 作問記録

投稿型プログラミングコンテストであるyukicoderで、僕が作った4問でコンテストが開かれた。yukicoderは最近勢いのあるコンテスト基盤で、気軽に皆が問題を投稿できることが特徴である。16世紀のルネサンスのような、問題を出し合って解き合う雰囲気が楽しい。作問時のyukicoderの管理人とテスターとのやりとりは、自分の勉強にもなった。

 

作問の流れは、以下のようになっている。

  • 問題を作る
  • テスト入力を作る
  • 解説を書く
  • テスターと呼ばれる人とやりとりし、問題が正しく作られていることを確認する。問題のより良い解法を一緒に模索する。
  • 実際に問題を出す
  • コンテスト中の質問に答える
  • 最終的な問題の不備を修正する

作問の練習用に、AからCまではやるだけという感じの問題を作った。D問題は自分で作っておきながら難しすぎたので、らてさんと相談しながら{O(\sqrt{n})} 解を実装した。のちに、りあんさんと相談していたら{O(\log n})解が爆誕した。

 

テスターとのやりとりが非常に勉強になった。

C問題では難易度見積もりでテスターと議論があった。僕の難易度見積もりは★2だったのだが、確率問題なので★3とした。一方、テスターのbtkさんは数学的厳密解を出そうとしたために★4と見積もった。このテスター解（確率を行列演算で求める方法）が面白かったのだが、制約がキツいので誤差の問題でこれが通らない。テスター解を通すために、制約を緩和したのだが、それでも通らなかったのでテスター解を想定解とするのを諦めた。

D問題では、想定解は平方分割で{O(\sqrt{n})}解法だったが、テスターのりあんさんがO(\log n)解を出してくれた。これを想定解とするように制約をキツくする調整を行った。さらに、りあんさんはテストケースの追加指示・解説のミス指摘など、多くの貢献をしてくれた。考察が終わってみると実装も比較的軽く、綺麗なコードになるのでいい問題になったと思う。勉強にもなったし、いい問題になったと思うが、問題完成がコンテストの10時間前だった。

 

AがWA祭りになった。コーナーケースの問題を出そうとしていたから、予想していたのだが、さすがに一発ACが10%しかいないのは、問題がダメだったなあと思った。leading zerosの厳密な定義を書いていなかったのもよくなかった。

 

Dはコンテスト中に★4から★5に格上げされた。★4にしたのは、解答を聞いてみればただのsegment treeなのと、この解答を出してくれたテスターが黄色だったから。黄色上位なら解けるだろうと思っていた。甘かった。実際には、btkさんと、LGMレベルのantaとyosupoさんの3人しかコンテスト中に解けなかった。

 

Dの非想定解{O(q^2})が出た。初期値が単位行列であることと、クエリ数が小さいので疎であることを利用した解答だった。やはり作問には自分のアルゴリズム力が重要であることを再確認した。

 

Dのリアクティブの設定が上手く言っていなかった。コンテスト後に管理人に指摘され、リアクティブを問題文から消す羽目になった。クエリ先読みしても大して解法が増えなそうだったので、コンテスト後に問題文から全削除した。

 

D問題の解説が間違っており、数人の時間を無駄にした。数学的にきちんと書いたつもりだったが、一箇所添字が間違っていた。コンテスト後、解説をそのまま忠実に実装したkmjpさんとpekempeyさんがWAを出しまくっていて申し訳なかった。

 

総じて、楽しくやりとりしながら作問できた上、勉強になったので良い経験だった。

CODE FESTIVAL 2016 qual A 参加記録

日本最大のオンサイトプログラミングコンテスト、CODE FESTIVALの予選に参加した。プログラミングコンテストと言うが、実際にはアルゴリズムコンテストという感じ。このコンテストは、大学生・大学院生・未就業者を220人（！）集めて開催される。人数が多いので、予選突破が容易である。むしろ普通の人間がこれ以外でオンサイトに参加するのは困難だと思う。

 

code-festival-2016-quala.contest.atcoder.jp

 

日本人学生100人が通過する中で、社会人を含めた順位で115位だった。通ってるかどうか怪しい。問題は5問で120分。A, B, Cまで13分で解けた。Cはかなりどうでもいいバグを埋め込んで時間を5分近くロスした。Dは提出したが間違いだった。とてもUnion-Find Treeっぽいなあと思いながら、ゴリゴリ場合分けしたので、アルゴリズム力不足だった。残念。

 

火曜日（予選3日後）に、予選通過のメールが届いた。

ブログの目的

今後、イベント参加の記録にブログを使う。最近、オンサイトのプログラミングコンテストやハッカソン運営や、博士課程教育リーディングプログラムフォーラム、その他さまざまなイベントに参加する予定がある。今までも、IMPACT学生討論やらロボコンやらロボコンやらロボット系のテレビ出演が多数あった。TOYOTAのハッカソンに出たり、Engadget Fesのハッカソンにも出た。ちょうど今、ドイツ留学が終わろうとしている。これらの記録・発信をしないのは、機会と人生の損失に思えるので、このブログを立ち上げる。

 

今まで、自鯖でWordpressを運営してきたが、テーマの編集性が低かった上に管理が絶望的に困難だったので、はてなブログに移行することにした。 

 

勉強記録は、ブログでは情報集約性が低いので、リンクを張るだけに留めたい。僕はプログラミングコンテストの記録、チャレンジの記録、CTFの記録、論文の記録、レストランの記録などをGoogle Driveにつけている。これをブログに書くのが薄まるので、リンクを張るためだけの投稿をする。

 

技術や生活は、Wikiに全部まとめているので、はむこのスキルセットに興味があればこっちを見てね。