id:asi1024によるJOI予選予想問題
みんな大好きScalaですが、使うことのできるプログラミングコンテストが Google Code Jam と JOI くらいしかありません。
というわけでScalaで書いてみたのですが、なかなか楽しいです。
- 1. 特製カレーライス
ベータ版のタイトルは「おいしいハンバーガー」でした。(問題の内容は同じ)
"キログラム"を読み逃すという小学生並みのことをやらかす。
- 2. 雑誌の統計
mutable なクラスを使いました。
関数型勉強中の身なので immutable なクラスを使ったほうが勉強にはなりそうですが。。。
- 3. タイル
リスト操作と親和性のある言語(≒関数型)にとってはお手の物でしょう。
RUPC2011
PCK最予選に参加するよりも遥かに有意義だったw
(PCKは相方の都合が合わず辞退)
A > C > D の順に解きました。
- A. Swap Cipher
"aiとbiの差分"を"文字列のai番目とbi番目の差分"と勘違いする。(意味不明)
- B. Problem B
自分の日本語力が足りない!諦めた。
- C. Seishun 18 Kippu
どうせならと一緒に行こうと考えたsirokurostoneは途中の駅で2D好きな彼を拾って向かおうと考えた。
どこで彼を拾うんだろう。。。(2D好きな彼のいる駅まで、迎えに行くということらしい)
最大ケース投げられたらWarshall-Floydじゃ間に合わないなー、ということでDijkstra2回で解きましたが、Warshall-Floydで通るらしいです。反省。
- D. The Legendary Sword
「あっ、去年のJOIでやった問題だ!」(←まちがい)
BFSした後でなぜかDijkstra。
普通にDPしろよ。
そのせいで1時間強をデバッグに費やす。
vectorの使い方をよく分かっていない、ということがよく分かったコンテストでした。