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

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

Lambda Calculi - March 2016に参加した:関数型言語だけでの競技プログラミング

3月25日14時30分(日本時間)から丸3日間にわたり、HackerRankにてLambda Calculi - March 2016という関数型言語縛りのプログラミングコンテストが開催され、私はそれに参加しました。Lambda Calculiを冠するコンテストは以前にも何度か開かれていたようですが、私にとってはこれが初めての参加でした。

コンテストの概要

今回のLambda Calculiでは、3日間という制限時間の中で、基本的なものからやや高度なものまで7問の問題を解くことが求められました。上位10名には賞品としてHackerRankのTシャツが出ました。このコンテストで使用が認められた言語は、以下の通りです。

私の結果および取り組み

私の順位は77位でした(登録者数283)。4問に完答し、1問で部分点を得ました。以下には、各問題についての取り組みについて簡単に書いておきます*1。なお、私は第1問~第4問に対しHaskell*2で解答を作成しましたが、第6問ではScalaを使用しました。

第1問:Functions or Not?

いくつかの非負整数の二つ組(x_i, y_i)について、いずれのiに対してもx_iy_iに移すような関数f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0}が存在するかを答えさせる問題でした。少々面食らいましたが、正答できました。

第2問:Compute the Perimeter of a Polygon

題名の通り、自己交差のない多角形の各頂点の座標を使い、その多角形の周長を求めるという問題でした。注意深く実装し、解けました。問題文には点が時計回りに与えられるとは明記されていませんでしたが、時計回りを前提としても正答となりました。

第3問:Compute the Area of a Polygon

幾何の問題が続きました。この問題は、自己交差のない多角形の各頂点の座標からその多角形の面積を求めよというものでした。どうやって求めればよいのか自分ではわからなかったので公式を調べましたが、その後はすんなりと解答できました。この問題でも、点が時計回りに与えられるという問題文には見当たらない仮定を置きましたが、それでもAcceptedとなりました。

第4問:Concave Polygon

またもや幾何の問題でした。これは自己交差のない多角形の各頂点の座標に基づき、その多角形が凹多角形であるかを判定するという問題でした。今度は点の与えられる順番が時計回りとは限らないことが問題文から示唆されていたので、与えられた点を反時計回りに並べ替える処理を加えました。凹凸の判定にやや手間取りましたが、なんとかAcceptedを得ました。

第5問:Tree manager

根付き木に対して指示された操作を行い、結果を報告するという問題でした。どう実装すればよいのかわからず、結局何も書けませんでした。

第6問:Fighting Armies

いくつかの軍隊について兵士の加入・離脱および軍隊の合併に関する情報が与えられ、それらの処理が求められるという問題でした。入出力の高速化を図ったうえで愚直に実装しましたが、大きなテストケースに対するTimeoutを解消できませんでした。

第7問:Simplify the Algebraic Expressions

与えられた数式を簡単な多項式に直すという問題でした。いろいろと考えてはみたものの、結局何も書けずに終わりました。

感想

私の関数型言語(主にHaskell)歴は1年に満たないので、歯が立たないかもしれないと思っていましたが、とりあえず無残な結果にはならずほっとしました。問題文は英語で書かれていましたが、難解な表現はなかったので、理解に支障をきたすことはあまりありませんでした。ただ気になったのは、上で述べたように、制約条件に関する記述に不足が見られたという点です。もしかしたら、私が読み落としただけなのかもしれませんが。また、幾何の問題が全体の半数程度を占めており、出題分野が偏っているような気がしました。

また、このようなコンテストをもっと盛んに開催してほしいとも感じました。実験的コンテストという位置づけで、AtCoderなどでこういった一風変わったコンテストを開いてほしいものです(出過ぎたことかもしれませんが)。

おわりに

今回のコンテストを通じて、競技プログラミングにおいては、手続き型だけではなく関数型プログラミングも十分利用できるということを改めて実感しました*3。問題に応じて、両者を適宜使い分けたいところです。

*1:解けた問題の具体的な解き方や解答例については、頭の整理を兼ねて別の記事としてまとめる予定です。

*2:ブログやTwitterで繰り返し述べてきたように、私が競技プログラミングを始めた当初の目的は、Haskellの学習でした。今では手段の自己目的化が起こりつつあります。

*3:この点については、別の記事で述べるかもしれません。