オフラインリアルタイムどう書くE18参加しました

はじめに

2017/10/7開催の「オフラインリアルタイムどう書くE18」に参加しましたので、そのレポートです。

どんな感じ?

ここのところ各種イベントとのバッティングで、オフライン参加していなかったのですが。久しぶりの参加&記事掲載です。本来なら子供の運動会だったのですが、そっちで雨で延びたためという微妙な状況ではあったのですが。

さて、今回は初参加の方も多く、久しぶりの満員御礼でした。偏にyancyaさんの、RubyKaigiでの宣伝のおかげなのですが、当のyancyaさんは所用で不参加という。

問題

今回は鍋谷さんの出題回で、問題はドット直角三角形の共通部分でした。概要は次の通りです。

  • 直角二等辺三角形めいた形状に配置されたマス目の塊、2組分の情報が与えられる
  • それらの共通部分のマス目の個数を数える
  • 塊の情報には、二等辺三角形の頂点に相当するマス目の座標、二等辺三角形の高さ、二等辺三角形の中で頂点が上下左右のどこに位置しているかの方向、この3つが含まれる

詳細は上のリンクからご覧ください。

解説

会場で書いたコード

会場で圧倒的多数だったのは、それぞれの塊に所属するマス目情報をそれぞれ列挙し突合させるというもの。或いは両方の塊を含む十分大きなキャンバスを考え、それぞれのマスが塊に所属するか印をつけていき、両方の印がついているマスを数えるというものでした。

ただ、計算量的に高さの二乗のオーダになることが見えるため、一乗以下のアルゴリズムで組むことを目指し、なんとか制限時間一杯で次のコードを完成させました。

方針としては、

  • 小さい方の塊を二等辺三角形の斜辺に沿って平行に短冊状に切り、
  • その短冊と大きい方の塊との共通部分を計算し、足し合わせる

というものです。共通部分は端の座標を計算すれば分かりますから、計算量的には足し合わせの分、小さい塊の高さの一乗で済むことになります。

例えば次の図のように、小さい方 ( 青/紫 ) が高さ4であれば、4個分の共通部分 ( 紫 ) を足し合わせる、ということです。共通部分のサイズは、「青・赤の上端の内下の方」と「青・赤の下端の内上の方」の差を見ればわかります。

f:id:ange1:20171014134356p:plain

ただ問題は、三角形の位置や向きはテストケースによってまちまちですから、どうやって切る方向を考えるか、というところです。

そこで、例によって座標表現を複素数にして、最初に「正規化」を行いました。基準点としては小さい三角形の斜辺の中点、ここを原点$0+0i$とし、三角形の頂点の方向を大きさ1の複素数、すなわちRなら$i^0=1$, Bなら$i^1=i$, Lなら$i^2=-1$, Tなら$i^3=-i$として表現します。T,Bが逆じゃないの? と思われるかもしれませんが、問題の図では「下」が y方向正の向きになっているためです。

その上で正規化を行います。小さい方の斜辺の中点を$z_s$向きを$d_s$、大きい方をそれぞれ$z_b,\,d_b$としたとき、小さい方の斜辺の中点を原点$0$、向きを$1$に合わせるように平行移動+回転を行うと、大きい方の斜辺の中点は$(z_b-z_s)\cdot d_s^{-1}=(z_b-z_s)\cdot \overline{d_s}$、向きは$d_b\cdot d_s^{-1}=d_b\cdot \overline{d_s}$に変換されます。このことを正規化と呼んでいます。
なお、逆数$d_s^{-1}$の代わりに複素共役$\overline{d_s}$ ( コード中10,11行目の.conj ) が等しいのは、$d_s$の大きさが1だからです。

一例として次の図の状況を挙げます。
小さい方の斜辺の中心が$3-3i$、向き$i$に対して、大きい方がそれぞれ$2$、$1$なところ、正規化を行うと、大きい方の中心は$(2-(3-3i))\cdot \overline{i}=(2-(3-3i))\cdot(-i)=3+i$、向きは$1\cdot\overline{i}=-i$に変換される、ということになります。

f:id:ange1:20171014143740p:plain

そこから先は、( 変換後の ) 大きい方の三角形の向きを見て共通部分を探るわけですが…。その時あまりいい方法を思いつかなかったので、case分でゴリっと計算しています。

定数時間解法

しかしながら、会場でも話が出ましたが、$O(1)$で解く方法もあるはずです。ということで、家に戻ってから考えてみました。

基本的なアイデアはこうです。

まず、領域を偶数場・奇数場 ( x座標とy座標の合計の偶奇により ) に分け、それぞれで共通部分を考える。詳しくは触れませんが、これをやっておかないと後で偶奇を考慮した計算が必要になり面倒だからです。
その上で斜向座標系で表現し直します。こうすることで、各三角形が正方形をほぼ半分に割った形に置き換わります。

f:id:ange1:20171014155023p:plain

このように斜向座標系に直す前には、やはり正規化をしておきます。今度は上とはちょっと違いますが、ロジックは同じです。大きい方の三角形の頂点を原点に、頂点が左に来るように変換します。加えて、必要に応じて上下反転を行って、三角形を下に寄せる or 下に斜辺が来るようにしておきます。

ちなみに実際に行うと次のようになります。

f:id:ange1:20171014161635p:plain

後は重なり具合をどう見るか。それは小さい方の三角形の向きに応じて3通りできるのですが、それは次のようなパターンとして見ることができるため、簡単に計算することができます。なお、計算の前に明らかに重ならない部分は削っておきます。

f:id:ange1:20171014163126p:plain

ということでこちらが実装したコードになります。関数 s_fwd, s_rev, s_crs がそれぞれ向きに応じた計算の実装、共通している「階段状の領域」は s_tri です。( s_tri2は「傾いた」に相当します )

終わりに

今回初参加だった方も、また来ていただけると賑やかでうれしいです。終わった後の懇親会には参加できなかったので、次回こそは…。ということで。次は11/4(土)ですので是非。