はじめに
ブログではお久しぶりということになります。はちじです。
さて,私ですが,先日2022年3月3日(木)21:00~23:00に,学科の授業・実験などをネタとした「Hachiji Contest」を開催しました。
そこで,今回は,その感想や裏話などを書いていきたいと思います。
コンテストの各問題について
コンテスト全体の各データ
コンテスト終了時間までのサインアップ人数 31人
提出者数 24人
全問正解者数 8人
上位5人(敬称略・括弧内は全問正解時のタイム)
1位 sayakaamemiyag(38:00)
2位 eeic_is_black(69:25)
3位 YSatUT(84:38)
4位 Ricky_pon(97:23)
5位 packer_jp(98:54)
A問題 - Decibel
正解者:23人
First AC:eeic_is_black(0:51)
おそらく多くの人が最初に開く問題ということで,ABCのA問題同様,簡単な入出力と演算が書ければ解けるような問題を置くことにしました。
簡単な演算で解ける問題しか置けないということで,実は逆にこの枠に何を置いたらよいのか地味に悩みました。最終的に,簡単な四則演算で解ける上に,学科で授業を受けてきた中でしばしば登場する,デシベルの計算問題を置くことにしました。
特に詰まった人もおらず,A問題として適切だったように思います。
B問題 - Do Not Drink Too Much
正解者:22人
First AC:eeic_is_black(2:56)
単純なif文の問題に見せかけた小数誤差の問題です。
ここで少し時間を食ってしまったりペナを出してしまう人が多くいたりするかなと思っていたのですが,この手の小数誤差の問題はAtCoderなどでも一時期しばしば出題されていたことや,今回の主なターゲット層が情報系学科の人であることなどもあり,ノーペナで突破したり,ペナを出してしまってもすぐに気づくことができたりと,想定よりよくできていたようでした。
なお,C++でlong doubleを使っただけのコードも今回のテストケースで落としています(実際何人かそれで落としました)。また,小数を単にそれぞれ10倍しただけ(整数型に直していない)で判定したコードが通っていましたが,残念ながら今回の制約下でそのケースを落とすことはできません。ただ,B問題なのもあり,そんなにあまりにも厳しくしすぎるのもどうかと思ったので,誤差に少しだけ気を遣いさえすればACできてしまうことについては特に気にしないことにしました。
ちなみに,当初はこの問題が整数のみの制約でA問題として置かれており,B問題に現在のA問題を改変したものが置かれて誤差問枠になっていました。しかし,そうすると誤差問としてうまくいかないことが判明しました。そのため,現在のような位置に置くという形となった,という経緯があります。
C問題 - Psychological Distance
正解者:22人
First AC:sayakaamemiyag(4:34)
授業で「グレイコード」が登場したということで,グレイコードに気づければすぐに解ける問題を出題してみました。
全探索などの単純なアルゴリズムで解けるような問題ではなく,ある程度の考察や知識が必要なため,BとCの間で差がつくかなと思っていたのですが,意外や意外,CもBと同様によく解かれていました。元々グレイコードが題材の問題のため,学科民が有利な問題ではありますが,Bが解けてCは解けない,というようなレベル層の人が今回はいなかった,ということがあるかもしれません。
D問題 - Many Processes
正解者:15人
First AC:sayakaamemiyag(8:58)
OSに関する授業を受けていたということで,プロセスの依存関係を題材として,それを競プロにアレンジして出題しました。
このセットのA~Cはほぼ実装が要らないタイプの問題なので,ここから実装が複雑になっており,やはりと言うべきか,すぐにはそんなに多くの正解者が出ませんでした。ただ,最終的な正解者数は想定していたよりも多かったです。
解法については,優先度付きキューを持っておいて時系列順にシミュレーションをする,という解法を想定していましたが,テスターから,トポロジカルソートを普通にやっていく過程で時間の情報を別で更新する,という解法が飛んできました(実はそっちの解法については思ってもいませんでした)。正解者の大体がこのどちらかの解法を選択しており,ほぼ半々でした。この2つに比べると数は少ないですが,トポロジカルソートの過程でSCCを持ち出していたり,DFSを使って解いていたりした人もいたということもあり,この問題に関しては,人によって本当に解法が分かれると思います。
E問題 - Gyoza Tour
正解者:12人
First AC:sayakaamemiyag(18:24)
学科の実験で(私はその実験を選択していませんが),オープンソースソフトウェアを自由に選び,その機能拡張をはかる,という実験がありました。その実験において書かれた記事のひとつに,アルゴリズムとデータ構造の力で機能拡張をはかっている,以下の記事がありました。
アルゴリズムとデータ構造が好きな私としては,この記事を読んで黙ってはいられないと思い,この記事を題材とした競プロの問題を作ろうと思い至りました。どのような問題にするか少し迷いましたが,最終的に「記事内にあるオイラーツアーの頂点追加の原理を問うた上で,記事を知らなくても解くのに困らないような問題設定にするのが良い」と考えた結果,このような形となりました。
実験をやっていた人からどう思われるかがやや心配でしたが,おおむね好評だったようで良かったです。
ちなみに,Pythonだと想定解でも1sec以上かかってしまい(PyPyは再帰が遅いので,スタックを使ってオイラーツアーを書くか,遅いの覚悟でPython3で提出するしかない),TL4secに引き上げたにしては大丈夫か少し不安ではあったのですが,Pythonで提出した人がちゃんと正解できていたようで良かったです。
正解者は想定より多かったです。
F問題 - Mitsu-Detection Machine
正解者:9人
First AC:Sapphire15kyopro(25:56)
電子工作の授業の発表で「密を検知して音で知らせるマシーン」について発表している人がいたことから着想を得て,問題を作成しました。
当初はが固定の値として与えられておりYes/Noで答えさせる,という問題だったのですが,せっかく二分探索で答えさせられる問題に出来るのにそれを生かさないのは勿体無い,と思い,今のような設定になりました。
解法については,二分探索を用いた解法と,Union-Findで頂点を距離について降順に見て辺を適宜つないでいく解法の2つに大きく分かれますが,多くが前者を選択していました。また,前者を使う場合に判定問題をどのようにして解くかに関してもバリエーションがあったのですが,Union-Findを使うという人が多く,次点でBFSが数人いた,といった感じでした。
余談ですが,(PyPyなら通るのですが)Python3だと,二分探索のほうの解法が落ちます。今回この問題をPythonで通している人はいなかったのですが,少し制約の厳しめな問題だったかもしれません。
正解者は,絶対数で言うなら想定より多かったのですが,ほかの問題と比較した相対数で言うと,そこまで多くはならなかった,という感じです。ペナ率が予想よりかなり高かったです。
G問題 - Illumination of 7-Segment Display
正解者:8人
First AC:sayakaamemiyag(38:00)
F問題と同様に,電子工作に関する授業を受けて,7セグメントLEDを使った人がいたことから着想を得ました。
DPを復元する際,「番目の7セグメントLEDで数字
を作れるか」という条件を見落とし,ペナを出している人が多かったです。ただ,その多くは気が付き,最終的には正解できていました。
多くはbool型の二次元DPテーブルの復元によって解いていたようですが,文字列を持ったO(N2 K)のDPで(しかも時間に余裕を持って)通している人もいました。これについては,の制約をもう少し大きくすべきかな(
とか
とか)とも少し思っていたのですが,文字列を使ってDPするにしても,状態数じたいがそこまで多くないということがあり,おそらくこれについては落とすことは厳しいだろうと考えています。
終了直前にACしている人が多く,見ている側としてもびっくりしました。
余談ですが,今回,6完が一人も現れず,A~Fを正解した人は全員Gも正解していました。問題文の最後に「ここまで来られたキミなら解けるはず。こわくないよ。」というのがありますが,まさか本当にA~Fを解いて最後にGに臨んだ人が全員正解してくる展開になるとは思っておらず,個人的にこの展開は熱い展開でした。
コンテスト全体の所感
個人的に,特に後半の問題の置き場所については,難易度差がすぐにはわかりにくいようなタイプの問題であったこともあり,けっこう迷いました。要求される知識や実装量などを鑑みた結果,今のような配置に決めたのですが,結果的には正解者数が見事に広義単調減少になっており,問題の置き場所はこれで正解だったようです。
当初,けっこう時間がかかるセットだろうと踏んでコンテスト時間は150分で設定したのですが,テスターから「このセットの難易度だと,150分もあると上位陣が暇しそう」という意見が飛んできたということで,120分にしました。(ただ,参加者からはコンテスト時間はもっと長いほうが良いという意見もみられたようです。コンテスト時間の設定は難しいですね。)
全体的に想定よりも多くの人に解かれていたように思います。全問正解者がここまで出るのも予想外でした。
コンテストとして簡単だったのではないかとも思われがちですが,もとより,今回のコンテストのメインのターゲット層が学科の同期や後輩(予想外に先輩も参加してくださり非常に嬉しかったです!)であり,必ずしも全員が全員競プロの強者とは限らないため,基本的には解ける問題の数が多いほうが多くの人にとって楽しめるであろうことを考えると,あまり問題を難しくしすぎるのもどうかと思い,個人的にはこの難易度で良かったと思っています。ただ,いわゆるボス問的存在の高難易度の問題を1問置くなどは考えてもよかったかもしれません。
大変だった点
何より,コンテスト開催じたいが今回が初めてなので,慣れないところがあったのが大変でした。
今回,出したかった問題にグラフ問題が多く(D,E,Fの3問がグラフ関連の問題だった),初めてテストケースを作る身としてはかなり大変でした。色々調べながらやったのですが,正直テストケースが甘いのではないかという不安がありました。結果弱すぎるということはなく,そこはひと安心でした。
終わりに
今回,人生で初めて自分で作問した問題でコンテストを開いたわけで,うまく開催できるのかという不安もありましたが,ふたを開けてみると学科の先輩にも参加していただいたりなどと想定より多くの人に参加していただけました。特に不備やトラブルもなく,大変好評だったようで,開催できて本当に良かったと思います。またこのような機会があれば自分で作問した問題でコンテストを開いてみたいものです。もっと実力がつけばyukicoderでの作問なんかもやってみたいものですね。
それでは。