はむ吉（のんびり）の練習ノート

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

Scala歴0日で競技プログラミングの問題にScalaで解答してみた

プログラミング 競技プログラミング

ふと思い立ち、今日私はプログラミング言語Scalaを使ってAizu Online Judgeおよびyukicoderの問題に解答してみました。Scalaのコードを書くのは初めてでしたが、思っていたよりもすんなりといきました。この記事では、その顛末や、Scalaを使ってみた感想について述べます。

きっかけ

私は、かなり前からyukicoderの問題No.90 品物の並び替え - yukicoderに取り組んでいましたが、なかなかAccepted (AC)を得られずにいました。当初はHaskellやPython 3により解答していたのですが、いくらコードを改良してもTime Limit Exceeded (TLE)を解消できませんでした。そこでこれをC++で書き直してみましたが、今度は原因不明のバグに悩まされ、うまくいきませんでした。そこで、Pythonのように手続き型と関数型のスタイルを併用でき、Pythonよりも実行時間が短くて済む言語を探しました。そんなときに出会ったのがScalaでした。

コーディング環境

当初私は、IntelliJ IDEAにScalaのプラグインを導入し、これを利用してScalaのコーディングをしていました。しかし、標準入力をリダイレクトさせる設定ができず、またいちいちProjectを作成するのが面倒になったため、プラグインlanguage-scalaを導入したテキストエディタAtomを使ってコーディングすることにしました。

コーディングの際に参照したページ

以下で述べる競技プログラミングの答案作成を、主に次のページを適宜参照しながら行いました。思いのほか日本語で書かれた記事・サイトが多かったため、助かりました。

Aizu Online JudgeのIntroduction to Programmingを使った練習

Scalaは初めてである私にとって、いきなり込み入ったコードを書くのは困難に思えました。そこで、まずはAizu Online JudgeのIntroduction to Programming (ITP)に属する問題10000-10005にScalaで解答しました。なお、ITPを用いた練習は以前Haskellを学習したときにも使った方法です*1。この練習を通じて標準入出力の処理や基本的な制御構文をある程度習得できたので、本題に進むことにしました。

yukicoder No.90への解答

やや急であるようにも感じましたが、さっそく上記のyukicoder No.90への解答を作成しました。一度非効率的な処理をさせたためTLEが発生しましたが、その部分を書き直したところ念願のACを得ることができました（実際の提出コード）。大部分を手続き型のスタイルで書きましたが、ごく一部で関数型風のスタイルを取り入れました。

Scalaを触って感じた利点

Scalaを使い始めて数時間ほどしか経っていませんが、現時点においてScalaについてよいと思うところを述べておきます。

陽にforループを書いても低速にならない

Pythonの場合には、for文によるループ処理がやや遅いので、適宜内包表記などで置き換える必要がありました。しかしながら、今回の取り組みを通じて感じたのは、Scalaの場合にはforループがさほど遅くならないということでした。Pythonコードをforループによる低速化を恐れてこねくり回すことがある私にとって、これは重要でした。

Javaの標準ライブラリを利用できる

ScalaはJavaプラットフォーム上で動作する言語であり、ScalaコードではScalaの標準ライブラリだけではなくJavaのそれも利用できます。Java標準ライブラリにはBigIntegerなどの競技プログラミングで使えそうなクラスが含まれていることを踏まえると、これは長所であるといえます。上記の取り組みで提出したコードにも、主に標準入力の処理にJavaの標準ライブラリを使用しています。

リストから順列・組み合わせを容易に作成できる

Pythonではitertools.permutationsやitertools.combinationsでリストから順列・組み合わせを作成できますが、Scalaでもリストのpermutationsメソッドやcombinationsメソッドを用いることで同様のことができます。競技プログラミングにおいてはこのような操作が必要となることがあるため、これは利点であるといえます。

おわりに

Pythonに親しみ、またHaskellもある程度使っていたためか、競技プログラミングの問題に対してScalaで解答するのは、予想していたよりも容易でした。ただ、今日の取り組みだけでは決してScalaの機能を活かしきれていないと思われます。Scalaに対応しているオンラインジャッジやプログラミングコンテストのサイトは限られているようですが、今後問題を解く際にはScalaの利用も検討したいと考えています。

*1:以前の記事でも述べたかもしれませんが、実はこれが競技プログラミングを始めたきっかけでした。