paizaオンラインハッカソンVol.2で考えたこと
女子大生とペアプロするだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.2 の私の考えたアルゴリズムをまとめました！
実は、やりはじめた時点では、
動的計画法って言葉も知らなかったのです（笑）
よって、
私自信が非常に初心者な知識しかありませんので、
初心者向けな説明になっています。
間違っていることがあれば、ご指摘下さい。
１．ホームのビット列をウィジェットの高さ分OR演算
まず、最初に思いついた基本的な考え方を示します。
ホームのビット列を、POH2のページにある例２のものとします。
00000
00100
00010
10001
10000
POH2のページにある例２の最初のウィジェットは、高さ:2 幅:2 です。
2*2のウィジェットであれば、
11000
11000
と表せます。
1.1.一番左上の座標で考える
ホームの上２列
00000
00100
を、OR演算すると、「00100」です。
ウィジェットは、高さを考え無くていいので、
（必ず正方形か長方形ですので、ウィジェット側はいくらOR演算しても同じです）
「11000」です。
ホームの「00100」とウィジェットの「11000」をAND演算します。
「00100」AND「11000」⇒「00000」
となり、すべてゼロになるため、この座標はぶつからない
ということになります。
ぶつからないので、座標数を＋１カウントします。
1.2.一番右下の座標で考える
2*2のウィジェットでなので、
00011
00011
がホームに入りきるかを考えます。
ホームの下２列
10001
10000
を、OR演算すると、「10001」です。
ウィジェットは、高さを考え無くていいので、
「00011」です。
ホームの「10001」とウィジェットの「00011」をAND演算します。
「10001」AND「00011」⇒「00001」
となり、すべてゼロとならなかったので、座標数をカウントしません。
以上、この考えで、ウィジェットが通る座標は
カウントすることが可能です。
２．ゼロの並びリストを作成する
当然と言えば当然なのですが、ウィジェットが取り得る全座標を、
１座標ずつチェックしていたら、とてつもなく時間がかかってしまいます。
何も考えないとオーダー（計算量）は、Ｏ[H^3W^3]になります。
オーダーとは、アルゴリズムの計算量を解り易く(？)表現したもので、
その式に比例してプログラム全体の計算量が大きくなります。
何故、単純なアルゴリズムが、Ｏ[H^3W^3] なのかは、
ウィジェットの数が最大H*Wなのでというのもありますが、
解り易く分解すると、
（ホームの高さ * ウィジェットが取り得る縦座標）*（ホームの幅 * ウィジェットが取り得る横座標）* ウィジェットの数
だけの計算をしなければならなくなるからです。
O[(H*H)*(W*W)*(H*W)] ⇒ O[H^3W^3] になってしまいます。
処理時間を短くするためには、この計算量をどれだけ少なくするかに
かかってきます。
もし仮に300桁（or130桁）のOR演算を簡単に高速に行うことができるのであれば、
横方向を走査する必要が無いため、O[H^3W^3] ⇒ O[H^3W] でいけます。
実際にはそんな桁数のOR演算は簡単には行えないため、
横方向の座標数の影響は受けますが、
便宜上、現時点のオーダーは、O[H^3W] としておきます。
当初は、ウィジェットをシフト演算させながら
全座標AND演算をさせていたのですが、これではCase5も
通りませんでした。
最終的に、私が考えたのは、次の方法です。
2.1.ゼロの並び数がわかればいい
ホームのOR演算した結果が仮に
「1000001」 だったとします。真ん中に0が5個並んでいます。
ウィジェットの幅 6 ⇒ 入りきらないので0個
ウィジェットの幅 5 ⇒ 1個しか入りません
ウィジェットの幅 4 ⇒ 2個入ります
ウィジェットの幅 3 ⇒ 3個入ります
ウィジェットの幅 2 ⇒ 4個入ります
ウィジェットの幅 1 ⇒ ホームのゼロの並び数と同じ 5個
ということは、ゼロの並び数さえわかれば、座標数は、
(ホームのゼロの並び数 - ウィジェットの幅 + 1)個
と求めることができます。
ホームのOR演算した結果が仮に
「110011000100011」だとすると、
ゼロの並びリストは、
（2個,3個,3個）
です。
ウィジェットの幅が2とすると、
(ゼロ:2個 - 幅:2 + 1) + (ゼロ:3個 - 幅:2 + 1) + (ゼロ:3個 - 幅:2 + 1)
⇒ (1+2+2)個 ⇒ 座標:5個
と比較的少ない計算で、座標数を求めることが可能です。
つまり、ウィジェットの高さパターンに応じたゼロ並びリストを
作っておけば、ウィジェット数の繰り返しを
オーダーから分離することが可能となります。
O[H^3W^3] ⇒ O[H^3W] ⇒ O[H^2]+O[HW] ⇒ O[H^2] になります。
（ウィジェット数の影響を受けないわけは無いのですが、
オーダー表記は一番高い次数のみ残します。）
2.2.ゼロの並びリストをいかに作るか
解りやすいように、
POH2のページにある例２で考えます。
00000
00100
00010
10001
10000
高さが5なので、
高さ1から高さ5までのゼロ並びリストを作る必要があります。
高さ1のゼロ並びリストは、1行ずつゼロの数を数えて、
{{5},
{2,2},
{3,1},
{3},
{4}}
になります。
高さ2のゼロ並びリストは、まず、元のホームを
2行ごとにOR演算をさせた情報を作ります。
結果、
00100
00110
10011
10001
の4行のホームがあると考えれば良いのです。
{{2,2},
{2,1},
{2},
{3}}
になります。
高さ3のゼロ並びリストは、
2行ごとにOR演算させた結果を、
さらに2行ごとにOR演算させます。
結果、
00110
10111
10011
の3行のホームがあると考えれば良いので、
{{2,1},
{1},
{2}}
になります。
高さ4のゼロ並びリストは、
高さ3のOR演算させた結果を、
さらに2行ごとにOR演算させます。
10111
10111
の2行のホームがあると考えれば良いので、
{{1},
{1}}
になります。
高さ5のゼロ並びリストは、
高さ4のOR演算させた結果の最後の2行を
OR演算させます。
10111
の1行だけのホームがあると考えれば良いので、
{1}
になります。
これより、高さ1より順番にOR演算して、
その結果を残していけば、高さが高くなればなるほど、
行わないとならないOR演算数が減ることが解ります。
オーダーは、
O[H^3W^3] ⇒ O[H^3W] ⇒ O[H^2]+O[HW] ⇒ O[H^2] ⇒ O[H!]
となります。
（前述しましたが、Wの影響を受け無いわけでは無いです。。）
H! の「!」は階乗です。
もし、ホームが5行あるならば、
(5+4+3+2+1)回の処理で済むということになります。
さて、POH2のページにある例２の手計算を続けます。
出来あがったゼロ並びリストは、上記では便宜上、
行ごとに分けて書きましたが、座標数を求める上では
どこの行でカウントしたかは関係無いです。
よって、
高さ1 (5,2,2,3,1,3,4)
高さ2 (2,2,2,1,2,3)
高さ3 (2,1,1,2)
高さ4 (1,1)
高さ5 (1)
となります。
例のウィジェット1個目は、
(2,2)ですので、
高さ2のリストより、
(2-2+1)+(2-2+1)+(2-2+1)+(2-2+1)+(3-2+1)=1+1+1+1+2 = 6個 です。
（ゼロ並びリスト中の1はウィジェットより狭いので無視します）
例のウィジェット2個目は、
(1,1)ですので、
高さ1のリストより、
(5-1+1)+(2-1+1)+(2-1+1)+(3-1+1)+(1-1+1)+(3-1+1)+(4-1+1)=5+2+2+3+1+3+4=20個 です。
例のウィジェット3個目は、
(3,2)ですので、
高さ3のリストより、
(2-2+1)+(2-2+1)=1+2=2個 です。
よって、解答は、
6
20
2
となります。
さらに早く処理させるためには、言語によっては、
以下の考えを取り込むことができます。
☆ゼロリストを降順に並び変えて、
ウィジェット幅より短くなったらループから抜けて処理数を少なくすることが
できます。
☆マップや動的配列が使える言語であれば、ゼロリストを
ゼロの並び数をキー、出現回数を値に変更することで、
ゼロリストの繰り返し数を少なくすることができます。
(ホームのゼロの並び数 - ウィジェットの幅 + 1) 個
↓
(キー：ホームのゼロの並び数 - ウィジェットの幅 + 1) * 値：出現回数 個
になります。
３．桁数が多いOR演算対策は言語ごとに
OR演算のようなビット演算は、
コンピュータにとっては早い処理では
ありますが、以下の問題があります。
文字列（もしくはバイト列）で、
ホーム情報を読み取った場合、
そのままではビット演算できない。
よって、何らかの対策が必要なのですが、
いろいろ試した結果、言語ごとに以下の2通りの方法で対策をしました。
⇒ ホーム文字列を、整数値に置き換えてOR演算した後に文字列に戻す。
整数値は32ビットであれば、正の数は0 ～ 2の31乗-1 までの範囲しか
扱えません。よってホームの幅が大きい場合は、
31桁ずつホームの文字列を区切って計算する必要があります。
また、OR演算後の 整数 ⇒ 文字列
の変換で、桁数が落ちることがあるので、
その補正に気を付けなければなりません。
ちょっと面倒くさいですが、バイト列が扱いにくい（扱えない？）言語は
しかたがないか。というところです。
また、もし64ビットの整数が使えたら、処理は早くなると思います（試してませんが）。
⇒ バイト列で読みこんだホーム文字情報を、1バイトずつ比較して、OR演算させる。
比較する1バイトが同じであれば、そのまま。
異なる場合は、「1」をセットします。
例） A:0101 と B:0110 で、Aに結果を格納
1バイト目 A:0 B:0 ⇒ 同じなので変更なし よって A:0
2バイト目 A:1 B:1 ⇒ 同じなので変更なし よって A:1
3バイト目 A:0 B:1 ⇒ 異なるので A:1
4バイト目 A:1 B:0 ⇒ 異なるので A:1
これで、A:0111 となりOR演算の結果が格納されます。
[1]より、こっちのほうがお手軽ですが、確実にオーダーが、
O[H!W] になってしまうので、もしかしたら、これらの言語も、
[1]の方法でやったほうが良かったのかもしれません。
結局、どの言語でも、この部分が一番処理時間がかかる箇所でした。
C言語のCASE7も0.02で、最速に出来なかったため、
アルゴリズムそのものに問題があるのか、もっと高速にOR演算の結果を
出せる方法があるのか、解らずじまいでした。
４．動的計画法って？
4月30日に発表された、模範回答のページを見て、初めて知った言葉です。
ウィキペディアによると、
下記2条件を満たすアルゴリズムの総称
1.分割統治法：部分問題を解き、その結果を利用して、問題全体を解く
2.メモ化：部分問題の計算結果を再利用する
とのこと。
ということは、常に2行分の部分的な箇所のOR演算しかしてないから分割統治法なのか、
前のOR演算の結果を利用して計算量を減らしているからメモ化なのか。。
実は良く解っていません（笑
ただ、漸化式をこしらえて、再帰的にうんぬんという手法は取っていないので、
ちょっと違うのかなー？
でも、競技プログラミングの世界では、動的計画法(DP)の考え方は必須のようで、
解っていれば、もっと早く解けるかも知れないので、勉強しましょう。
５．テストパターンからの対策
少しでも高速化するために、テストパターンを推測して、
いろいろ試したのですが、
以下の方法の効果はありませんでした。
5.1.OR演算の結果、途中ですべて「1」になったら、計算数を大幅削減できる
例えば、以下のホームがあったとします。
00001
00100
11010
10001
10000
高さ「3」の計算途中で、「11111」が出てくるのですが、
この段階で、高さ4や、高さ5は計算する必要が無いことが解ります。
もし、「1」の数がそれなりにあれば、効果があるのですが、
今回のテストパターンでは効果無しでした。
5.2.OR演算をする前に、値のどちらかがすべて「0」だったら、OR演算しなくていい
すべて「1」が存在しないのであれば、
すべて「0」は存在するだろうと思ったのですが。。効果無しでした。
そもそも値がすべて「0」であることの判定に時間がかかっていて、
ダメなのかも知れません。
ということは、おそらく、
ホーム上のどの行も列も「1」が必ず入っているが、
非常に「1」の数が少ないというテストパターンになっているのでしょう。
結局、ホームの大きさなどによって場合分けして、
それぞれのテストケースに対して、
最適化するということは出来ませんでした。
（なんかずるい感じがするので、しなくていいといえばいいんですが）
6.ソース
どの言語にしようか迷いましたが、生まれて初めてチャレンジした
Pythonで最速レコード（たぶん）を出せたので、
記念に貼っておきました。Pythonそのもののことは、
ほとんど解ってません。PHP版を移植しただけです（笑
コメントや変数名が上記の説明とあまりマッチしてないですが。。
あとこのブログへのGist貼り付けのやりかたが解らなくって苦労しました（笑
