Facebook HC Qualification Round

今年もやってきましたひどいコンテスト頂上決定戦。

A

文字列を指定された矩形の中に収めるとき、一文字の最大の大きさとして可能な正方形のサイズを答えよ、という問題。

大きさをバイナリサーチする。大きさが決まれば文字数が決定できるので、それにフィットするように収まるかどうかを判定していくだけ。

B

ランダムに生成される二次元配列があるので、ソートしたときに一番小さいものと一番大きいものはいくつずつあるか答えよ、という問題。

乱数がループするので、一方の値が決まっているときに他方の値が乱数のどの範囲を取得するかが分かる。これをSegmentTreeか何かに入れておくと、最大値と最小値が高速に取り出せる。後はスイープしていって、一方の値を小さい方から見ていって、最小値を更新するところが最小値になり得るところで、最大値はその逆。

ひたすら実装あるのみ！

もっと効率良く注目したい点に注目して進んでいく方針もあるみたい。(深く考えていないので適当。)

C

文字列が与えられるので、脅迫文スタイルで目的の文字列を何回作れるか答えよ、という問題。

カウントするだけ。