Codeforces デビュー
TopCoder 環境構築人間になりつつありますが、本日は Codeforces に触ってみました。 Codeforces デビューと言っても、過去問解いてただけです……早く参戦したい!
Codeforces は標準入出力を使用し、最後にファイルを提出する形式*1ですので、特に環境構築は必要ありません!
Scala デビュー
実は Scala も始めて触りました。Codeforces は Haskell も使えますが、あえて Scala でやってみました。
Scala にした理由は、
といったところです。
Codeforces Round #273 (Div. 2)
A, B, C と解いてみました。Cは正直解けませんでした。降参してググって、回答みて感動しました……そんなの気がつかないよ!!
A. Initial Bet
問題はこんな感じ。正直、英語力がヤバい。辛い。
全員に同じ枚数のコインを与えてゲームを始める。ゲームをするとコインのやりとりが発生する。最終的なコインの状態から、最初に与えられたコインは何枚だったのか求めよ。おかしな状態だったら-1を出力せよ。
超楽勝ですね。全員の枚数を足して、人数で割ってあまりがない場合の商が答えです。 全員0点だった場合も-1にしないといけないそうです。1度提出してから気がつきました。
import java.util.Scanner object R273_InitialBet { def main(args:Array[String]) = { val in = new Scanner(System.in).nextLine().split(" ").map(_.toInt) val sum = in.sum val len = in.length println(sum match { case 0 => -1 case _ if sum % len == 0 => sum / len case _ => -1 }) } }
B. Random Teams
英語力の足りなさを感じる。
n人の参加者をmチームに分ける。各チームは最低1人。同じチームの人は友人になる。友人の組み合わせの最小と最大を求めよ。
どういうときに最小になるのか、どういうときに最大になるのかを考えてみました。
- 最小: 各チームの人数差を高々1にする
- 最大: 可能な限り大人数のチームを作る (1チーム以外はメンバー1人のチームにする)
正直、完全に勘です。実装して提出してから合ってるか考えましょう。
import java.util.Scanner object R273_RandomTeams { def main(args: Array[String]) = { val in = new Scanner(System.in).nextLine().split(" ").map(_.toInt) val (n, m) = (in(0), in(1)) val (p, q) = (n / m, n % m) val min = combination2(p) * (m - q) + combination2(p + 1) * q val max = combination2(n - m + 1) println(min + " " + max) } def combination2(n: Long): Long = { (n * (n - 1)) / 2 } }
なぜか合っていました。
ポイントは組み合わせ (combination) の求め方です。 最初はバカ正直に実装してたんですが、与えられる入力が109と結構大きいため、組み合わせを求める公式通りに計算したら時間オーバーします。
そのため、常に nC2 となることを利用して、式を展開しておきます。あと、Int では なく Long を使い桁あふれを防ぎます。
C. Table Decorations
これは綺麗な解法思いつきませんでした。ググっちゃいました。
赤、緑、青の風船が与えられる。風船3つを使って机をデコレーションせよ。ただし、同じ色の風船のみの机は作ってはならない。最大いくつの机をデコレーションできるか求めよ。
これ、どうやら、
- 一番大きいものが、それ以外の2つの和の2倍以上のとき
- それ以外のとき
の2パターンの場合わけでいけるっぽいです。詳細な説明は割愛しますが、1の場合は一番大きいものから常に2つ取る方法が最大になり、それ以外のときは単に合計を3で割れば良いです。
以下、ヒント
RRRRRRGGGG GGGGGGGBBB BBBBBBBBBB
一番大きいものが、それ以外の2つの和の2倍以上のときって、全ての列にとある色が出現しちゃう状況ってことです。
import java.util.Scanner object R273_TableDecorations { def main(args: Array[String]) = { val in = new Scanner(System.in).nextLine().split(" ").map(_.toLong).sorted println(if ((in(0) + in(1)) * 2 <= in(2)) in.take(2).sum else in.sum / 3) } }
こんなの気がつかないよ……!
まとめ
Codeforces はサイトが割と分かりやすい。使える言語が沢山ある。良い。
Scala も良い。書きやすい。ストレスが結構少ない。
とりあえず、TopCoder と Codefores の Div2 あたりを沢山解いていこうと思います。 とにかくいろんなことに慣れていきます……そして蟻本も……!!
使う言語に関しては、
- TopCoder: Python
- Codeforces: Scala
- お楽しみ: Haskell
ってなりそうな予感!ちなみに仕事では Ruby を使ってます。 見事にバラバラ。楽しい言語ばっかりでとても素晴らしい。