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
これは、二次元平面上に相異なる点が存在するときに、条件(ただしは互いに異なる)を満たす3つ組の数を求めるという問題でした。私には効率のよい方法が思い浮かばず、全部で個存在する3つ組のそれぞれに対して、それが条件を満たすかを確認するという方法をとりました。その結果として、自分で適当に作成したテストケースに対する処理が数秒では終わらなかったため、提出を諦めました。
High Security
この問題では、各マスが"."(何もない)あるいは"X"(建物がある)であるようなグリッドとして地図が与えられました。求めるべきものは、"."マスに警備員を配置できるときに、すべての"."マスが少なくとも一人の警備員により監視されるために必要な警備員の数の最小値でした。私は行数が2であるという制約条件を読み落とし、早々にあきらめてしまいました。グリッドを解析する問題を苦手としていることも一因でした。
The Price is Correct
この問題で求めるべきものは、正の整数からなる数列について、を満たす2つ組の数でした。使用すべき技法として累積和と尺取り法が思い浮かびましたが、私は前者を用いた解答を作成しました。自分で適当に作成したテストケースに対しては処理が1分ほどで終わったため、本番の入力ファイルをダウンロードしました。しかしながら、これに対しては処理が進まず、Case #1の結果すら出力されないうちに制限時間を超えてしまいました。
Text Editor
この問題では、1文字の追加、1文字の削除および現在の文書の印字という3つの操作だけが行える仮想のテキストエディタが登場しました。求めるべきものは、文書が空の状態から、個の文字列のうち個を選んで印字し、再び文章を空にする際に必要な操作回数の最小値でした。この問題については解法を考え出すことができませんでした。