はじめに

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

どんな感じ?

今回は私含めて5名でした。いつものメンバーなので、まあ、自己紹介は簡単に。

問題

今回の問題は、@Nabetaniさんです。事前問題よりやや難というお話でしたが…。結果的には確かにちょうどそんな感じだったと思います。なお私は方針が良くなかったことに気付かずtime up ( 10秒で支度しな! は無理だった )。でも後で ( 発表大会中に ) 組んだら割とあっさりという感じでした。

タイトルは「とあるカードゲーム」です。詳細は問題のサイトをご覧ください。概要は次の通りです。

7種類(A～G)のスート、1～9の数(ランク)からなる63種類のカードを考える。( トランプのようなものと見て大過ない )
与えられた8枚セットの手札の得点を計算し答えとする。得点にならない場合は"-"が答えとなる。
得点の計算方法は次の通り
- 手札を全て2枚以上の複数の組に、それぞれが「ストーリー」か「カインド」のどちらかを構成するように分割する。
  ※分割できなければ得点なし
- ストーリーとは同一スートでランクが連番、カインドとは同一ランク(スートは任意)の組を指す。
- 得点は、分割した組それぞれの (枚数-1)² の値の総和。
- 複数の分割方法がある場合は、最も点数が高い方法を採用すること。

なんというか、トランプゲームのセブンブリッジを思い出すような状況です。

解説

問題のイメージ

問題提示と同時に、状況説明の図も紹介されました。…なので、イメージ的には図形の矩形分割でもあるのですね。

なので、それぞれのカードは2次元平面上のマスに対応し、繋がっているマスをそのまま組にするか、それとも途中で切るか、という考え方ができるわけです。

(会場で考えて)失敗した点

ということで、マスの連結ということで、孤立していて必ず隣と繋がらざるを得ない状況から攻めようとしたのですが…。問題のケースの#7や#8が典型なのですが、どこを切って・繋いでを考える方の比重が遥かに大きく、あまり役に立たなかったのですね。

ということで、最初から探索をメインに考えるべきでした、というのが反省点でした。

解法(深さ優先探索)

これはcedretaberさんの解法とほぼ同じなのですが。( というか解法発表観てから組んだので )

2次元上のマスとして考えた場合、いずれかのマスがストーリー/カインドに相当する幅1長方形の左/上端になるはずです。そのため、あるマスをその「端」として固定すると、

$(固定した場合の最終的な得点)=Max( 1+(横2の矩形を取り去った残りの点数), 4+(横3の矩形を取り去った残りの点数), \cdots, \\ 1+(縦2の矩形を取り去った残りの点数), 4+(縦2の矩形を取り去った残りの点数),\cdots )$

という再帰で計算することができます。

つまり、これはDFS(深さ優先探索)で書けるということです。 …本当言うと、ある程度の高得点が確定した時点で後の探索を打ち切るようなこともできるはず ( 今回の得点方式だと、「最多枚数の組の枚数」だけで決まるため ) なのですが、それをケアすると面倒なので、ストーリー/カインドがちゃんと成立するかどうかだけで全パターンを挙げてMaxを計算するようにしました。

そのRubyによる実装はこちらです。矩形を横に伸ばすか、縦に伸ばすかを d で制御し、残ってるマスを1つ1つ端にするよう試し、伸ばせる限り伸ばしていって、それぞれの長さで再帰をかけて分割方法(に対応した点数)を挙げていくような感じです。

なお、図で考えた場合は2次元なのですが、( いつもの手ながら ) 左上から順に連番を振って1次元化して考えています。そうすることで、同一スート隣接ランクは差1、同一ランク隣接スートは差10という違いだけで同一視することができてお得です。

それ以外の解法

出題者の鍋谷さんの実装例にもありますが、分割枚数は 8,6-2,4-4,4-2-2,3-3-2,2-2-2-2 と限られたパターンしかないので、順列で総当たりするという方法もありました。これは考えてなかったので目から鱗 ( もちろん大規模化したら計算量が爆発しますが )。

このように色々アプローチが考えられるというのは面白いところです。

終わりに

さて次の開催案内が出ていますので、興味がある方は是非ご参加を。

※新規参加者増えないかなあ…とも思うのですが、なかなかいいアピールは思いつかず…。

なお、今回の色々な方の実装例は、オフラインリアルタイムどう書く E27 の問題に紹介されています。

ange1のブログ

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