この記事はNTTコミュニケーションズ Advent Calendar 2020の9日目の記事です。昨日は @tetrapod117 さんのうちでChrome拡張機能を作ろう
でした。
はじめに
こんにちは@y-iです。普段はNTTコミュニケーションズでSkyWayの開発をしています。
2020年8月21日にNTT Coding Challenge #3をオンライン上で開催しました。
この記事では当日のスケジュールや事前準備についてどのように行ったかを書きます。
NTT Coding Challengeとは
NTT Coding ChallengeはNTTグループの社員が開催するグループ内の社員向けの競技プログラミングの大会です。
競技プログラミングを雑に説明すると与えられた問題に対して実行時間や使用メモリの制限を満たしつつ、正しい答えを出力するプログラムをできるだけ多くできるだけ早く提出できるかを競うものです。誤ったプログラムを提出すると順位付けの上でペナルティが発生するため、コーナーケースのカバーなどの正確さも求められます。普段社内ではAtCoderで開催されるコンテストの感想を話したり、バーチャルコンテストをやったりすることもありました。
上の活動は特に社内で宣伝はしていませんが、NTT Coding Challengeについては各社内で宣伝しており幅広い参加者が参加していました。加えて第3回では内定者の一部の方にも参加いただきました。
第1回は2019年12月に開催しました。その様子については、弊社ブログの開催レポートをご覧ください。
オンラインでの開催
第1回ではブログの写真のとおり弊社内の会議室で物理的に集まって開催していましたが、新型コロナウイルスの影響によって第2回以降は運営側、参加者側共に一箇所に集まらずにオンライン上で集まる形になりました。
コンテスト後の懇親会が開催できないため参加者の交流という面ではマイナスですが、プログラミングコンテスト自体はもともとオンライン上で開かれているのが一般的なため問題なく開催・進行できました。また、後述のLTによって交流がある程度できたのではないかと思います。
当日の流れ
コンテスト当日は以下のようなタイムテーブルで開催しました。当日は百人弱の参加者が本番のコンテストに参加しました。
| 時間 | 内容 |
|---|---|
| 13:10-14:15 | チュートリアルコンテスト |
| 14:30-16:30 | 本番コンテスト |
| 16:40-18:00 | コンテスト解説 |
| 18:10- | LT |
チュートリアルコンテスト
チュートリアルコンテストはタイムテーブルの最初にありますが任意参加のコンテストになっています。
NTT Coding Challengeの参加者は普段からプログラミングコンテストに参加している人から競技プログラミング初心者まで幅広く存在するため、競技プログラミングやジャッジシステムへの提出に慣れてもらう目的でこのコンテストを行いました。
普段から使い慣れている言語でも言語や業務内容によっては標準入出力を全く扱わない場合もあるため、そういった入出力の扱いや改行の有無、出力が整数か小数かなど、コンテスト本番に出て慌てないように適宜説明やヒントを挟みながら行われました。
このようにチュートリアルは得点を競うコンテストではないため、問題数は2問で第1回から同じ内容のコンテストを開催しています。
本番コンテスト
こちらが今回のメインイベントで2時間で6問の問題を解くコンテストになっています。上のチュートリアルコンテストで初めて参加した初心者でも解けるような問題から普段参加している人でも考えるような問題まで難易度に傾斜がつくように出題しました(結果的には最初の方の問題は想定より難しくなってしまいました)。
順位を競い合うコンテストではありますが社内のエンジニアのスキルアップも開催目的の一つであるため、A問題などについてはコンテスト中ある程度時間が経った後に追加のヒントとなるケースをslack上に投稿するといった解いてもらうための工夫をしています。
コンテスト解説
コンテスト終了後は作問者がそれぞれ自身の作成した問題について問題の意図や解法、コーナケースについての解説をスライドを映しながら行いました。解説の他にも想定解法の行数やコンテスト中のFAを誰が取ったかなども共有しました。
スライドのURLは共有されているので、参加者は後からでも見直すことができるようになっています。また、コンテスト後は他の参加者の提出内容も見ることができるので自分の実装の何が悪かったかを見ることもできます。
slack上ではそれぞれの問題の感想のスレッドが作られ、こんなふうに考えていた、こんなコーナケースでハマった、と参加者同士で盛り上がりを見せていました。
他にもA問題のコードゴルフ1を楽しんでいる参加者もいました。過去のコンテストの問題のコードゴルフでは運営の作った短縮済みのコードと比べて更に半分以下の長さへの圧縮をした参加者もいました。
各問題の解説の後は講評と表彰を行いました。
講評では参加者数やそれぞれの問題の出題意図や正答者数について話しました。
表彰では上位3名を表彰し、それぞれ一言コメントをいただきました。他にも特別賞をAのshortest codeと最後に得点をした参加者に授与しました。
LT
オンライン開催のため懇親会が開けなくなった代わりに今回はLTを行いました。競技プログラミングに便利なツールの紹介や問題を解くテクニックなどいろいろな内容のLTが行われ、slack上で非常に盛り上がっていました。
コンテスト運営
事前準備
コンテストで出す問題は各自で問題を考えて非同期でGitHubにpushするような運用にしていました。以前のコンテスト向けに作って使わない問題もあったためコンテスト開催に向けて問題が足りないということはありませんでした。
開催の2ヶ月ほど前にコンテストの日程を決めました。8/21になったのは、金曜日だと次の日が休みのため気持ち的に参加しやすいのと月末だと月末の処理で参加できないということがあるかもしれないのでそれを避けるという理由だったと思います。
開催の1ヶ月ほど前に出す問題を決め、それぞれの問題のテスターを決定しました。
その後はテストケースを作ったり解説を書いたり、テスターが問題自体やテストケースをチェックしたりしていました。その結果、入力の制約が変わった問題もありました。
問題はrimeで必要なファイルをリポジトリで管理しているため、必要なコマンドを入れれば互いに動作チェックしやすい環境でした。
当日の運営
コンテスト中は運営メンバーで通話しながら参加者から来た質問に対して対応を考えたり、問題の提出状況やソースコードを見ていました。
質問についてはslack上で投げ、それが運営側のprivate channelに流れるようなbotを作ったので、運営メンバーで簡単に質問を共有できる上に対応も同時に考えられたのでスムーズに進められました。
誰もAC2していない問題でWA3が出ると、想定解が違うのではないかと不安になりコードをチェックしていました。今回のコンテストでは想定解の不備は見つからず、提出コードのここが違うというのを運営で確認できたので安心できました。逆にACが出ている問題でWAが続いているコードを見て、ヒントを出そうか考えるということもしていました。
今回のコンテストでは想定しない解法が何種類かACしてしまうことがありました。
B問題では愚直に実装すると最大$10^{18}$回のループを回す必要があるテストケースが存在し、$O(N)$で計算するとTLE、時間計算量を改善しても途中の値の桁数が非常に大きくMLEになると思っていました。
しかし、for文でfor(int i=0; i<n; ++i)としているコードがACしているのを発見しました。運営でデコンパイルなどで検証したところ、gccに-O2オプションを渡すと最適化の結果while文になり、オーバーフローした結果間に合うということがわかりました。他にもnumpy.power(x1,x2)を使ってACしているコードも存在しました。
これらは計算結果の値は正しくないのですが、この問題のこのようなコーナーケースでは最後に0を掛けていたため値にかかわらず計算さえ間に合えば問題ないという風になってしまいました。
感想
難易度調整をしたつもりだったのですが、最終的にB問題の正答者がC問題よりも少ないという結果になりました。配点は100-200-200-300-300-400としていたので大きくは外れていなかったのですが難易度の推定は難しいなと感じました。
一方で全完は3人という結果になり、上位層が時間ギリギリまでかかっているためコンテスト時間に対する問題全体の難易度はちょうど良かったと思います。
普段自分が参加しているコンテストでも問題難易度調整は難しいんだろうなというのを少し想像できるようになりました。
問題作成自体についてもあまりない経験だと思うのでやってみることができて良かったです。
また、これからも継続的に開催できればと思います。
おわりに
明日は @yuki_uchida さんのWebTransportとWebCodecsでビデオチャットを作るチュートリアルです!お楽しみに!