1Scalaによる競技プログラミングのすすめScala競技プログラミング今日からアドベントカレンダーが始まります。プログラミング言語を学習した次にやることの1つとして、競技プログラミングがおすすめです。今回は、業務で使っているScalaで競技プログラミングに取り組む話をします。競技プログラミングとは?パズルやクイズなどの問題を、プログラムを用いて解く速さを競います。実行時間や使用メモリ数などに制限があり、それを守りつつ正解となるコードを作る必要があります。オンラインのコンテストもあり、インターネット環境があれば自宅でも外出先でも参加することができます。競技プログラミングがいい?プログラミング言語の習得時に、基本的な文法を学んだ後に何をするかで悩むことがあるのではないでしょうか。自分が作りたいシステムやサービスを作ろう、とよく言われますが、私は何を作れば良いのかなかなか思い浮かびませんでした。競技プログラミングでは問題が与えられるため、何を作るかのアイデアがなくても気軽に取り組むことができます。競技という特性上、前回の自分や他の人を意識することで、モチベーションを保ちやすいです。文法を学習した直後であれば特に、文法を使いこなす経験が積めるのでおすすめです。教科書の練習問題は解けるけど実際に使いこなすのが難しい、という状態から、頭で思い浮かぶ操作をソースコード上で実現できるようになります。実際に解いてみよう簡単な問題に関しては、言語での文法を使いこなせれば十分解くことができます。過去のコンテスト問題を解いてみましょう。AtCoderのオンラインコンテストの過去問を解きます。自分で手を動かす場合はAtCoderのアカウントを作るのがおすすめです。問題に取り掛かる前の準備(入出力)問題に取り組む前に、入出力の仕方を確認しましょう。contestにいくつかの言語で解答例があるので、まずはそこから入出力の仕方を知るのが良いでしょう。私はScala標準の入力ではなくJavaのScannerを用いていますが、この方法でやらなければならない、というものはないです。値を入力・出力できるようになれば問題ないです。高橋くんは、自動販売機でジュースを買ったときの音が好きです。円で聞くことができます。回まで聞けるだけ聞きます。高橋くんはお気に入りの音を何回聞くことになるでしょうか。入力は全て整数である。≤100競技プログラミングには問題と制約があります。問題に対する答えを求めるプログラムを作ることが目標です。指定されたフォーマットの入力値が与えられるので、それらを受け取ってプログラムを実行し、指定されたフォーマットで答えを出力します。制約は、フォーマットの入力値として考えられる値の条件です。制約によって、解き方が大きく変わる場合があるので注意が必要です。プログラムが正しいかどうかは、いくつかの決められた入力値(テストケース)で実行して正しい答えが求まるかどうかで判定します。整数型(Int)として扱っていいことがわかります。うち、小さくない方であることがわかります。プログラムはこんな感じです。結果を出力する}公式ページの下部にいくつかの入出力例があるので、試してみましょう。横着してコードを書いてすぐに提出して間違えると、ペナルティとして提出時間が+5分されてしまいます。入出力例の確認に5分かかることはないので、やって損は無いです。いくつかコメントです。ScalaプログラムはMain.scalaというファイル名でコンパイルされるため、object名はMainにしています$^{(※1)}$。・問題文中では入力値の変数はA,B,Cと大文字を使っているのにプログラム中では小文字を使っているのは、Scalaプログラムでは先頭が大文字の変数は定数とする規約があるためです。パターンマッチを用いる際にハマったことがあり、以来小文字を使っています。意味がわかる変数名につけなおす考えがありますが、ある程度理解できる範囲なので変数名を考えることに時間を使うよりも提出を優先させています。AもBも割り切る正整数のうち、K番目に大きいものを求めてください。K番目に大きいものが存在することが保証されます。入力は全て整数である。AもBも割り切る正整数のうち、K番目に大きいものが存在する。今回も、A,Bは整数値(Int)で良いですね。AとBの公約数はAとBの最大公約数の約数であることが、整数に関する有名事実として知られています。K番目に大きいDの約数を求めるということになります。競技プログラミングではちょっとした数学の知識があると有利な場合があります。AとBの最大公約数Dを求めるユークリッドの互除法を用います。大きい数を小さい数で割って余りを求めて、小さい数をその余りで割って・・・というのを繰り返す話です。Javaでこのような繰り返しを行う場合はwhile文を用いますが、Scalaでは専ら再帰関数を用います。最大公約数を求める処理は競技プログラミングを行う際には時々使うので、Myライブラリとして保管しておくといいかもしれません。}Step2:Dの約数を全て求める値が大きくないので、素直に1から順に割り切るかを調べて問題ありません。Step3で、大きい方からK番目であるものを求めるため、reverseをします。0).reverseStep3:K番目に大きいDの約数を求めるRangeのapplyメソッドから取得することができます。1)合わせたコードがこちら。}}提出する前に、入出力例の確認をお忘れなく。Unification一筋縄ではいかない例を紹介します。説明はざっくりなので、気になった人は調べてみてください。個のキューブが縦に積まれています。