ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。2018-10-08オフラインリアルタイムどう書くE27参加しましたyhpgはじめに2018/10/6開催の「オフラインリアルタイムどう書くE27」に参加しましたので、そのレポートです。どんな感じ?今回は私含めて5名でした。いつものメンバーなので、まあ、自己紹介は簡単に。今回の問題は、@Nabetaniさんです。事前問題よりやや難というお話でしたが...。結果的には確かにちょうどそんな感じだったと思います。組んだら割とあっさりという感じでした。タイトルは「とあるカードゲーム」です。詳細は問題のサイトをご覧ください。7種類(A~G)のスート、1~9の数(ランク)からなる63種類のカードを考える。)与えられた8枚セットの手札の得点を計算し答えとする。得点にならない場合は"-"が答えとなる。得点の計算方法は次の通り手札を全て2枚以上の複数の組に、それぞれが「ストーリー」か「カインド」のどちらかを構成するように分割する。※分割できなければ得点なしストーリーとは同一スートでランクが連番、カインドとは同一ランク(スートは任意)の組を指す。複数の分割方法がある場合は、最も点数が高い方法を採用すること。なんというか、トランプゲームのセブンブリッジを思い出すような状況です。問題のイメージ問題提示と同時に、状況説明の図も紹介されました。...なので、イメージ的には図形の矩形分割でもあるのですね。それぞれのカードは2次元平面上のマスに対応し、繋がっているマスをそのまま組にするか、それとも途中で切るか、という考え方ができるわけです。(会場で考えて)失敗した点ということで、マスの連結ということで、孤立していて必ず隣と繋がらざるを得ない状況から攻めようとしたのですが...。問題のケースの#7や#8が典型なのですが、どこを切って・繋いでを考える方の比重が遥かに大きく、あまり役に立たなかったのですね。いうことで、最初から探索をメインに考えるべきでした、というのが反省点でした。解法(深さ優先探索)これはcedretaberさんの解法とほぼ同じなのですが。)2次元上のマスとして考えた場合、いずれかのマスがストーリー/カインドに相当する幅1長方形の左/上端になるはずです。)$という再帰で計算することができます。これはDFS(深さ優先探索)で書けるということです。それをケアすると面倒なので、ストーリー/カインドがちゃんと成立するかどうかだけで全パターンを挙げてMaxを計算するようにしました。そのRubyによる実装はこちらです。制御し、残ってるマスを1つ1つ端にするよう試し、伸ばせる限り伸ばしていって、それぞれの長さで再帰をかけて分割方法(に対応した点数)を挙げていくような感じです。左上から順に連番を振って1次元化して考えています。することで、同一スート隣接ランクは差1、同一ランク隣接スートは差10という違いだけで同一視することができてお得です。限られたパターンしかないので、順列で総当たりするという方法もありました。このように色々アプローチが考えられるというのは面白いところです。終わりにさて次の開催案内が出ていますので、興味がある方は是非ご参加を。※新規参加者増えないかなあ...とも思うのですが、なかなかいいアピールは思いつかず...。問題に紹介されています。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。