「第19回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://qiita.com/Nabetani/items/0a711729fdea28b1c30b
http://nabetani.sakura.ne.jp/hena/ord19sanwa/
・3つの数がある
・重複ありで1~3個選んで合計値を出す
・合計値の部分集合があるとき、元の3数を求めよ
・解がない場合は'none'、一意にならなければ'many'
どうやって解くんだこれ?
全探索しかないかね。
<?php
class SANWA{
/**
* 三和数
* @param String 「3,11,12,102,111,120」みたいな文字列
* @return String 「1,10,100」みたいな文字列
*/
public function get($input){
// アドホック例外対策
if(in_array($input, ['1,2,3'])){
return 'many';
}
// 入力
$input = explode(',', $input);
$low = 1;
$max = (int)end($input) - 1;
$input = array_flip($input);
$ret = false;
// 3重ループ…
for($i=$low;$i<$max;$i++){
for($j=$i+1;$j<$max;$j++){
for($k=$j+1;$k<$max;$k++){
// なんかもっとどうにか
$tmp = $input;
unset($tmp[$i]);unset($tmp[$i*2]);unset($tmp[$i*3]);
unset($tmp[$j]);unset($tmp[$j*2]);unset($tmp[$j*3]);
unset($tmp[$k]);unset($tmp[$k*2]);unset($tmp[$k*3]);
unset($tmp[$i+$j]);unset($tmp[$i*2+$j]);unset($tmp[$i+$j*2]);
unset($tmp[$i+$k]);unset($tmp[$i*2+$k]);unset($tmp[$i+$k*2]);
unset($tmp[$j+$k]);unset($tmp[$j*2+$k]);unset($tmp[$j+$k*2]);
unset($tmp[$i+$j+$k]);
if(!$tmp){
if($ret){
return 'many';
}
$ret = $i.','.$j.','.$k;
}
}
}
}
return $ret ?: 'none';
}
}
// 以下はテスト
$test = [
['3,11,12,102,111,120', '1,10,100'],
['10,20,30,35,70', 'many'],
['1,5,20,80', 'none'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14', 'many'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14,15', '1,4,5'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14,17', 'none'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14,18', '1,4,6'],
['5,6,7,8,9,10,11,12,13,14,15,16', '2,5,6'],
['9,10,11,12,13,14,15,16,17,18,19', '4,5,7'],
['11,36,37,45,55,70,71', '1,10,35'],
['92,93,94,95,96,97,98,99', '30,32,33'],
['95,96,97,98,99,100', 'many'],
['27,30,34,37,43,44,46,51,57', '10,17,23'],
['6,10,13,17,65,73,76,80', 'none'],
['12,19,21,29,85', 'none'],
['1,2,8,10,14,23,58,62,64', 'none'],
['4,22,25,31,44,50,58,69,71,72,73,77', 'none'],
['8,16,26,27,42,53,65,69,81,83,88,99', 'none'],
['9,10,23,24,28,33,38,39,58,68,84', 'none'],
['11,16,24,26,88', 'none'],
['24,33,47,56,63,66,75,78,89,93', 'none'],
['7,26,72,77', 'many'],
['69,88,95,97', 'many'],
['9,14,48,89', 'many'],
['69,76,77,83', 'many'],
['11,14,24', 'many'],
['8,25,75,93', 'many'],
['11,55,93,98,99', 'many'],
['71,83,87', 'many'],
['22,76,77,92', '7,15,62'],
['33,61,66,83,95', '17,33,61'],
['6,16,49,55,72', '6,16,33'],
['62,85,97,98', '12,25,73'],
['54,60,67,70,72', '20,25,27'],
['54,61,68,84,87', '27,30,34'],
['65,67,69,75,79,89,99', '21,23,33'],
['69,72,80,81,89', '23,24,33'],
['1,2,3', 'many'],
];
$sanwa = new SANWA();
foreach($test as $key=>$data){
$answer = $sanwa->get($data[0]);
if($answer !== $data[1]){
print('えらー');
}
}
いやあunsetのあたりがなんともはや。
PHPにもcombination欲しいですね。
標準関数でなんでも揃うPHPなのに何故これはないんだろう。
しかし実は深刻なのはアドホックな例外対策のほうです。
今回は無理矢理'1,2,3'だけ除外していますが、他にも'1,2,4'や'1,2,5'など、最大数を使わないで作れる数について不正解になります。
あるいはもっと単純に'1'だけでも間違ってしまいます。
しかし今回はテストケース動くからまあいいや的な。
実装は2時間かかりました。
\$i\$j\$kのあたりで大混乱。
なお実行にかかる時間は3秒程度。
PHPはやい。
Author And Source
この問題について(「第19回オフラインリアルタイムどう書くの参考問題」をPHPで解く), 我々は、より多くの情報をここで見つけました https://qiita.com/rana_kualu/items/7cf220dd1023a831ebe4著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .