忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/07/26 15:45 |
PHP5.6.0 「第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分くらい。

ところで概ね毎回のことなんだが、他人の回答例を見てみても全く理解できぬ。
PR


2014/07/21 22:53 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<Smartyで配列のキーにハイフンが使えない理由 | HOME | 買ったものリスト 2014/07/20>>
忍者ブログ[PR]