弱小PHPerの憂鬱

http://qiita.com/Nabetani/items/936e7885f4c607472060
http://nabetani.sakura.ne.jp/hena/ord13blocktup/

積み木の水槽に、水をどれだけ貯められるかを計算します。

<?php
	class BLOCKTUP{
		
		/**
		* 貯められる水容量を返す
		* @param  String 「83141310145169154671122」みたいな文字列
		* @return int 「24」みたいな数値
		*/
		public function get($input){
			$count = 0;
			
			// 0で分割
			$input = explode('0', $input);
			
			// くるくる
			foreach($input as $key=>$block){
				// 幅が2以下であれば0
				if(strlen($block) < 3){continue;}
				// 2文字目から最後-1文字目までをくるくる
				$arr = str_split($block);
				for($i=1; $i<count($arr)-1; $i++){
					// ( 左MAXと右MAXの低い方 - 自分 ) > 0であればそのぶん足す
					$bucket = min(max(array_slice($arr, 0, $i, true)), max(array_slice($arr, $i+1, NULL, true))) - $arr[$i];
					if($bucket > 0){
						$count += $bucket;
					}
				}
			}
			return $count;
		}
		
	}
	
	// テスト
	$test = [
		['83141310145169154671122', '24'],
		['923111128', '45'],
		['923101128', '1'],
		['903111128', '9'],
		['3', '0'],
		['31', '0'],
		['412', '1'],
		['3124', '3'],
		['11111', '0'],
		['222111', '0'],
		['335544', '0'],
		['1223455321', '0'],
		['000', '0'],
		['000100020003121', '1'],
		['1213141516171819181716151413121', '56'],
		['712131415161718191817161514131216', '117'],
		['712131405161718191817161514031216', '64'],
		['03205301204342100', '1'],
		['0912830485711120342', '18'],
		['1113241120998943327631001', '20'],
		['7688167781598943035023813337019904732', '41'],
		['2032075902729233234129146823006063388', '79'],
		['8323636570846582397534533', '44'],
		['2142555257761672319599209190604843', '41'],
		['06424633785085474133925235', '51'],
		['503144400846933212134', '21'],
		['1204706243676306476295999864', '21'],
		['050527640248767717738306306596466224', '29'],
		['5926294098216193922825', '65'],
		['655589141599534035', '29'],
		['7411279689677738', '34'],
		['268131111165754619136819109839402', '102'],
	];

	$blocktup = new BLOCKTUP();
	foreach($test as $key=>$data){
		$answer = $blocktup->get($data[0]);
		if($answer !== (int)$data[1]){
			print('えらー');
		}
	}

なんか見た感じ難しそうだなあと思ってたのですが、実際に作ってみたら予想外に一瞬で終わった。
かかった時間は30分くらい。

考え方は単純です。
「83141310145169154671122」を例に挙げてみると、まず0で分けて「8314131」「145169154671122」にします。
「8314131」を2文字目の「3」で見ると、左側にある壁の最大値は8、右側にある壁の最大値は4、よって左右両方の最大値は4です。
自分の高さは3なので、1升ぶんだけ水が貯まります。
4文字目の「4」で見ると、左の最大値は8、右の最大値は3、自分は4なので貯まりません。
というのを列ごとにくるくるしていくだけです。


「オフラインリアルタイムどう書く」の一覧