IAX Contest #2

IAX Contest #2 に参加してきました。

結果は 5問中3問。28人中7位。
いまいちパッとしない感じ。。

システムについて

Ajax なインターフェース。
格好良いんだけど使い勝手はあまりよくない。
特にエディタが全然使えないので、localで作ってアップロードしてました。

exam

13個の 0/1 を入力すると、何個合っているかが返ってくる。

サービス問題。数試せば必ずAcceptがもらえる。
いかに少ない手数で判定するか。

• 1 回の施行で、ある範囲にいくつ 1 があるかがわかり、その範囲は半分ずつに絞っていける。
• あとは運。
• saveする前にsubmitして一回損した orz

ugly

正整数 k に対し、ugly pair (A,B) を以下で定義する
A = B * k^i　　(A >= B, i >= 0)

整数 k と整数列Sが与えられるので、
Sの中で k-uglyとなるペアの組み合わせは何通りあるかを求める。

• Sの中で重複を考慮する。
• 32bitだと桁あふれするので64bit integerを使う。
• multiset を使っているつもりで set を使っててWA連発してた。アホの子め。

count

整数kが与えられ、ノード数kの連結グラフの個数を求める。
簡単そうだけどよく分からず。

isomorph

二つの木の同一性判定問題。
根がどこかわからないので、葉から探索してやる。
各ノードから出る枝の本数でノードの等価性を調べる。
バックトラックでにゃーーっと実装。

points

xy平面上に点がいくつか与えられ、交わらないようにそれらを結ぶ線を引く問題。
幾何だってだけで捨て。勉強しないとなぁ。