Scala競技プログラミング（入出力、型、参考URL）

（変更履歴）
2017/2/2：yu_ishikawaさん、表の整形どうもありがとうございました！
および、f補完子の小数書式を訂正しました。

---

大上段なタイトルですが、paizaやCodeIQターゲットなので競技というほどでもありませんが……。

# 標準入出力
ロジックは別として結構面倒なのが標準入出力周りではないでしょうか。。

## 入力
paizaでよくある入力のパターンとして、以下の形式がある。
１．一行目は設定
２．二行目以降に実データ

たとえば、以下のような入力が与えられる。

```bash
5 3
123 456 789
111 222 333
1 2 3
63 72 81
100 200 300
```

1行目の二つの数字は、それぞれ実データのレコード件数、および1レコード内のフィールド数となる。二行目以降に実データ（上記の例では5行3列のデータ）が与えられる。

### 一行ずつ読み込む - io.StdIn.readLine
動きがわかりやすいのが利点です。

```scala
object Main extends App {
  import scala.io.StdIn.readLine
  
  val Array(rows, cols) = readLine split " " map(_.toInt)
  val xss = for(i<- (1 to rows)) yield readLine split " " map(_.toInt) toList
  println(xss.mkString(" "))

// 結果
// List(123, 456, 789) List(111, 222, 333) List(1, 2, 3) List(63, 72, 81) List(100, 200, 300)
}
```

### Scannerを使う - java.util.Scanner(System.in)
おそらくこれが最も使い勝手が良いです。

```scala
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val rows, cols = sc.nextInt
  val xss = List.fill(rows, cols)(sc.nextInt)
  println(xss)

// 結果
// List(List(123, 456, 789), List(111, 222, 333), List(1, 2, 3), List(63, 72, 81), List(100, 200, 300))
}
```

### 複数行読み込む - io.Source.stdin.getLines
Paizaでは使える場面が思いつかないが、他では使えるのではないでしょうか。
#### 入力が続く限り読み込むケース

```scala
object Main extends App {
  val xss = for(l <- scala.io.Source.stdin.getLines) yield (l split " " map(_.toInt) toList)
  println(xss.mkString(" "))

// 結果
// List(5, 3) List(123, 456, 789) List(111, 222, 333) List(1, 2, 3) List(63, 72, 81) List(100, 200, 300)
}
```

#### 特定の数値を受け取るまで読み込むケース
たとえば、-1が与えられるまで読み込む場合。

```bash
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
-1
```

for式とifガードをつかって"-1"という文字列が来るまでyieldすれば良いです。

```scala
object Main extends App {
  val xss = for (l <- scala.io.Source.stdin.getLines; if l != "-1") yield (l split " " map(_.toInt) toList)
  println(xss.mkString(" "))
// 結果
// List(1, 2, 3) List(1, 2, 3) List(1, 2, 3) List(1, 2, 3) List(1, 2, 3)
}
```

### 特定の書式に従って読み取る。
特定の書式（たとえばyyyy/mm/ddなど）に従って入力が与えられるケースです。正規表現とIteratorで乗り切ります。

以下の入力が与えられるとします。

```bash
2017/01/31 10:09:32
```

一例として

```scala
object Main extends App {
  import scala.io.StdIn.readLine
  
  val r = """\d{2,4}""".r
  val dt = r.findAllIn(readLine)
  val yyyy, mm, dd, hour, min, sec = dt.next.toInt
  println(yyyy, mm, dd, hour, min, sec)

// 結果
// (2017, 1, 31, 10, 9, 32)
}
```

### 

### 結論
Paiza、CodeIQでは以下をまずコピペしておくと捗るはずです。

```scala
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  /* Sample Code */
  val rows, cols = sc.nextInt
  val xss = List.fill(rows, cols)(sc.nextInt)
  println(xss)
}
```

#### 参考：
[Scalaで標準入力を受け取る \- Perl日記](http://r9.hateblo.jp/entry/2016/01/05/232036)
[Scalaで競技プログラミング（入出力編） \- Qiita](http://qiita.com/nel215/items/2cc03daaac29b03af176)
[Scalaの標準入力 \- Qiita](http://qiita.com/nesheep5/items/cd2e6113e6aada97112a)
[競技プログラミングにおけるScalaの標準入力を楽にする \- Qiita](http://qiita.com/cohalz/items/a54bfc70e4bbc33440cb)
[【Scala】 正規表現による文字列検索 \- takafumi blog](http://takafumi-s.hatenablog.com/entry/2015/08/19/130513)
[Pythonで競技プログラミングする時に知っておきたいtips\(入出力編\) \- Qiita](http://qiita.com/lethe2211/items/6cbade2bc547649bc040)

## 出力
入力処理に比べてパターンは少ないです。
### 普通のprintln

```scala
println("Hello, World!")
// Hello, World!
println("Hello,\nWorld!")
// Hello,
// World!
```

### s補完子
変数、式を埋め込める。

```scala
val w = "World"
println(s"Hello, ${w}!")
// Hello, World!
println(s"1 + 1 = ${1+1}")
// 1 + 1 = 2
println(s"${for (i<-(1 to 10)) yield i}")
// Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
```

### f補完子
s補完子に書式指定の機能を追加したもの

```scala
val a = 12
val b = "aaa"
println(f"${a}%03d")
// 012
println(f"${a}%04.2f")
// 12.00 (本来は0012.00という動きを期待していたのだが……）
println(f"${b}%10s")
// "       aaa"
```

#### 参考：
[scalaの文字列いろいろありすぎて笑ったけど便利だった \| KentaKomai Blog](http://komaken.me/blog/2014/10/18/scala%E3%81%AE%E6%96%87%E5%AD%97%E5%88%97%E3%81%84%E3%82%8D%E3%81%84%E3%82%8D%E3%81%82%E3%82%8A%E3%81%99%E3%81%8E%E3%81%A6%E7%AC%91%E3%81%A3%E3%81%9F%E3%81%91%E3%81%A9%E4%BE%BF%E5%88%A9%E3%81%A0/)
[printfで文字列の最大文字数を指定する \- 揮発性のメモ](http://d.hatena.ne.jp/iww/20090701/printf)
[フォーマット指定子一覧](http://www.k-cube.co.jp/wakaba/server/format.html)
[fprintf\(\)](http://www.k-cube.co.jp/wakaba/server/func/fprintf.html)

## プリミティブ型
PaizaではIntもしくはLongで十分と思われますが、念のため。

| 型名       | 説明                         | 範囲（数値型の場合）                            | 例                                                       |
|------------|------------------------------|-------------------------------------------------|----------------------------------------------------------|
| Boolean    | 真偽値                       |                                                 | true,false                                               |
| String     | 文字列                       |                                                 | "abcde"                                                  |
| Char       | 2バイトUnicode文字           |                                                 | 'A','あ'                                                 |
| Byte       | 8ビット符号付整数値          | -128～127                                       | （省略）                                                 |
| Short      | 16ビット符号付整数値         | -32768～32767                                   | （省略）                                                 |
| Int        | 32ビット符号付整数値         | -2147483648～2147483647                         | （省略）                                                 |
| Long       | 64ビット符号付整数値         | -9223372036854775808～9223372036854775807       | （省略）                                                 |
| Float      | 32ビット浮動小数点数         | -3.4028235E38～3.4028235E38                     | 0.2f, 1e-2f                                              |
| Double     | 64ビット浮動小数点数         | -1.7976931348623157E308～1.7976931348623157E308 | 0.2, 0.2d, 1e-2, 1e-2d                                   |
| BigInt     | 任意桁数の整数               | 多分ない                                        | BigInt(10), BigInt("123179623176239716237619241")        |
| BigDecimal | 任意桁数の数値（小数点有り） | ある程度整数部が大きいと小数部が丸められる      | BigDecimal(10000.12345), BigDecimal("123719.1823761238") |

ScalaのLong型はc言語で言うところの「long long」型に相当します。

BigIntはこんな風に使います。すんごい大きな数字を扱うのに便利です（遅いけど）。

```scala
scala> val v = BigInt(1234567890)
v: scala.math.BigInt = 1234567890

scala> v + v
res14: scala.math.BigInt = 2469135780

scala> v * v
res15: scala.math.BigInt = 1524157875019052100

scala> v * v * v
res16: scala.math.BigInt = 1881676371789154860897069000

scala> v * v * v * v
res17: scala.math.BigInt = 2323057227982592441500937982514410000

scala> (v * v * v * v).toDouble
res18: Double = 2.3230572279825926E36

scala> val v2 = v * v * v * v
v2: scala.math.BigInt = 2323057227982592441500937982514410000

scala> v2
res19: scala.math.BigInt = 2323057227982592441500937982514410000

scala> val v3 = BigInt(23179871238719823798138927198)
<console>:1: error: integer number too large
       val v3 = BigInt(23179871238719823798138927198)
                       ^

scala> v2 * -1
res20: scala.math.BigInt = -2323057227982592441500937982514410000

scala> v2 * -1 + 10
res21: scala.math.BigInt = -2323057227982592441500937982514409990
```

#### 参考：
[第6章：Scalaのプリミティブ型を語る \- Qiita](http://qiita.com/f81@github/items/c43803f4a8da94615c9c)
[猿でも分かるScala\!：Scalaの型 \- Qiita](http://qiita.com/msano/items/151a6402605df071a7de)

## アスリートの皆様
参考：
[Scalaで競技プログラミングしてみる \- Lizan's note](https://lizan.asia/blog/2012/12/11/scala-competitive/)
[scalaで競技プログラミング \-ABC001\- \- scache's diary](http://scache.hatenablog.jp/entry/2014/09/17/130057)
[競技プログラミングモードのscalaを書いてみたｗ](https://gist.github.com/akihiro4chawon/898160)
[競技プログラミング特有の変な実装テク // ichyo\.jp](http://ichyo.jp/posts/2014-12-15-advent-calender/) → C++だけど有用です
[Scala歴0日で競技プログラミングの問題にScalaで解答してみた \- はむ吉（のんびり）の練習ノート](http://hamukichi.hatenablog.jp/entry/2016/02/18/195019)
[競技プログラミング in Scala \- 純粋関数型雑記帳](http://d.hatena.ne.jp/tanakh/20090908)
[ScalaでCodeforces\#97 Div2参加してみた \- くじらにっき\+\+](http://kujira16.hateblo.jp/entry/20111210/1323534495)
[Pythonで競技プログラミングする時に知っておきたいtips \- Qiita](http://qiita.com/lethe2211/items/b91cc9e2b355ad32f1e6) → Pythonだけど結構Scalaにも応用できます。

# 一般論
## 競技プログラミングへの心構え、解き方
動的計画法、幅優先探索、深さ優先探索などなど。
[競技プログラミング \| ソフトウェア工房](http://koubou.cs.kanagawa-it.ac.jp/procon/)
[競技プログラミング Wiki\*](http://wikiwiki.jp/kyopro/)
[競技プログラミングの問題の解き方、そのマニュアル · うさぎ小屋](https://kimiyuki.net/blog/2016/06/21/how-to-solve-problems-in-competitive-programming/)
[競技プログラミング頻出アルゴリズム攻略](http://www.slideshare.net/MonetoK/ss-56993100)

## 有名競技プログラミングサイト
[yukicoder](https://yukicoder.me/)
[Topcoder \| Deliver Faster through Crowdsourcing](https://www.topcoder.com/)
[AtCoder](https://atcoder.jp/)
[AIZU ONLINE JUDGE: Programming Challenge](http://judge.u-aizu.ac.jp/onlinejudge/)
[Welcome To PKU JudgeOnline](http://poj.org/)

## その他
[Scalaを始めて早5年、今一度冷静にScalaと向き合ってみた \- tehepero note\(・ω<\)](http://blog.stormcat.io/entry/2015/03/11/214212)