以下の図を相似な2つの図形に分割する。図形は裏返しても良い。
こういう問題で図形を裏返して使っても良いってことは暗に「裏返して使え」ってこと。
2005年2月12日の問題は板チョコなのに斜めに切り込みを入れる解だったから,今回も斜めの切り込みを入れるのかなと思ってプログラムで解くことを最初から諦めてじっと見る。
あそことあそこが一致する…
そこから先は2つの図形を延ばしていき,正解へ一直線。
出てきた答えは矩形に沿った切り込みになる。
これならプログラムで解けたかも知れない…
残念!
ということで,今回はプログラムはなし。
今回も時期的にバレンタイン用の問題だったのが,チョコにふさわしくない形だったのでお蔵入りしていたのかも知れない。
Winnyが社会問題化してきた。Winny自体が悪いわけでは無いけど,これだけ情報流出が起きて連日のように報道されるとやはり心配もあるだろう。
私の所にも取引先から調査票が来た。
オウム真理教で大騒ぎだったとき,ちょうど官庁関係の仕事をしていたら,あそこは大丈夫かと聞かれたらしい。こういう調査はそれ以来かな。
私は余計なソフトを入れないし,余計なクリックはしないし,おまけに非常に疑り深いのでウィルス感染の心配もなし。
もっと若ければWinnyとかインストールしていたかも知れない。
(2006.3.21)
ちょっと遅くなってしまったが,矩形区切りの図形なのでやっぱりプログラムを作ってみることにした。
よく見たら2005年2月12日の問題よりも2005年4月1日の問題のほうに似ている気がする。4月1日の問題より図が大きいので同じ手法では出来ない。
まずは以下のように番号を振る。
これをじっと見ると,例えば6と19と32の図形について,これらは同じ図形に含まれることが判る。同じように他の部分についても考えると以下のような分類が出来る。
アルファベットの小文字の矩形は大文字の矩形と同じ図形に含まれることになる。大文字のA〜Gの矩形は7個あるので,これを2つの図形に割り振ることを考える。
例えば以下のように振り分けることが出来る。
このとき同じ色に分けた図形をまとめて一つに考え,それぞれが重なり合うかどうか調べる。
重なりあえば残りの矩形を足していく。
そうするとプログラムはざっくりと次のようになる。
const int M = 13; // 図形全体の大きさ,プログラムを楽にするため縦横同じ大きさとする const byte BLK = 0xFF;// 図形内の空白 const int NUMX = 62; // 図形の矩形は全部で62個ある const int NUMA = 31; // 全部で62なので,2つの図形の半分は31個 const int NUMD = 7; // 最初に決まっているポイントは7点,7点に隣接する点も自動的に決まる const int NUMC = 20; // 最初の7点が決まったとき自動的に決まる点 cstring str_original_zukei[] = { // X :図形内で点のある場所 // A-G :図形を2つに分割したとき肝となる場所 // a-g :図形を2つに分割したとき大文字の点と同じ場所に分類される "......a......", "......a......", "..b.XXAXX.c..", "bbb.XXXXX.ccc", "..BXXXXXXXC..", "..XXXXXXXXX..", "ddDXXXXXX....", "..XEXXFXGgg..", "...e..f..g...", "...e..f..g...", ".............", // 全体の図形は横長なので縦を拡張 ".............", ".............", // ここが空でなくなる図形だとプログラムの修正が必要 }; main() { A〜Gの7点を図形A,Bに振り分ける。 小文字の点を追加する。 図形A,Bが重なるかどうか調べる。 重なれば更に残りの振り分けられていない点を調べる。 }
答えは1件出力されました。
解速度
Pentium Xeon2.4GHz で0.9秒