codeforces 24

F# programming contest

Codeforces Beta #24 参加しました。久しぶりに反省会。

A. Ring road

リング状の無向グラフに向きをつけました。ばらばらに向きをつけたので一周できません。一周したくなったのでいくつかの辺の向きを変えます。各辺の向きを変えるのに必要なコストが与えられたとき，一周できるようにする最小コストを計算しましょう。

出発点を任意に固定して二通り試すだけ。試すだけなのだけど，グラフの扱いに慣れてないので時間がかかる。要練習。

B. F1 Champions

レースを何回かやります。順位に応じて得点が入ります。得点，一位になった回数，二位になった回数，三位になった回数，……と辞書順で比較した場合の優勝者と，一位になった回数，得点，二位になった回数，三位になった回数，……と辞書順で比較した場合の優勝者とを決定しましょう。

やることは問題文に書いてあるので，そのとおりにやるだけ。その「やるだけ」が面倒臭かったのですけど。

反省点その一。Map のインタフェースを把握してなかった。immutable だとか知らなかったし。

反省点そのニ。配列アクセスで型を書かないと型推論がうまくいかない(らしい)ため延々と文句を言われて手間取った。

反省点その三。List.maxBy の挙動を勘違いしていて，型エラーが出てだいぶ時間を食った。最大値を返すんじゃないんですねこれ。

C. Sequence of points

なんか与えられた操作にしたがって点列を作ります。j 番目の座標を求めましょう。ただし j <= 10^18 なので順番に計算するとアウトです。

手で計算したら周期性があることがわかるので，周期で j を割ってから一つずつ計算すれば間に合います。そこまでは紙と鉛筆で済むのでよかったのだけど。

反省点その一。比較演算子をなぜか == と書いてしまって "'op_EqualsEquals' not found" とか言われてしばらくはまった。

反省点そのニ。再び配列アクセスで型を書かなくて文句を言われる。

反省点その三。長さ 2 のリストとサイズ 2 の tuple を混同していて妙な型エラーが出て混乱した。ついでに int * int64 がほしかったけど int64 list になってて余計な型合わせをやったり。

対処

慣れてないとか知らないはまあ仕方ないとして，他のはなんか対処のしようがあるだろうということで二つほど。

(* 配列アクセスは関数にしてしまう *)
let aref (a : 'a array) i = a.[i]

(* tuple として行を読み込む *)
let readPair f1 f2 = 
  let [|a; b|] = stdin.ReadLine().Split([|' '|]) in f1 a, f2 b
let readTriple f1 f2 f3 = 
  let [|a; b; c|] = stdin.ReadLine().Split([|' '|]) in f1 a, f2 b, f3 c

op_EqualsEquals については一回やれば覚えるからいいことにしましょう。