Scalaによる競技プログラミングのすすめ

今日からアドベントカレンダーが始まります。
どうぞ宜しくお願いします。

プログラミング言語を学習した次にやることの１つとして、競技プログラミングがおすすめです。
今回は、業務で使っているScalaで競技プログラミングに取り組む話をします。

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

パズルやクイズなどの問題を、プログラムを用いて解く速さを競います。実行時間や使用メモリ数などに制限があり、それを守りつつ正解となるコードを作る必要があります。オンラインのコンテストもあり、インターネット環境があれば自宅でも外出先でも参加することができます。

なぜ競技プログラミングがいい？

プログラミング言語の習得時に、基本的な文法を学んだ後に何をするかで悩むことがあるのではないでしょうか。自分が作りたいシステムやサービスを作ろう、とよく言われますが、私は何を作れば良いのかなかなか思い浮かびませんでした。

競技プログラミングでは問題が与えられるため、何を作るかのアイデアがなくても気軽に取り組むことができます。競技という特性上、前回の自分や他の人を意識することで、モチベーションを保ちやすいです。
文法を学習した直後であれば特に、文法を使いこなす経験が積めるのでおすすめです。教科書の練習問題は解けるけど実際に使いこなすのが難しい、という状態から、頭で思い浮かぶ操作をソースコード上で実現できるようになります。

実際に解いてみよう

簡単な問題に関しては、言語での文法を使いこなせれば十分解くことができます。
過去のコンテスト問題を解いてみましょう。
AtCoderのオンラインコンテストの過去問を解きます。自分で手を動かす場合はAtCoderのアカウントを作るのがおすすめです。

問題に取り掛かる前の準備(入出力)

問題に取り組む前に、入出力の仕方を確認しましょう。
practice contestにいくつかの言語で解答例があるので、まずはそこから入出力の仕方を知るのが良いでしょう。私はScala標準の入力ではなくJavaのScannerを用いていますが、この方法
でやらなければならない、というものはないです。とりあえずは値を入力・出力できるようになれば問題ないです。

Main.scala

import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  
  val inputInt    = sc.nextInt       // 数値(Int値)を受け取る
  val inputString = sc.next          // 文字列を受け取る

  val res = inputInt + inputString
  println(res)                       // 結果を出力する
}

その１ AtCoder Beginner Contest 120 A Favorite Sound

問題文
高橋くんは、自動販売機でジュースを買ったときの音が好きです。
その音は 1 回 A 円で聞くことができます。
高橋くんは B 円持っていますが、お気に入りの音を C 回聞くと満足するため、B 円で最大 C 回まで聞けるだけ聞きます。
高橋くんはお気に入りの音を何回聞くことになるでしょうか。

制約
・ 入力は全て整数である。
・ 1 ≤ A,B,C ≤100

競技プログラミングには問題と制約があります。問題に対する答えを求めるプログラムを作ることが目標です。指定されたフォーマットの入力値が与えられるので、それらを受け取ってプログラムを実行し、指定されたフォーマットで答えを出力します。制約は、フォーマットの入力値として考えられる値の条件です。制約によって、解き方が大きく変わる場合があるので注意が必要です。プログラムが正しいかどうかは、いくつかの決められた入力値(テストケース)で実行して正しい答えが求まるかどうかで判定します。

###考察
制約をみると、特にA,B,C は整数型(Int)として扱っていいことがわかります。

・音を聞くことができる回数は、最大でもB/A回である
・C回音を聞くとそれ以上は聞かない

ことから、答えは B/A と C のうち、小さい方であることがわかります。

プログラムはこんな感じです。

Main.scala

import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  
  val a = sc.nextInt                 // 入力Aを受け付けて、aに格納する
  val b = sc.nextInt                 // 入力Bを受け付けて、bに格納する
  val c = sc.nextInt                 // 入力Cを受け付けて、cに格納する

  val res = Math.min(b/a, c)         // B/A と C のうち、小さい方 を計算する
  
  println(res)                       // 結果を出力する
}

公式ページの下部にいくつかの入出力例があるので、試してみましょう。横着してコードを書いてすぐに提出して間違えると、ペナルティとして提出時間が+5分されてしまいます。入出力例の確認に5分かかることはないので、やって損は無いです。

いくつかコメントです。

・atCoder ではScalaプログラムはMain.scalaというファイル名でコンパイルされるため、object名はMainにしています$^{(※1)}$。

・問題文中では入力値の変数はA,B,Cと大文字を使っているのにプログラム中では小文字を使っているのは、Scalaプログラムでは先頭が大文字の変数は定数とする規約があるためです。パターンマッチを用いる際にハマったことがあり、以来小文字を使っています。意味がわかる変数名につけなおす考えがありますが、ある程度理解できる範囲なので変数名を考えることに時間を使うよりも提出を優先させています。

##その2 AtCoder Beginner Contest 120 B K-th Common Divisor

問題文
正整数 A,B が与えられます。
AもBも割り切る正整数のうち、K番目に大きいものを求めてください。
なお、与えられる入力では、Aも Bも割り切る正整数のうち K番目に大きいものが存在することが保証されます。

制約
・ 入力は全て整数である。
・ 1 ≤ A,B ≤100
・ AもBも割り切る正整数のうち、K番目に大きいものが存在する。
・ K ≧ 1

考察

今回も、A,Bは整数値(Int)で良いですね。
AとBの公約数はAとBの最大公約数の約数であることが、整数に関する有名事実として知られています。

やることは、
step1 AとBの最大公約数Dを求める
step2 Dの約数を全て求める
step3 K番目に大きいDの約数を求める
ということになります。

競技プログラミングではちょっとした数学の知識があると有利な場合があります。

Step1: AとBの最大公約数Dを求める

ユークリッドの互除法を用います。
大きい数を小さい数で割って余りを求めて、小さい数をその余りで割って・・・というのを繰り返す話です。
Javaでこのような繰り返しを行う場合はwhile文を用いますが、Scalaでは専ら再帰関数を用います。
最大公約数を求める処理は競技プログラミングを行う際には時々使うので、Myライブラリとして保管しておくといいかもしれません。

  def gcd(a: Int , b: Int): Int ={
    //基本的にaがb以上の場合で考える
    if(b == 0) a
    else {
      if(a < b) gcd(b,a)  //aがbよりも小さい場合はひっくり返す
      else gcd(b, a % b)  //余りを求めて、小さい数をその余りで割って・・・
    }
  }

Step2:Dの約数を全て求める

値が大きくないので、素直に1から順に割り切るかを調べて問題ありません。
Step3で、大きい方からK番目であるものを求めるため、reverseをします。

    val res = (1 to d).filter(d % _ == 0).reverse

Step3:K番目に大きいDの約数を求める

Rangeのapplyメソッドから取得することができます。

    val res = (1 to d).filter(d % _ == 0).reverse(k - 1)

合わせたコードがこちら。

Main.scala

import java.util.Scanner
 
object Main {
  val sc = new Scanner(System.in)
  def main(args: Array[String]): Unit = {
    val a = sc.nextInt
    val b = sc.nextInt
    val k = sc.nextInt
 
    val d = gcd(a,b)
    val res = (1 to d).filter(d % _ == 0).reverse(k - 1)
 
    println(res)
  }
 
  def gcd(a: Int , b: Int): Int ={
    if(b == 0) a
    else {
      if(a < b) gcd(b,a)
      else gcd(b, a % b)
    }
  }
}

提出する前に、入出力例の確認をお忘れなく。

その3 AtCoder Beginner Contest 120 C Unification

一筋縄ではいかない例を紹介します。説明はざっくりなので、気になった人は調べてみてください。

(追記！)
12月4日: コードが間違っている部分があったので修正しました！
(追記その２！！)
12月23日: 解説が間違っている部分があったので修正しました！

問題文
机の上に N 個のキューブが縦に積まれています。長さ N の文字列 S が与えられます。
下から $i$ 番目のキューブの色は、S の $i$ 文字目が 0 のとき赤色、1 のとき青色です。
あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら 2 個のキューブを取り除く操作を何度でも行えます。
このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。
最大で何個のキューブを取り除けるでしょうか。
制約
・ 入力は全て整数である。
・ 1 ≤ N ≤ $10^5$
・ |S|=N
・ S の各文字は '0' または '1' である。

考察

文字列Sに対して"01"もしくは"10"があったら取り除く、という操作を取り除く文字列がなくなるまでやる、という処理を忠実に行おうとすると、次の様になります。

Main.scala(一部)

  val s = sc.next

  def loop(str: String): String = {
    val eliminated =
      str.replace("01","") // 赤青のキューブの隣接を消す
         .replace("10","") // 逆の並びもあり得る

    if(str == eliminated) str // 変化がなかったら終了
    else loop(eliminated)     // 変化があったらもう一度
  }

  val res = loop(s)
  println(res)

これで入出力例の確認も正しくできたので、満を持して提出すると、TLE(Time Limit Exceeded: 実行時間over)となります。制約をみると、今回は$10^5$と先ほどまでの範囲よりもだいぶ大きくなります。用意された入出力例は文字数が少なく、単純なデータだったため時間内に実行できましたが、他のケースで時間がかかりすぎています。今回のコードでは、"111...1100...000"('1'が5,000個、'0'が5,000個)のケースで一番時間がかかります。入力値を用意できればコードテストで確かめることができます。
テストコードを得るためにコードが必要になる分量です。

BuildInput.scala

object Main extends App{
  val res = Seq.fill(5000)(1).mkString + Seq.fill(5000)(0).mkString
  println(res)
}

ここで、競技プログラミングでよくある工夫が必要になります。スタックというデータ構造を使います。ScalaではListが対応します$^{(※2)}$。

Main.scala

 val s = sc.next
 
 val stack =
   s.foldLeft( Seq.empty[Char] ){(stack, ch) =>
     ch match{
       case '0' if stack.headOption.contains('1') => stack.tail
       case '0'                                   => ch +: stack
       case '1' if stack.headOption.contains('0') => stack.tail
       case '1'                                   => ch +: stack
     }
   }

 val res = s.length - stack.length
 println(res)

##Scalaで参加する際の注意
競技プログラミングはScalaの他にも様々な言語で参加することができますが、特にScalaで参加する際に気づいたことをいくつかコメントします。

・Scalaは実行時間が遅い
主に競技プログラミングで使われている言語はC++ やC# などの実行速度が早い言語です。
C++ で書くと1ms の処理が Java だと100ms, Scala だと300ms 程度になります。
特に、実行速度が早い言語を用いた場合の想定解をそのままScalaで適用しても、TLEとなることが稀にあります。想定解を見直し、無駄な処理や工夫できる点を探してより良い解法を考える、という姿勢が大事になります。私の観測範囲では、まだどうしても間に合わないという問題にはあたっていないです。

・Scalaでの参加者が少ない
上の理由からもわかる通り、競技プログラミングで良い成績を納めるためにScalaで参加することは滅多にないです。実際にScalaでの参加者も少ないです。そのため、Scalaでの参加者の中で一番早く解いた人になりやすいです。
一方、どうしても解けない時に正解者の人のコードを参考にしようとしたら、まだScalaでの正解者がいなかった。。。ということも結構起こります。

##まとめ
競技プログラミングの問題をみてきました。
これなら自分もできそうだな、楽しそうだな、などと思っていただければ幸いです。

明日は@tsaitou1さんです。よろしくお願いします。

##脚注
(※1) ルール中の言語/Scala を参照

(※2) 具象不変コレクションクラス 中の"不変スタック" を参照