http://nabetani.sakura.ne.jp/hena/ord17foldcut/
http://qiita.com/Nabetani/items/ebd9d7deb30c57447806
折って切る、何処かで見たと思ったら第18回の参考問題に似ている。
なので同じように考えれば解けるかな？
解けませんでした。
展開図を作るところまでは同じなので一瞬だったのですが、そこから穴の数をどうやって数えるのかというところで詰まった。
結局今回の展開図の特徴を用いた超力業で解きました。
かかった時間は1.5時間くらい。
絶対なんかもっとまともな数え方があるはず。
というか図にせずに計算する方法があるはず。
PR
http://qiita.com/Nabetani/items/ebd9d7deb30c57447806
折って切る、何処かで見たと思ったら第18回の参考問題に似ている。
なので同じように考えれば解けるかな？
001 | <?php |
002 |
003 | class FOLDCUT{ |
004 | |
005 | /** |
006 | * 折って切る |
007 | * @param String 「RRTRB-bl」みたいな文字列 |
008 | * @return int 「6」みたいな数値 |
009 | */ |
010 | public function get($input){ |
011 | // 入力値を分解 |
012 | $input = explode('-', $input); |
013 | $loop = str_split(strrev($input[0]), 1); |
014 | |
015 | // 初期値を作成 |
016 | switch($input[1]){ |
017 | case 'tl': $data = ['01', '11']; break; |
018 | case 'tr': $data = ['10', '11']; break; |
019 | case 'bl': $data = ['11', '01']; break; |
020 | case 'br': $data = ['11', '10']; break; |
021 | } |
022 | |
023 | // 展開する |
024 | foreach($loop as $key=>$val){ |
025 | $data = $this->{'extract'.$val}($data); |
026 | } |
027 | |
028 | // 穴を数えて返す |
029 | $count = $rowflg = $colflg = 0; |
030 | $collen = strlen($data[0]); |
031 | foreach($data as $row=>$line){ |
032 | // 穴は必ず2*2になるので、右上でカウントしたら下の行は飛ばす |
033 | if($rowflg){ $rowflg=0;continue; } |
034 | $colflg = 0; |
035 | for($col=0;$col<$collen;$col++){ |
036 | // 空があった |
037 | if(!$line[$col]){ |
038 | // 最上段/最下段は穴にならない |
039 | if(!$row || !isset($data[$row+1])){ |
040 | $rowflg++; |
041 | continue; |
042 | } |
043 | // 次が1であればカウント |
044 | if($colflg && isset($line[$col+1]) && $line[$col+1]){ |
045 | $count++; |
046 | $rowflg++; |
047 | continue; |
048 | } |
049 | // 空がなかった |
050 | }else{ |
051 | $colflg++; |
052 | } |
053 | } |
054 | } |
055 | return $count; |
056 | } |
057 | |
058 | // 右半分を手前に折って、左半分に重ねる |
059 | private function extractR($data){ |
060 | return array_map(function($val){ |
061 | return $val . strrev($val); |
062 | }, $data); |
063 | } |
064 | |
065 | // 左半分を手前に折って、右半分に重ねる |
066 | private function extractL($data){ |
067 | return array_map(function($val){ |
068 | return strrev($val) . $val; |
069 | }, $data); |
070 | } |
071 | |
072 | // 上半分を手前に折って、下半分に重ねる |
073 | private function extractT($data){ |
074 | return array_merge(array_reverse($data), $data); |
075 | } |
076 | |
077 | // 下半分を手前に折って、上半分に重ねる |
078 | private function extractB($data){ |
079 | return array_merge($data, array_reverse($data)); |
080 | } |
081 | |
082 | } |
083 | |
084 | // 以下はテスト |
085 | $test = [ |
086 | ['RRTRB-bl', '6'], |
087 | ['R-tr', '0'], |
088 | ['L-br', '0'], |
089 | ['T-tl', '0'], |
090 | ['B-tl', '0'], |
091 | ['BL-br', '0'], |
092 | ['LB-tl', '0'], |
093 | ['RL-tl', '0'], |
094 | ['BL-tl', '0'], |
095 | ['TL-bl', '0'], |
096 | ['RT-tr', '1'], |
097 | ['TRB-tl', '0'], |
098 | ['TRL-bl', '0'], |
099 | ['TRB-br', '2'], |
100 | ['LLB-bl', '2'], |
101 | ['RTL-tr', '1'], |
102 | ['LBB-tr', '0'], |
103 | ['TLL-tl', '2'], |
104 | ['RLRR-tr', '0'], |
105 | ['BBTL-tl', '4'], |
106 | ['TBBT-tr', '0'], |
107 | ['LLBR-tl', '0'], |
108 | ['LBRT-tl', '2'], |
109 | ['RLBL-bl', '4'], |
110 | ['BRRL-br', '3'], |
111 | ['TBBTL-tl', '8'], |
112 | ['TLBBT-br', '0'], |
113 | ['LRBLL-br', '7'], |
114 | ['TRRTT-br', '6'], |
115 | ['BBBLB-br', '0'], |
116 | ['RTTTR-tl', '4'], |
117 | ['BBLLL-br', '6'], |
118 | ['RRLLTR-tr', '16'], |
119 | ['TTRBLB-br', '8'], |
120 | ['LRBRBR-bl', '14'], |
121 | ['RBBLRL-tl', '8'], |
122 | ['RTRLTB-tl', '12'], |
123 | ['LBLRTR-tl', '14'], |
124 | ['RRLTRL-tl', '16'], |
125 | ['TBLTRR-br', '12'], |
126 | ['TTTRLTT-bl', '30'], |
127 | ['TBBRTBL-tr', '15'], |
128 | ['TRTRTLL-tr', '28'], |
129 | ['TLLRTRB-tr', '24'], |
130 | ['RLLBRLB-tr', '15'], |
131 | ['LTLRRBT-tr', '32'], |
132 | ['RBBRBLT-br', '21'], |
133 | ['LLRLRLR-tr', '0'], |
134 | ]; |
135 |
136 | $foldcut = new FOLDCUT(); |
137 | foreach($test as $key=>$data){ |
138 | $answer = $foldcut->get($data[0]); |
139 | if($answer !== (int)$data[1]){ |
140 | print('えらー'); |
141 | } |
142 | } |
展開図を作るところまでは同じなので一瞬だったのですが、そこから穴の数をどうやって数えるのかというところで詰まった。
結局今回の展開図の特徴を用いた超力業で解きました。
かかった時間は1.5時間くらい。
絶対なんかもっとまともな数え方があるはず。
というか図にせずに計算する方法があるはず。
