codeforces 25

programming F# contest

昨日の Codeforces Beta #25 にまた参加しました。Div 2 only に毎回参加できる程度の能力。

反省会。

A. IQ test

三つ以上の自然数が与えられます。一つだけ奇偶が異なるものがあります。それが何番目にあるか答えましょう。

一部で問題文が難しいとの評判があった問題です。確かに evenness という言葉はあまり聞きません。

最初は異なる数字そのものを答えるのかと思って，List.partition で奇数だけのリストと偶数だけのリストに分けて長さが 1 の方をとればいいよね，と書いたら違った。仕方ないので List.findIndex で無理やり位置を割り出す。

インデックスがほしいとわかっていればこんな風にできたのですけど。

let solve inputs =
  let (evens, odds) = List.partition (fun (x, _) -> x % 2 = 0) inputs in
    match evens with [_, i] -> i | _ -> match odds with [_, i] -> i

let n = readInt ()
let inputs = List.zip (readWords int) [1..n]
let () = stdout.WriteLine(solve inputs)

問題文はよく読みましょう。

B. Phone numbers

数字の列を覚えたいです。二つか三つずつまとめると覚えやすいですね。するプログラムを書きましょう。

ほとんどやるだけ。列の長さ n (> 2) として

  • n = 0 mod 3 だったら三つずつ
  • n = 1 mod 3 だったら最初の四文字を二つずつに分けて，残りは三つずつ
  • n = 2 mod 3 だったら最初の二文字をまとめて，残りは三つずつ

としたけど，今思えば mod 2 で考えて

  • n: even だったら二つずつ
  • n: odd だったら最初だけ三つで後は二つずつ

のほうが簡単でしたね。

あと部分文字列の取り方は s.Substring(start, length) です。第二引数は切り出す部分の長さ。

C. Roads in Berland

n 個の都市の間に道路が走っていたり走っていなかったりします。個々の道路の長さはわからないけど各都市間の最短径路が与えられます。新たに道路を敷設したときに最短径路の総和はどうなりますか。

Warshall-Floyd のでき損ないのようなことをしたら TLE をもらいました。よく考えたら i-j 間の最短距離が新しい道路 a-b の新設で短くなるときは，新しい最短径路は必ず i-a-b-j か i-b-a-j なので，そんなことをしなくてもよかった。

それに気付くところまではよかったんですけど，答えを int で計算してて溢れました。結局最後まで気付かなかったし。

教訓。accumulator が int だと溢れると思え。

D. Roads not only in Berland

また n 個の都市の間に道路が走っていたりいなかったりします。今度は連結ではないかもしれません。連結にしたいです。ただし新しい道路を作ると，そちらのメンテナンスのコストを捻出するために，代わりに他の道路をどこか閉鎖しなければなりません。どういう手順で敷設・閉鎖をすればいいでしょう。

たぶん連結成分ごとに分解すると，いくつかの成分が閉路を持つ。その閉路の中のどれかを閉鎖して，新たに他の連結成分へつながる道路を敷設する。これを繰り返していけば最短手順で連結になる。と思う。

実装してません。書ける気しなかったし。コーディング練習が必要。

E. Test

三つの文字列をすべて contingent substring として含むような最短文字列の長さを計算しましょうとか。

見た感じ，よく知らないデータ構造 (suffix array?) が必要だろうと思ったのであまり考えてません。