Clever Geek Handbook

CodinGame 11月：フー博士によるメモ

画像 土曜日（2013年11月23日）にCodinGameから別のコンテストがありました 。 そして、同日、Doctor Whoシリーズの最初の発行からちょうど50年が経過したため、コンテストのすべてのタスクはこのトピックに関連していました。 私の記事では、タスクの1つを分析し、ソリューションを説明し、その欠点を示します。



コンテストについて



CodinGameコンペティションに2回参加しています。 前回はoDeskとの競争でした。 そこでは65位になりましたが、タスクは主観的には簡単でした。 今回は、コンテストの形式は変更されていません。2つのタスク、 選択できる15の言語 、4時間、1,000人以上の参加者。 コードはビルトインエディターに直接入力でき、入念に準備されたテストもそこで実行できます。



最初のタスクは、いわば「ウォームアップのための」シンプルなものでした。 しかし、2つ目からは、スポーツプログラミングに不慣れな人として、私の髪の毛が逆立ちしました。 私は30分かけてタスクを解析し、それを理解し、これが冗談ではなく、残りの2時間半で書くことができると確信させようとしました。 私があなたと知り合いたいのはこの仕事です。



短い課題



黒と白のピクセルのブロックの形式で表示された白黒の画像から一連のノートを認識します。

画像



タスクの詳細



画像 写真は5行の音楽スタッフを示しています。 ノートは、ルーラー上、ルーラー間、または追加のルーラー上に配置できます。 音符の先頭は空でも塗りつぶしてもかまいません。つまり、音の長さは異なります（空-半音、塗り-4分の1）。 ミュージシャンの下半分にある音は静かに上に録音され、上の部分は落ち着いて録音されます。 穏やかなメモ「B」は上下に向けることができます。



データはSTDINから取得され、応答はSTDOUTに返される必要があります。 スクリプト入力には2行があります。1行目はスペースで区切られた画像の幅と高さ、2行目はエンコードされた画像です。 画像は、ランレングスエンコーディングを使用して送信されます。 同じ色のピクセルのシーケンスが1文字にエンコードされ（黒ピクセルの場合はB、白の場合はW）、スペースの後にスペースが表示され、その色のピクセル数を示します。 たとえば、W 5 B 20 W 16は5つの白ピクセルを意味し、その後に20の黒ピクセルと16の白ピクセルが続きます。 画像は上から下、左から右にエンコードされます。 1つのブロックは次の行に続くことができます。 出力は、スペースで区切られた音符（および音符の長さ）を示す文字列でなければなりません。 割り当てによると、ベアラーの上半分と下半分の音には違いはありません。 文字H（ 2分音符）またはQ（ 4分の1 ）で送信される長さのみが重要です。



画像オプション：



100 <幅<5000

70 <高さ<300

ミュージカルルーラーの最小幅と穏やかな1ピクセル

2つのノート間の最小距離1ピクセル

2つのルーラー間の距離は、少なくとも8ピクセルで、ルーラーの幅の少なくとも4倍です。



例



ログイン： 画像
120 176 W 4090 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 1020 B 2 W 118 B 2 W 118 B 2 W 118 B 2 W 118 B 2 W 26 B 10 W 82 B 2 W 25 B 12 W 81 B 2 W 23 B 4 W 8 B 4 W 79 B 2 W 23 B 2 W 12 B 2 W 79 B 2 W 22 B 2 W 14 B 2 W 78 B 2 W 21 B 3 W 14 B 3 W 77 B 2 W 21 B 2 W 16 B 2 W 77 B 2 W 20 B 3 W 16 B 3 W 36 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 60 B 2 W 20 B 2 W 18 B 2 W 76 B 2 W 20 B 3 W 16 B 3 W 76 B 2 W 20 B 3 W 16 B 2 W 77 B 2 W 20 B 4 W 14 B 3 W 77 B 2 W 20 B 4 W 14 B 2 W 78 B 2 W 20 B 2 W 1 B 2 W 12 B 2 W 79 B 2 W 20 B 2 W 1 B 4 W 8 B 4 W 79 B 2 W 20 B 2 W 3 B 12 W 81 B 2 W 20 B 2 W 4 B 10 W 82 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 56 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 46 B 10 W 4 B 2 W 20 B 2 W 81 B 12 W 3 B 2 W 20 B 2 W 79 B 16 W 1 B 2 W 20 B 2 W 79 B 16 W 1 B 2 W 20 B 2 W 78 B 20 W 20 B 2 W 77 B 21 W 20 B 2 W 77 B 21 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 77 B 20 W 21 B 2 W 77 B 20 W 21 B 2 W 78 B 18 W 22 B 2 W 79 B 16 W 23 B 2 W 79 B 16 W 23 B 2 W 81 B 12 W 25 B 2 W 56 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 2420 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 5050




出力： 
 AQ DH




スクリプトが合格するすべてのテストのリストは、 ここにあります 。



解決策



基本的なアルゴリズムについて説明しますが、コードは提供しません。 誰にそれが面白い-あなたはここを見ることができます（perl）。 他の参加者の決定は、結果ページで見つけることができます 。 この問題を自分で解決したい場合は、数週間でトレーニングで利用できるようになるでしょう。



解決策
1）入力データを解析し、画像列の配列を形成します



2）空の列（図の緑色の丸）を無視して、列を調べます。 遭遇する最初の列には黒いピクセルがあり、ノート間のセパレーターとして保存されます（図では青で囲まれています）。 セパレータと一致しない空ではない列はすべて、メモとしてカウントされ（図の赤丸）、個別に保存されます。



3）一連のノートを調べて、各ノートを認識します



4）メモの中央の列を取る



5）音符間の間隔をすべてチェックします（紫色でマーク）







6）各間隔の可能なオプション：

-間隔に黒いピクセルが含まれていない（空）-メモが見つからなかったため、次へ

-最初のピクセルが黒で、間隔に白ピクセルが含まれていない-ルーラー間の四分音符が見つかっている

-最初のピクセルは黒で、間隔には白いピクセルが含まれています-ルーラー間の半音が見つかりました

-間隔に白黒のピクセルが含まれている-次の行に半分の音符が見つかった

-そうでない場合-次の行に4分音符があります





ソリューションの欠点



決定の間、私は写真に関していくつかの仮定をしました。 明らかに、これは条件に示されていませんが、すべてのテストでこれらの仮定が満たされました。 いずれかの条件に違反した場合、画像はエラーで処理されます。



仮定：

1）最初の空ではない列はセパレータであり、音符の始まりではありません;

2）ルーラーの幅とそれらの間の距離は、全体像で変化しません。

3）音符は2つの定規の間のすべてのスペースを占有します。



まとめ



この問題の解決には2時間40分かかりました。 問題は完全に解決され、すべてのテストに合格しました。 コンテストの結果によると、私は23位になりました。


More articles:


All Articles