はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

Facebook Hacker Cup 2016 Qualification Roundに参加してはみたものの歯が立たなかった

Facebook Hacker Cupは、年に一回開かれるプログラミングの競技会です。今年は、その最初のラウンドであるQualification Roundが、1月9日9時から12日9時(日本時間)にわたりオンラインで実施されました。私はこれに参加しましたが、1問も解答できないという結果に終わりました。

参加に至るまで

私にとって、Facebook Hacker Cupへの参加は今回が初めてでした。Qualification Roundの実施を知ったのは1月10日のことであり、すでに開催期間中でした。そのため、過去に出題された問題を確認することはほとんどできませんでした。また、以前の記事でも述べたように、私はアルゴリズムに習熟しているとは決していえません。準備が不足していることは明らかでした。しかしながら、1問でも解答できればよいという気持ちで、とりあえず参加してみることにしました。

各設問に対する取り組み

Qualification Roundでは4つの問題が出されました(実際の問題)。私は以下のように取り組みましたが、いずれについても解答を提出できませんでした。

Boomerang Constellations

これは、二次元平面上に相異なる点\mathrm{S}_i(X_i,\,Y_i)\:(i=1,2,\cdots ,N)が存在するときに、条件\mathrm{S}_i\mathrm{S}_j=\mathrm{S}_j\mathrm{S}_k(ただしi,\,j,\,kは互いに異なる)を満たす3つ組(i,\,j,\,k)の数を求めるという問題でした。私には効率のよい方法が思い浮かばず、全部で_NC_3個存在する3つ組のそれぞれに対して、それが条件を満たすかを確認するという方法をとりました。その結果として、自分で適当に作成したテストケースに対する処理が数秒では終わらなかったため、提出を諦めました。

High Security

この問題では、各マスG_{i,j}\:(i=1,2;\,j=1,2,\cdots ,N)が"."(何もない)あるいは"X"(建物がある)であるようなグリッドとして地図Gが与えられました。求めるべきものは、"."マスに警備員を配置できるときに、すべての"."マスが少なくとも一人の警備員により監視されるために必要な警備員の数の最小値でした。私は行数が2であるという制約条件を読み落とし、早々にあきらめてしまいました。グリッドを解析する問題を苦手としていることも一因でした。

The Price is Correct

この問題で求めるべきものは、正の整数からなる数列\{B_i\}_{i=1,2,\cdots ,N}について、\sum_{i=a}^{i=b}B_i\le P\:(1\le a\le b\le N)を満たす2つ組(a,\,b)の数でした。使用すべき技法として累積和と尺取り法が思い浮かびましたが、私は前者を用いた解答を作成しました。自分で適当に作成したテストケースに対しては処理が1分ほどで終わったため、本番の入力ファイルをダウンロードしました。しかしながら、これに対しては処理が進まず、Case #1の結果すら出力されないうちに制限時間を超えてしまいました。

Text Editor

この問題では、1文字の追加、1文字の削除および現在の文書の印字という3つの操作だけが行える仮想のテキストエディタが登場しました。求めるべきものは、文書が空の状態から、N個の文字列のうちK個を選んで印字し、再び文章を空にする際に必要な操作回数の最小値でした。この問題については解法を考え出すことができませんでした。

解答の作成に使用した言語

当初、私は処理速度を重視して、C++でコードを書いていました。しかし、C++の経験に乏しいせいか、同じプログラムを実行するたびに結果が異なるという珍妙な事態に陥り、これを解決できなかったため、慣れ親しんでいるPythonに切り替えました。

課題

まずは、よく用いられるアルゴリズムを自分で使えるように訓練する必要があると感じています。また、Pythonだけではなく、(C++のように)より高速で、競技プログラミングでよく用いられる言語にもう少し慣れる必要がありそうです。