REQLY開発ブログ

プロの料理レシピ専門検索エンジンREQLY(レクリー)の開発ブログです。

codeFlyer本選参加記

こんにちは。エンジニアのm2kuです。今回は6/30(土)に行われたbitFlyerさん主催の競技プログラミングコンテスト「codeFlyer」の参加記です。ありがたいことに今回初めてオンサイトのコンテストに参加させて頂き、そして清々しく惨敗させて頂きました。

bitflyer.com


競技プログラミングとは?

競技プログラミングとは、「〇〇を実現するコードを書いてください」という課題がいくつか与えられ、時間内にプログラムを組んで提出し、その正確さや提出の速さを競うものです。与えられる課題は、ただ単純な実装を行うだけでは実行制限時間を超過するようになっていることも多く、その課題に適したアルゴリズムやデータ構造を上手く用いてコードを高速化する必要があります。実装を工夫して計算量を落とせた時に感じる、パズルが解けた時のような気持ち良さが魅力となっています。


いざ六本木

決戦の地は六本木にある東京ミッドタウンタワーでした。 f:id:reqly-tokyo:20180701012514j:plain

お洒落の最先端を行く東京ミッドタウンにおいて、我々100人のオタクたちが缶詰でプログラミングバトルに興じていることを、どこのマダムが想像しうるのだろうか...


会場で受付を済ませるとbitFlyerさんのロゴの入ったTシャツを頂きました。 f:id:reqly-tokyo:20180701012548j:plain おそらく会場までの交通費がTシャツの形で現物支給されるのでしょう。私は関東圏内からの参戦だったのでSサイズを1枚頂きました。中には遠方から新幹線でいらっしゃった方もいたようです。


コンテスト

本選は計3時間。のたうち回った3時間を時系列でお話ししましょう。

まず圧倒されたのが、開始10秒としないうちに響き渡る100デシベル近いタイピング音。こいつらいつ問題読んだんだよ。心を整えるため、Google Play Musicを立ち上げ平井堅を再生するところから私の戦いは始まります。

頑張ってA問題をこなし、次のB問題。ここから数学的な工夫が要求されてきそうです。問題文を5分ほど睨みましたが、クエリを独立に処理して単純に実装すると計算量がO(NQ)になってしまい、2秒の実行制限時間を超過してしまいます。一旦保留にします。

vs C問題

C問題構文解析のような問題です。個人的に競技プログラミングの問題としては初めての分野ですが、コーディング面接では何度か直面してきました。心をくくり、この問題と向き合うことにします。

とりあえず計算時間は無視して、正しい値を返すようなプログラムを考えてみることにします。30分ほど紙と向き合ってうんうん唸り続け、この問題はまずは次のようなサブ問題に分割できそうだと気づきます。

f:id:reqly-tokyo:20180701012846j:plain

入力文字列を上のように「括弧の対応が取れている文字列」(以下Good-String)に分割するのはスタックを使えばできそうです。あとはそれぞれのGood-Stringを独立に受け取って、それが合計何種類のGood-Stringを部分文字列として持つのかを計算する次のような関数を定義すれば良さそうです。

f:id:reqly-tokyo:20180701022513j:plain

これは再帰を使ってどんどんサブGood-Stringに分割して行くことで、なんとか計算できそうです。

上のアイディアに基づき、Pythonで実装を行い、提出。残念TLEです!(実行制限時間を超過すること)。この時点で開始からおよそ90分が経過。トイレへと向かい、怒りを放尿します。

ただ、上の提出でTLEにならなかったサンプルケースは全てAC(Accepted)でプログラムの動作としては信頼しても良さそうです。そこでC++でプログラムを書き換えることで高速化を図ることにしました。

(ここでそもそもの計算量を疑えなかったのは大きな反省点です。冷静に考えれば、上のサブGood-Stringへの分割は毎回文字列長スキャンするうえ、再帰の深さは最悪の場合文字列長の1/2になるのでO(N2)であり、C++にしても意味の無い書き換えであることに気付けたはずです。)

30分かけてC++に書き直し提出。当然TLEです!雲行きが怪しくなってきました。プレイリストをサザンオールスターズに変更し巻き返しを計ります。

vs B問題

Cは諦め、先ほど保留したB問題に戻ってきました。どうにかしてクエリ間で共通する処理をくくり出したいです。またしても10分ほど図を書きながら唸っていると、以下のような図が出来上がってきます。これは累積和か...?

f:id:reqly-tokyo:20180701012953j:plain

上の図で線として表現されている部分の累積和をO(N)で最初に計算しておくと、その引き算で基準点の左側の人々のコストが求まることに気付きます(図の丸で囲った部分)。累積和の関数cumは、最初に全てのXiについて値を求めておいて、cum(C)を求める時はCから最も近いXiのcum(Xi)に適宜必要な分だけ足し算すれば求まりそうです。最も近いXiは二分探索で求めることができるので、それぞれのクエリはO(logN)となり、無事に制限時間をクリアできそうです。

ここから頑張ってC++で実装を開始しますが、ギリギリタイムアップ。悔しい試合となりました。


懇親会

オタクプログラミングバトルも終わり、お洒落な六本木の街に平穏が戻ってきました。 f:id:reqly-tokyo:20180701013421j:plain


おわりに

B, C共に知っている人には典型問題だったようで、経験不足を痛感しました。しっかり復習し今回で自分のものとしたいです。結果自体は残念でしたが、久々に頭を長時間フル回転させる楽しい経験になりました。bitFlyerさん及びにAtcoderさんに改めてお礼申し上げます。