夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

TCOのMM和訳

今日はSRMの過去問解きまくる予定で。。。

結局インターネットにつなげず出来ませんでしたので、

その時間つかってやったMMの和訳。

問題文

高さがH、幅がWの黒と白のビットマップイメージは白い背景に描かれたさまざまなサイズのnLetter個の黒文字によってつくられています。あなたはすべてのイメージを見ることは出来ませんが、この列をスキャンし結果を解析することによってこのコンテンツを図で示すことは出来ます。あなたの仕事はできるだけ完全にイメージを再現することです。

あなたのコードはメソッドを修復する道具である必要があります。H,W,nLetterとイメージの中の黒のピクセルの数nbがパラメータとしてあなたに与えられます。あなたはイメージのR列をスキャンし長さWの文字列としてこのコンテンツ返すときにクラスImageToScanのscan(R)メソッドをライブラリとして呼び出すことが出来ます。元々のイメージのR列とi行にあるピクセルのコンテンツを表す文字列にある文字iは次のようになります。:'0'は白、'1'は黒。あなたはあなたの予想するイメージをvector で返さなくてはなりません。あなたの返り値はH個の要素があり、それぞれがW個の文字をもち、そしてそれは'0'か'1'しか含まれていてはなりません。i番目の要素のj番目の文字はi列のj行に描かれていなくてはなりません。
あなたのテストケースによるスコアは次のように計算されます。あなたの返す値のすべてのスキャンされていない列はピクセル毎に正しいイメージのピクセルと比べられます。正しいと推測されたピクセルの数CPと元々のイメージのスキャンされていない行にある白のピクセルの総数WPは計算されます。スコアは0と(CP-WP)/nbのうちの最大値で表されます。あなたの総スコアはすべてのテストケースの独立したスコアを足したものになります。

このテストケースに0点であるようないくつかの結果の返り値は無効になります。存在してない列をスキャンするという試みと、同じ列を一回以上スキャンしようという試みは無効であると考えられます。そのようなスキャンでのスキャン関数の返り値は空の文字列になります。さらにもしあなたのコードが結果として妥当なイメージを描画するものを返しても、このテストケースにおいて0点の無効な結果を作ります。

テストケースは次のように生成されます:H,W,とnLetterがランダムに、そして一律に選ばれます。その後、文字がイメージに描かれていきます。それぞれの文字はA~Zの文字、8~28のフォントサイズとplainかboldのフォントスタイルからランダムに一様に選ばれます。相当するイメージは先に生成された文字イメージのリストから行きます。次に、この文字の位置はランダムに選ばれ、つまりその文字は完全にイメージの中に位置し、先に位置していた文字をそれ以上横切ることはありません。より明確には、もっとも小さな境界の長方形にそれぞれの文字は保存され、それらの境界の長方形の交差点の大きさをたした文字のそれぞれの位置のペアはこれらの二つの境界の長方形のいくつかの大きさの和の最大で半分にすることができます。もし100回間違った新しい文字を配置しようとしたならば、その配置は交差点によるチェックを受けません。最後に、nbは結果のイメージから計算されます。

生成で使われたイメージの文字はダウンロードすることができます。それぞれのイメージは三つのパートからなる名前のファイルにわかれて保存されています:文字、フォントスタイル('P'はplain、'B'はbold)とフォントサイズ。それぞれのファイルは文字の境界線の長方形の高さH0と幅W0をふくむ二つのラインからスタートします。これはイメージを文字で表現しながら続きます:H0列にそれぞれの含まれているW0文字'0'/'1'。

ビジュアライザはオフラインテストを行えます。あなたはそのソースコードをテストケースの生成とスコアリングを正確に履行できたかチェックできます。

まぁ実際やってみないとわかんないし、コレだと不完全だけど大体わかるでしょ?

というわけです。