「第23回オフラインリアルタイムどう書くの問題」をPHPで解く
http://qiita.com/Nabetani/items/7ba11167ea28c929fcf2
http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/
くねくね増加列
5*5のマス目から単調増加列を全て取り出した場合、最も長いものを探す。
<?php
class SNAKEMOINC{
/**
* くねくね増加列
* @param String 「01224/82925/69076/32298/21065」みたいな文字列
* @return int 「6」みたいな数値
*/
public function get($input){
$input = str_replace('/', '', $input);
$tmp=[];
for($i=0;$i<strlen($input);$i++){
// 各升スタートでの最大長を取得
$tmp[] = $this->getMax($input, $i, 1);
}
// 一番長かった枝
return max($tmp);
}
/**
* 最長ルートを取得
* @param String input
* @param int 開始位置
* @param int 現在のルート長
* @return int 最大ルート長
*/
private function getMax($input, $pos, $loop){
$tmp=[$loop];
foreach($this->getLargeAdjacent($input, $pos) as $val){
$tmp[] = $this->getMax($input, $val, $loop+1);
}
return max($tmp);
}
/**
* 隣接4箇所のうち、自分より大きいところがあれば取得
* @param String input
* @param int 現在位置
* @return [] 隣接位置
*/
private function getLargeAdjacent($input, $pos){
$ret = [];
foreach($this->getAdjacent($pos) as $val){
if($input[$pos] < $input[$val]){
$ret[] = $val;
}
}
return $ret;
}
/**
* 隣接4箇所の位置を取得
* @param int 現在位置
* @return [] 隣接位置
*/
private function getAdjacent($pos){
if($pos>=5){ $ret[] = $pos-5; } // 上
if($pos<20){ $ret[] = $pos+5; } // 下
if($pos%5!==0){ $ret[] = $pos-1; } // 左
if($pos%5!==4){ $ret[] = $pos+1; } // 右
return $ret;
}
}
// テスト
$test = [
['01224/82925/69076/32298/21065', '6'],
/* 省略 */
];
$snakemoinc = new SNAKEMOINC();
foreach($test as $key=>$data){
$answer = $snakemoinc->get($data[0]);
if($answer !== (int)$data[1]){
print('えらー');
}
}
極めてふつーに、伸ばせるところに手を伸ばしているだけです。
メモ化すら行っていないという手抜きっぷり。
まあ計算量が問題になるサイズではないからいいでしょう。
かかった時間は50分くらい。
ところで概ね毎回のことなんだが、他人の回答例を見てみても全く理解できぬ。
Author And Source
この問題について(「第23回オフラインリアルタイムどう書くの問題」をPHPで解く), 我々は、より多くの情報をここで見つけました https://qiita.com/rana_kualu/items/1dce701ff3c5e80199f4著者帰属:元の著者の情報は、元の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 .