An Engineering Student's Frank Report.

どこかの工学系学生の覚え書き的な何か。

Hachiji Contest 開催記

はじめに

ブログではお久しぶりということになります。はちじです。

さて,私ですが,先日2022年3月3日(木)21:00~23:00に,学科の授業・実験などをネタとした「Hachiji Contest」を開催しました。

www.hackerrank.com

そこで,今回は,その感想や裏話などを書いていきたいと思います。

コンテストの各問題について

コンテスト全体の各データ

  • コンテスト終了時間までのサインアップ人数 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)

学科の実験で(私はその実験を選択していませんが),オープンソースソフトウェアを自由に選び,その機能拡張をはかる,という実験がありました。その実験において書かれた記事のひとつに,アルゴリズムとデータ構造の力で機能拡張をはかっている,以下の記事がありました。

qiita.com

アルゴリズムとデータ構造が好きな私としては,この記事を読んで黙ってはいられないと思い,この記事を題材とした競プロの問題を作ろうと思い至りました。どのような問題にするか少し迷いましたが,最終的に「記事内にあるオイラーツアーの頂点追加の原理を問うた上で,記事を知らなくても解くのに困らないような問題設定にするのが良い」と考えた結果,このような形となりました。

実験をやっていた人からどう思われるかがやや心配でしたが,おおむね好評だったようで良かったです。

ちなみに,Pythonだと想定解でも1sec以上かかってしまい(PyPyは再帰が遅いので,スタックを使ってオイラーツアーを書くか,遅いの覚悟でPython3で提出するしかない),TL4secに引き上げたにしては大丈夫か少し不安ではあったのですが,Pythonで提出した人がちゃんと正解できていたようで良かったです。

正解者は想定より多かったです。

F問題 - Mitsu-Detection Machine

  • 正解者:9人

  • First AC:Sapphire15kyopro(25:56)

電子工作の授業の発表で「密を検知して音で知らせるマシーン」について発表している人がいたことから着想を得て,問題を作成しました。

当初は Xが固定の値として与えられており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を復元する際,「 i番目の7セグメントLEDで数字 kを作れるか」という条件を見落とし,ペナを出している人が多かったです。ただ,その多くは気が付き,最終的には正解できていました。

多くはbool型の二次元DPテーブルの復元によって解いていたようですが,文字列を持ったO(N2 K)のDPで(しかも時間に余裕を持って)通している人もいました。これについては, Nの制約をもう少し大きくすべきかな( N \leqq 500とか N \leqq 800とか)とも少し思っていたのですが,文字列を使ってDPするにしても,状態数じたいがそこまで多くないということがあり,おそらくこれについては落とすことは厳しいだろうと考えています。

終了直前にACしている人が多く,見ている側としてもびっくりしました。

余談ですが,今回,6完が一人も現れず,A~Fを正解した人は全員Gも正解していました。問題文の最後に「ここまで来られたキミなら解けるはず。こわくないよ。」というのがありますが,まさか本当にA~Fを解いて最後にGに臨んだ人が全員正解してくる展開になるとは思っておらず,個人的にこの展開は熱い展開でした。

コンテスト全体の所感

個人的に,特に後半の問題の置き場所については,難易度差がすぐにはわかりにくいようなタイプの問題であったこともあり,けっこう迷いました。要求される知識や実装量などを鑑みた結果,今のような配置に決めたのですが,結果的には正解者数が見事に広義単調減少になっており,問題の置き場所はこれで正解だったようです。

当初,けっこう時間がかかるセットだろうと踏んでコンテスト時間は150分で設定したのですが,テスターから「このセットの難易度だと,150分もあると上位陣が暇しそう」という意見が飛んできたということで,120分にしました。(ただ,参加者からはコンテスト時間はもっと長いほうが良いという意見もみられたようです。コンテスト時間の設定は難しいですね。)

全体的に想定よりも多くの人に解かれていたように思います。全問正解者がここまで出るのも予想外でした。

コンテストとして簡単だったのではないかとも思われがちですが,もとより,今回のコンテストのメインのターゲット層が学科の同期や後輩(予想外に先輩も参加してくださり非常に嬉しかったです!)であり,必ずしも全員が全員競プロの強者とは限らないため,基本的には解ける問題の数が多いほうが多くの人にとって楽しめるであろうことを考えると,あまり問題を難しくしすぎるのもどうかと思い,個人的にはこの難易度で良かったと思っています。ただ,いわゆるボス問的存在の高難易度の問題を1問置くなどは考えてもよかったかもしれません。

大変だった点

何より,コンテスト開催じたいが今回が初めてなので,慣れないところがあったのが大変でした。

今回,出したかった問題にグラフ問題が多く(D,E,Fの3問がグラフ関連の問題だった),初めてテストケースを作る身としてはかなり大変でした。色々調べながらやったのですが,正直テストケースが甘いのではないかという不安がありました。結果弱すぎるということはなく,そこはひと安心でした。

終わりに

今回,人生で初めて自分で作問した問題でコンテストを開いたわけで,うまく開催できるのかという不安もありましたが,ふたを開けてみると学科の先輩にも参加していただいたりなどと想定より多くの人に参加していただけました。特に不備やトラブルもなく,大変好評だったようで,開催できて本当に良かったと思います。またこのような機会があれば自分で作問した問題でコンテストを開いてみたいものです。もっと実力がつけばyukicoderでの作問なんかもやってみたいものですね。

それでは。

なつやすみ 52-53日目

何をしてもお腹は空く。

DBでやったこと

午後試験を1問。

この試験はマジで知識ゲーではなく,この試験を制するには解くための特別な訓練が要るのだということを思い知らされる。果たして本番までに間に合うのだろうか,覚悟が必要そうである。

DB以外でやったこと

ABC220に出た。Eが解けなくてまたレートを溶かしてしまった。競プロの調子がマジで悪すぎるよ!

 

空腹だけはなんとかしてくれと切に願った。

なつやすみ 51日目

ああああああああああああああ。

DBでやったこと

午後試験,1問。

DB以外でやったこと

ARC127に出たが,手も足も出ずに終わった。

このBに気づけないのは流石にマズイ。あれなんで解けなかったんだ?

 

履修決めをおおよそやっておいた。迷うところはあるけど,おおかた決めるべきところは決めたと思う。

 

せめてABCこそは......

なつやすみ 50日目

DB試験も迫っているので(?)DBとそれ以外に日記のレイアウトを変えようかな。

DBでやったこと

もしかしたら読んでみたら色々変わるかなと思い,ここに来てDB対策の記事を色々読んでみた。感じたことは,「午後試験が長文で大変」「午後試験がやはり最大の山」だということであった。これを肝に銘じて,午後試験の対策に力を入れていきましょう。

それ以外でやったこと

人生で初めてひとりでからおけに行ってきた。*1サービスもすごく良くてそれなりに楽しかった。

 

yukicoderに出た。

本当に調子が悪く,なんと最初の簡単な問題しか解けなかった。ひとりでからおけに疲れていたのももしやあるかもしれないけど,それにしても明らかに調子が悪すぎる。

 

明日と明後日でARC,ABC。しっかり成果を出したいもの。

*1:複数人で行くことは割とありました。ですがひとりで行くのはなんとこれが初めてなんです。

なつやすみ 49日目

3A授業開始まであと一週間余り。

DB試験まであと二週間余り。

どう考えてもマズイですね,はい。

競プロ

今日は第五回PASTバチャをやってみた。

結果は70点中級という何とも微妙な結果に。え,この回さ,実装量やばくない?

DB

寝る前に午後試験の対策。見てみた感じ,午後試験はどうやらこれ特有の特別な訓練が要りそうで,午前試験がAPに比べてぬるい(要検証)ぶんだけ午後の対策をかなり重点的にやる必要が出てきそうな気がする。

 

これから先,午後試験対策をさぼっているところを目撃したら叩き起こしてください。

なつやすみ 48日目

気持ちが上がらなかったのと,諸事情もあってやることが色々あり,しばらく日記を書いていなかったです......

もはやなつやすみもあと少しになっている感じもありますが,今日から再開します。

競プロ

青diff埋め。黄diffにも手をつけたいかなぁ。

DB

主に午前試験の過去問を演習。同じような問題が繰り返し出題され続けていることに気づき,本当に知識として定着しているのかが気になるところ。

 

明日はPAST一本走ってあとはDBやろうかなって感じ。

なつやすみ 42日目

全身痒いが今日はおさまっていることを願う。

競プロ

青diffを数問埋めた。最近は試験管問題を埋めるのにハマっているが,昔の問題もそれはそれでけっこう教育的だと思うのよね。

DB

午前II試験の分野の全体的な勉強。もうそろそろ午後試験のほうの対策にも取り掛かりたさがある。

その他

全身痒いは昨晩にもあるにはあったが,そこまでではなかった。ただ,暑くて朝の4時まで寝られなかった。

 

AP受験する周りの人が焦りはじめているのを見て,いやぁこっちもそろそろDB本腰入れないとなぁという気持ちになりつつある。