エンジニアの kenkoooo です。

RCOアドテク部では、数名の社員やゲストが飲食しながら自分の好きなテーマで発表する「アドテク部勉強会&TGIF」なるものが隔週金曜日の夕方に行われています。第60回の勉強会は、「プロコン部祭」というテーマで、 RCO プロコン部 の shiratty8 さんが「プロコン部活動の紹介をしつつ、RedCoder のヤバさを体感してもらう」というテーマでエキシビションマッチを開催したほか、tomerun さんによる「マラソンマッチのビジュアライザ鑑賞会」が行われました。

プロコン部活動の紹介をしつつ、RedCoder のヤバさを体感してもらう

RCO プロコン部とは、プログラミングコンテスト好きの社員によるサークルですが、中でも uwi さんはトップクラスに強く、 HackerRank で現在世界ランク 1 位であるほか、他のコンテストサービスでも最上位クラスの RedCoder の称号を持つトッププレイヤーです。

今回は、その uwi さんに、私 kenkoooo と先輩の iehn さんがコンテストで挑むというエキシビションマッチを観戦しつつ、他の社員にプロコンの世界観を解説するという発表でした。私も iehn さんも決して弱くはないと思いますが、我々が 30 分かけて2問を解いている間に uwi さんが 4 問全てを解き切り圧勝しました。それはそうですね。

今回解いた問題と結果は以下のとおりです。

G 問題レビュー

せっかくなので今回解いた「G - 主菜と副菜」という問題を紹介します。

この問題は、「主菜を選んだ後の残金で、できるだけ副菜を詰め込む」という ナップサック問題 を、全ての主菜について 動的計画法 (Dynamic Programming, DP) で解き、その中で最大値を求めれば良いです。この時、副菜が M 個、お金が L あるので、主菜を選んだ後の残りの残金の中に副菜をできるだけ詰め込む DP で O(LM) の計算量がかかり、主菜が N 個あるので、 O(LMN) の計算量になります。ここで、「残金が l の時にできるだけ副菜を詰め込んだときの最大値」を DP で求める際に l 以下の残金についても計算ができていることを利用すると、O(LM) の DP は 1 回だけやれば良いことになり、全体の計算量は O(N + LM) となります。

マラソンマッチのビジュアライザ鑑賞会

短時間で正確に問題を解いていくコンテストのみならず、1 問を長時間かけてじっくりと解き、より高い点数を出すプログラムを作る「マラソンマッチ」と呼ばれるコンテストも得意とする tomerun さんに、過去に解いたマラソンマッチの問題を解説してもらいつつ、その結果を可視化する ビジュアライザ をみんなで眺めました。tomerun さんは topcoder Marathon Match で世界ランク10位のマラソンマッチ古参プレイヤーで、いままでに解いて来た様々な問題を可視化していただきました。この手のコンテストは1問2週間ほどの体力勝負になるのですが、そんな問題を本当にたくさん解いていて圧倒されますね……

今回のご飯

今回のご飯は寿司でした。私は個人的に寿司が大変好きなのですが、今回は問題を解くのに必死でそれどころではありませんでした……

RCO presents 日本橋ハーフマラソン 予選

今週末の土曜日、オンライン上で我々 RCO プロコン部がプログラミングコンテスト「RCO presents 日本橋ハーフマラソン 予選」を開催します。tomerun さんと uwi さんが作問するほか、コンテストをより楽しくする様々な便利ツールも提供します。上位入賞者は決勝へご招待しますので奮ってご参加ください！

コンテストページ