http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
http://nabetani.sakura.ne.jp/hena/ord27raswi/
分岐と行き止まり
右に進む線路的な。
文字列になおすあたりが野暮ったい。
かかった時間は2時間程度。
再帰は苦手なのです。
しかし昔やったような記憶があるなあ、と思ったら実際にやってました。
前の奴は全ルート求めてから行き止まりを排除していましたが、今回は行き止まりを排除してからルートを求めています。
もっとも今回は全部で21ルートしかないので、全部並べたほうがずっと楽だったりしますが。
最初からこうしたほうが手っ取り早かった。
http://nabetani.sakura.ne.jp/hena/ord27raswi/
分岐と行き止まり
右に進む線路的な。
<?php
class RASWI{
// 進行可能ルート
private $nextOrigin = [
1=>['a','g'],
2=>['d','h'],
3=>['b','f'],
'a'=>['b'],
'b'=>['c',5],
'c'=>[4,6],
'd'=>['c','e'],
'e'=>[5],
'f'=>['g'],
'g'=>['c','e','h'],
'h'=>[4,'i'],
'i'=>[6],
];
private $next = [];
/**
* 分岐と行き止まり
* @param String 「befi」みたいな文字列
* @return String 「14,16,24,26」みたいな文字列
*/
public function get($input){
$this->next = $this->nextOrigin;
// 通れない道を削除
foreach(str_split($input) as $val){
unset($this->next[$val]);
}
// 全ルートを取得
$start = [ 1=>1, 2=>2, 3=>3 ];
$routes = $this->getRoute($start);
// 分岐/行き止まりを排除し、開始/終了地点だけ抽出
$route = [];
foreach($routes as $key=>$val){
$route[$key] = array_filter(array_unique(iterator_to_array(
new RecursiveIteratorIterator(new RecursiveArrayIterator($val)), false)),
function($val){ return is_int($val); }
);
sort($route[$key]);
}
// 文字列にして返す
$ret = '';
foreach($route as $key=>$val){
foreach($val as $key2=>$val2){
$ret .= $key . $val2 . ',';
}
}
if(!$ret){ return '-'; }
return substr($ret, 0, -1);
}
/**
* 辿れる全ルートを取得する
* @param [1,2,3]
* @return [1=>[[b],[[4,6],[e],...]
*/
private function getRoute($arr){
array_walk_recursive($arr, function(&$val, $key){
$val = isset($this->next[$val]) ? $this->next[$val] : $val;
if(is_array($val)){
$val = $this->getRoute($val);
}
});
return $arr;
}
}
// 以下はテスト
$test = [
['befi', '14,16,24,26'],
['abc', '14,15,16,24,25,26,34,35,36'],
['de', '14,15,16,24,26,34,35,36'],
['fghi', '14,15,16,24,25,26,34,35,36'],
['abcdefghi', '-'],
['ag', '24,25,26,34,35,36'],
['dh', '14,15,16,34,35,36'],
['bf', '14,15,16,24,25,26'],
['ch', '15,25,35'],
['be', '14,16,24,26,34,36'],
['ci', '14,15,24,25,34,35'],
['cgi', '15,24,25,35'],
['acgi', '24,25,35'],
['cdefghi', '15,35'],
['acdefghi', '35'],
['cdegi', '15,24,35'],
['bcdegi', '24'],
['afh', '14,15,16,24,25,26,34,35,36'],
['abfh', '14,15,16,24,25,26'],
['dfh', '14,15,16,34,35,36'],
['cdfh', '15,35'],
['deh', '14,15,16,34,35,36'],
['cdeh', '15,35'],
['abefgh', '24,26'],
['abdefgh', '-'],
['acfghi', '25,35'],
['acdfghi', '35'],
['cegi', '15,24,35'],
['abcfhi', '15,25'],
['abcefhi', '-'],
['abdi', '14,15,16,24,34,35,36'],
['abdfi', '14,15,16,24'],
['bdi', '14,15,16,24,34,35,36'],
['bdfi', '14,15,16,24'],
['adfh', '14,15,16,34,35,36'],
['adfgh', '34,35,36'],
['acdfhi', '15,35'],
['bcdfgi', '24'],
['bcdfghi', '-'],
['defi', '14,15,16,24,34,35,36'],
['defhi', '14,15,16,34,35,36'],
['cdefg', '15,24,26,35'],
['cdefgi', '15,24,35'],
['bdefg', '24,26'],
['bdefgi', '24'],
];
$raswi = new RASWI();
foreach($test as $key=>$data){
$answer = $raswi->get($data[0]);
if($answer !== $data[1]){
print('えらー');
}
}
文字列になおすあたりが野暮ったい。
かかった時間は2時間程度。
再帰は苦手なのです。
しかし昔やったような記憶があるなあ、と思ったら実際にやってました。
前の奴は全ルート求めてから行き止まりを排除していましたが、今回は行き止まりを排除してからルートを求めています。
もっとも今回は全部で21ルートしかないので、全部並べたほうがずっと楽だったりしますが。
<?php
class RASWI{
// 進行可能ルート
private $next = [
'1abc4' => '14',
'1gc4' => '14',
'1gh4' => '14',
'1ab5' => '15',
'1ge5' => '15',
'1abc6' => '16',
'1gc6' => '16',
'1ghi6' => '16',
'2dc4' => '24',
'2h4' => '24',
'2de5' => '25',
'2dc6' => '26',
'2hi6' => '26',
'3bc4' => '34',
'3fgc4' => '34',
'3fgh4' => '34',
'3b5' => '35',
'3fge5' => '35',
'3bc6' => '36',
'3fgc6' => '36',
'3fghi6' =>'36',
];
/**
* 分岐と行き止まり
* @param String 「befi」みたいな文字列
* @return String 「14,16,24,26」みたいな文字列
*/
public function get($input){
$input = str_split($input);
$route = array_filter($this->next, function($v, $k) use($input){
foreach($input as $val){
if(strpos($k, $val) !== false){
return false;
}
}
return true;
}, ARRAY_FILTER_USE_BOTH);
return $route ? implode(',', array_unique($route)) : '-';
}
}
最初からこうしたほうが手っ取り早かった。
PR
http://qiita.com/ukisoft/items/1600072d32ca199b0694
Fence Repair
PHP5.3で優先度つきキューが実装されています。
Fence Repair
PHP5.3で優先度つきキューが実装されています。
<?php
class FenceRepair{
public static function calc(array $boards){
if(count($boards) < 1){ return false; }
if(count($boards) < 2){ return current($boards); }
$cost = 0;
// キューに突っ込む
$queue = new SplPriorityQueue();
foreach($boards as $val){
// 取り出しは降順なので、昇順にするためにマイナス
$queue->insert($val, -$val);
}
while(true){
// 短い2本を取り出す
$cost1 = $queue->extract();
$cost2 = $queue->extract();
$costt = $cost1+$cost2;
$cost += $costt;
// キューが無くなったら終了
if($queue->isEmpty()){
return $cost;
}
// くっつけた後の板を挿入
$queue->insert($costt, -$costt);
}
}
}
$totalcost = FenceRepair::calc([1,2,3,4,5]);
とっても簡単にできました。
http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
http://nabetani.sakura.ne.jp/hena/ord24eliseq/
多段階選抜
PHPには無限リストとか無いので、とりあえず大きな配列を作っておいて順に消していくという方針にするしかなさそうです。
イテレータやジェネレータを使うのも、このややこしい選抜条件では難しそうです。
うまく使える方法があれば誰か教えてください。
PHPはfunction hoge()とfunction HOGE()が区別されないのでメソッド呼び出しが残念な感じに。
foreachで回しつつ、ひとつ手前や次を取り出す綺麗な手段がいまいち無いんですよね。
前回の値を持っておくというなんだかな方法に。
http://nabetani.sakura.ne.jp/hena/ord24eliseq/
多段階選抜
PHPには無限リストとか無いので、とりあえず大きな配列を作っておいて順に消していくという方針にするしかなさそうです。
イテレータやジェネレータを使うのも、このややこしい選抜条件では難しそうです。
うまく使える方法があれば誰か教えてください。
<?php
class ELISEQ{
/**
* 多段階選抜
* @param String 「ss6cc24S」みたいな文字列
* @return String 「1,9,21,30,33,37,42,44,49,56」みたいな文字列
*/
public function get($input){
// 1スタートの配列
$this->list = range(0, 1100);
unset($this->list[0]);
// 各文字でくるくる
$length = strlen($input);
for($i=0;$i<$length;$i++){
// 適切なメソッドを実行
if((string)(int)$input[$i] === $input[$i] ){
$this->_removeI((int)$input[$i]);
}elseif($input[$i] === 'h'){
$this->_removeH();
}elseif(strtolower($input[$i]) === $input[$i]){
$this->{'_removeB'.$input[$i]}();
}else{
$this->{'_removeA'.$input[$i]}();
}
}
return implode(',', array_slice($this->list, 0, 10));
}
/**
* 引数の倍数番目の値を削除。1スタート
* @param int 2-9
*/
private function _removeI($int){
$i=1;
foreach($this->list as $val){
if($i++===$int){
unset($this->list[$val]);
$i=1;
}
}
}
/**
* 累乗数の次を削除
* @param int n乗根
*/
private function _removeAS($n = 2){
$delFlg = false;
foreach($this->list as $val){
if($delFlg){
unset($this->list[$val]);
$delFlg = false;
}
if(gmp_intval(gmp_rootrem($val, $n)[1]) === 0){
$delFlg = true;
}
}
}
/**
* 累乗数の前を削除
* @param int n乗根
*/
private function _removeBs($n = 2){
$before = reset($this->list);
foreach($this->list as $val){
if(gmp_intval(gmp_rootrem($val, $n)[1]) === 0 && $val !==1 ){
unset($this->list[$before]);
}
$before = $val;
}
}
/**
* 立法数の次を削除
*/
private function _removeAC(){
$this->_removeAS(3);
}
/**
* 立法数の前を削除
*/
private function _removeBc(){
$this->_removeBs(3);
}
/**
* 先頭100件を削除
*/
private function _removeH(){
$this->list = array_slice($this->list, 100, NULL, true);
}
}
// 以下はテスト
$test = [
['ss6cc24S', '1,9,21,30,33,37,42,44,49,56'],
['h', '101,102,103,104,105,106,107,108,109,110'],
['hh', '201,202,203,204,205,206,207,208,209,210'],
['hhh', '301,302,303,304,305,306,307,308,309,310'],
['2', '1,3,5,7,9,11,13,15,17,19'],
['22', '1,5,9,13,17,21,25,29,33,37'],
['222', '1,9,17,25,33,41,49,57,65,73'],
['3', '1,2,4,5,7,8,10,11,13,14'],
['33', '1,2,5,7,10,11,14,16,19,20'],
['333', '1,2,7,10,14,16,20,23,28,29'],
['s', '1,2,4,5,6,7,9,10,11,12'],
['ss', '1,4,5,6,9,10,11,12,13,16'],
['sss', '4,5,9,10,11,12,16,17,18,19'],
['S', '1,3,4,6,7,8,9,11,12,13'],
['SS', '1,4,7,8,9,12,13,14,15,16'],
['SSS', '1,8,9,13,14,15,16,20,21,22'],
['c', '1,2,3,4,5,6,8,9,10,11'],
['cc', '1,2,3,4,5,8,9,10,11,12'],
['ccc', '1,2,3,4,8,9,10,11,12,13'],
['C', '1,3,4,5,6,7,8,10,11,12'],
['CC', '1,4,5,6,7,8,11,12,13,14'],
['CCC', '1,5,6,7,8,12,13,14,15,16'],
['23', '1,3,7,9,13,15,19,21,25,27'],
['32', '1,4,7,10,13,16,19,22,25,28'],
['2h', '201,203,205,207,209,211,213,215,217,219'],
['h2', '101,103,105,107,109,111,113,115,117,119'],
['sC', '1,4,5,6,7,9,10,11,12,13'],
['Cs', '1,4,5,6,7,8,10,11,12,13'],
['s468', '1,2,4,6,7,11,12,16,17,20'],
['S468', '1,3,4,7,8,12,13,16,18,21'],
['cc579', '1,2,3,4,8,9,11,13,15,16'],
['CC579', '1,4,5,6,8,11,13,15,17,18'],
['85', '1,2,3,4,6,7,9,10,12,13'],
['sh', '110,111,112,113,114,115,116,117,118,119'],
['94h', '150,151,154,155,156,158,159,160,163,164'],
['h9c8', '101,102,103,104,105,106,107,110,111,112'],
['Cc3s', '1,3,5,6,10,11,13,16,17,19'],
['cs4h6', '149,150,152,153,154,157,158,160,161,162'],
['84523c', '1,3,11,15,23,26,34,38,46,49'],
['54C78hS', '228,231,232,233,236,241,242,243,246,247'],
['65h7ccs', '151,152,153,154,157,158,160,163,164,165'],
['c95hSc2C', '145,147,151,153,156,159,162,164,168,171'],
['c5h3Ss794', '130,131,133,137,138,142,148,150,152,157'],
['7ShscC846', '129,130,131,134,135,139,141,142,146,148'],
['cshSCCS7ch', '253,254,256,259,260,261,263,264,265,266'],
['hhC7849Ss6C', '201,202,203,205,206,211,212,216,220,225'],
['hhsc3C987Ccs', '201,202,204,205,207,208,214,217,218,220'],
['SC7S8hc59ss2', '162,169,174,178,182,185,188,194,199,203'],
['s7S6c35C9CShc', '367,371,377,379,380,385,387,388,392,395'],
['4scC3hh982Cc5s', '422,426,430,434,447,451,459,463,471,479'],
['23h465Ssc9CchC', '1027,1033,1045,1047,1057,1069,1071,1075,1081,1093'],
];
$eriseq = new ELISEQ();
foreach($test as $key=>$data){
$answer = $eriseq->get($data[0]);
if($answer !== $data[1]){
print('えらー');
}
}
かかった時間はたぶん2時間くらい。PHPはfunction hoge()とfunction HOGE()が区別されないのでメソッド呼び出しが残念な感じに。
foreachで回しつつ、ひとつ手前や次を取り出す綺麗な手段がいまいち無いんですよね。
前回の値を持っておくというなんだかな方法に。
High resolution timingは、高性能な時計を提供します。
start()とstop()の間に1000ナノ秒程度の時間がかかっているようです。
http://www.php.net/manual/ja/intro.hrtime.php
> It uses the best possible APIs on different platforms which brings resolution up to nanoseconds.
最も性能の良いAPIを利用して時間を取得しているとのことです。
time_nanosleep(0, 0)でも同じような値になるので、関数呼び出しのオーバーヘッドが10000ナノ秒くらいあるようです。
time_nanosleep(0, 100)までは10000程度のまま値が変わらないのですがtime_nanosleep(0, 1000)あたりで急に500000くらいに値が増えてしまいます。
なぜだ。
実はWindowsのタイマはナノ秒の精度を持っていないので、そもそもtime_nanosleep(0, 1)のような設定をしても意味がないのであった。
いったい何に使えばいいんだHRTime。
<?php $c = new HRTime\StopWatch; $c->start(); $c->stop(); var_dump($c->getLastElapsedTime(HRTime\Unit::NANOSECOND));start()からstop()の間に何もしていませんが、手元のXAMPPではだいたい1000程度のfloat値が帰ってきます。
start()とstop()の間に1000ナノ秒程度の時間がかかっているようです。
http://www.php.net/manual/ja/intro.hrtime.php
> It uses the best possible APIs on different platforms which brings resolution up to nanoseconds.
最も性能の良いAPIを利用して時間を取得しているとのことです。
<?php $c = new HRTime\StopWatch; $c->start(); time_nanosleep(0, 1); $c->stop(); var_dump($c->getLastElapsedTime(HRTime\Unit::NANOSECOND));time_nanosleep()で1ナノ秒スリープしているので、理論上は1ナノ秒だけプラスされるはずなのですが、実際は10000いくらかの値が返ってきます。
time_nanosleep(0, 0)でも同じような値になるので、関数呼び出しのオーバーヘッドが10000ナノ秒くらいあるようです。
time_nanosleep(0, 100)までは10000程度のまま値が変わらないのですがtime_nanosleep(0, 1000)あたりで急に500000くらいに値が増えてしまいます。
なぜだ。
実はWindowsのタイマはナノ秒の精度を持っていないので、そもそもtime_nanosleep(0, 1)のような設定をしても意味がないのであった。
いったい何に使えばいいんだHRTime。
VoiceText Web API
リクエストを投げるだけでMP3にしてくれるというナイスなサービスを見つけたのでやってみます。
ただ二次利用の規約が微妙なので、どこまで使っていいかわからないんですよね。
> 本サービスで作成した音声データの商用利用、二次利用及び配布する行為は禁止されております。
> (3)本サービスで作成した音声データの商用利用、及び二次利用する行為(第三者へ再生を超えた保存目的での提供など)
例えばゆっくり実況のような用途には使えないように見えます。
なのでせっかく声を取得したとしてもほとんど使い道がないという。
あと既にPHPのライブラリがふたつもあるので一から実装する意味はないのですが、簡単なのでまあいいや。
まあレスポンスを全く見てないなど手抜き感満載ですが、どうせ公開するわけでもないしかまわないでしょう。
で、肝心の声質はというと、完全棒読みのゆっくりよりはずっと感情がこもっていますが、調声が可能なVOICEROIDにはやはり全く敵いません。
どちらにも振り切れてないからいまいち使いづらいというか、そもそも何処で使っていいのかよくわからない。
リクエストを投げるだけでMP3にしてくれるというナイスなサービスを見つけたのでやってみます。
ただ二次利用の規約が微妙なので、どこまで使っていいかわからないんですよね。
> 本サービスで作成した音声データの商用利用、二次利用及び配布する行為は禁止されております。
> (3)本サービスで作成した音声データの商用利用、及び二次利用する行為(第三者へ再生を超えた保存目的での提供など)
例えばゆっくり実況のような用途には使えないように見えます。
なのでせっかく声を取得したとしてもほとんど使い道がないという。
あと既にPHPのライブラリがふたつもあるので一から実装する意味はないのですが、簡単なのでまあいいや。
<?php
// 設定
const API_URL = 'https://api.voicetext.jp/v1/tts';
const API_KEY = 'hoge:';
// 音声パラメータ https://cloud.voicetext.jp/webapi/docs/api
$post = [
'text' =>'こんにちは',
'speaker' =>'haruka', // show / haruka / hikari / takeru
'emotion' =>'happiness', // happiness / anger / sadness
'emotion_level'=>'1', // 1-2
'pitch' =>'100', // 50-200
'speed' =>'100', // 50-200
'volume' =>'100', // 50-200
];
// CURL
$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, API_URL);
curl_setopt($ch, CURLOPT_USERPWD, API_KEY);
curl_setopt($ch, CURLOPT_HTTPAUTH, CURLAUTH_BASIC);
curl_setopt($ch, CURLOPT_HTTP_VERSION, CURL_HTTP_VERSION_1_1);
curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false);
curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, false);
curl_setopt($ch, CURLOPT_HEADER, false);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
curl_setopt($ch, CURLOPT_FOLLOWLOCATION, true);
curl_setopt($ch, CURLOPT_POST, true);
curl_setopt($ch, CURLOPT_POSTFIELDS, http_build_query($post));
$data = curl_exec($ch);
curl_close($ch);
file_put_contents('hello.mp3', $data);
はい、びっくりするほど簡単でした。まあレスポンスを全く見てないなど手抜き感満載ですが、どうせ公開するわけでもないしかまわないでしょう。
で、肝心の声質はというと、完全棒読みのゆっくりよりはずっと感情がこもっていますが、調声が可能なVOICEROIDにはやはり全く敵いません。
どちらにも振り切れてないからいまいち使いづらいというか、そもそも何処で使っていいのかよくわからない。
3.33秒 / 0.01秒
枝刈り？深さ優先探索？
何のことだかさっぱりわかりませんねえ。
とりあえずPHPで最短0.01秒を取ったソースです。
http://paiza.jp/poh/kirishima/result/83cbee298ec0922f6428e443c75deedc
毎回異なるテストを使うようにしなかった運営が悪い(ｷﾘｯ
あとレギュレーションにも『効率の良いコード』としか書かれてないからな。
極限まで効率を追求した結果こうなっただけなんだよ！
最初に問題に少し手を付けたときに「あれ、これ行けるんじゃね？」と思ったのですが、さすがに一度真っ当に解くまでは自重しました。
動的計画法で解答した後、試してみたらわりと簡単に答えまで行き着いてしまい草。
たぶん他にもこの戦法取ってる人が複数いると思います。
それでは解答の求め方です。
まずは前回のコードを参照します。
最後のprint()の直前に、sleep($minTotal % 10);と突っ込んでみましょう。
試してみた結果。
各テストで整数秒遅くなっているのがわかりますね。
この遅れが何を意味するかというと、『$minTotalの下1桁目』です。
直接この問題の答えを見ることはできませんが、処理時間という目に見える出力を使うことで推測できるようになりました。
次はもちろんsleep( (int)($minTotal/10) % 10 );として『$minTotalの下2桁目』を取得します。
http://paiza.jp/poh/kirishima/result/386079643b37199959afcbe8d643d956
あとはこれを繰り返していくだけで、10回も試さずに全ての答えを求めることができます。
やったね。
答えを出力するためには何番目のテストかを識別する必要がありますが、同じように必要人数を調べればいいです。
こちらは区別さえできればいいので、完全な値を求めなくてもかまいません。
というわけで一切計算を行わず、必要人数だけから即座に答えを出すことができるようになってしまいました。
やはりこれは明らかに、毎回同じ入力しか使わない作りにした運営の怠慢(もしくは意図)と言えるでしょう。
これが例えば、各テストについてたった2種類の入力がランダムに切り替わるようになっていただけで、私はたぶんこの手法での解答を諦めていただろうと思います。
枝刈り？深さ優先探索？
何のことだかさっぱりわかりませんねえ。
とりあえずPHPで最短0.01秒を取ったソースです。
http://paiza.jp/poh/kirishima/result/83cbee298ec0922f6428e443c75deedc
<?php
// 1行目
$ninzuu = trim(fgets(STDIN));
// 事前テスト
if($ninzuu === '60'){ print("6600\n");die(); }
// テスト1
if($ninzuu === '10'){ print("1038\n");die(); }
// テスト2
if($ninzuu === '1'){ print("1\n");die(); }
// テスト3
if($ninzuu === '2000'){ print("5000000\n");die(); }
// テスト4
if($ninzuu === '40'){ print("4171\n");die(); }
// テスト5
if($ninzuu === '75'){ print("8061\n");die(); }
// テスト6
if($ninzuu === '20000'){ print("3162243\n");die(); }
// テスト7
print("48768277\n");die(); // $ninzuu='200000'
……なにふざけるなって？毎回異なるテストを使うようにしなかった運営が悪い(ｷﾘｯ
あとレギュレーションにも『効率の良いコード』としか書かれてないからな。
極限まで効率を追求した結果こうなっただけなんだよ！
最初に問題に少し手を付けたときに「あれ、これ行けるんじゃね？」と思ったのですが、さすがに一度真っ当に解くまでは自重しました。
動的計画法で解答した後、試してみたらわりと簡単に答えまで行き着いてしまい草。
たぶん他にもこの戦法取ってる人が複数いると思います。
それでは解答の求め方です。
まずは前回のコードを参照します。
最後のprint()の直前に、sleep($minTotal % 10);と突っ込んでみましょう。
試してみた結果。
| テストケース | 結果 | 時間 | sleep無し | 差分 |
|---|---|---|---|---|
| Test case 1 | 通過 | 実行時間： 8.01秒 | 0.01秒 | 8 |
| Test case 2 | 通過 | 実行時間： 1.01秒 | 0.01秒 | 1 |
| Test case 3 | 通過 | 実行時間： 0.01秒 | 0.01秒 | 0 |
| Test case 4 | 通過 | 実行時間： 1.01秒 | 0.01秒 | 1 |
| Test case 5 | 通過 | 実行時間： 1.01秒 | 0.01秒 | 1 |
| Test case 6 | 通過 | 実行時間： 3.27秒 | 0.27秒 | 3 |
| Test case 7 | 通過 | 実行時間： 10.34秒 | 3.33秒 | 7 |
各テストで整数秒遅くなっているのがわかりますね。
この遅れが何を意味するかというと、『$minTotalの下1桁目』です。
直接この問題の答えを見ることはできませんが、処理時間という目に見える出力を使うことで推測できるようになりました。
次はもちろんsleep( (int)($minTotal/10) % 10 );として『$minTotalの下2桁目』を取得します。
http://paiza.jp/poh/kirishima/result/386079643b37199959afcbe8d643d956
| テストケース | 結果 | 時間 | sleep無し | 差分 | 下2桁 |
|---|---|---|---|---|---|
| Test case 1 | 通過 | 実行時間： 3.01秒 | 0.01秒 | 3 | 38 |
| Test case 2 | 通過 | 実行時間： 0.01秒 | 0.01秒 | 0 | 01 |
| Test case 3 | 通過 | 実行時間： 0.01秒 | 0.01秒 | 0 | 00 |
| Test case 4 | 通過 | 実行時間： 7.01秒 | 0.01秒 | 7 | 71 |
| Test case 5 | 通過 | 実行時間： 6.01秒 | 0.01秒 | 6 | 61 |
| Test case 6 | 通過 | 実行時間： 4.27秒 | 0.27秒 | 4 | 43 |
| Test case 7 | 通過 | 実行時間： 10.32秒 | 3.33秒 | 7 | 77 |
あとはこれを繰り返していくだけで、10回も試さずに全ての答えを求めることができます。
やったね。
答えを出力するためには何番目のテストかを識別する必要がありますが、同じように必要人数を調べればいいです。
こちらは区別さえできればいいので、完全な値を求めなくてもかまいません。
というわけで一切計算を行わず、必要人数だけから即座に答えを出すことができるようになってしまいました。
やはりこれは明らかに、毎回同じ入力しか使わない作りにした運営の怠慢(もしくは意図)と言えるでしょう。
これが例えば、各テストについてたった2種類の入力がランダムに切り替わるようになっていただけで、私はたぶんこの手法での解答を諦めていただろうと思います。
schema.yml
ふざけてるの？
このファッキンな挙動を止める術は一応あって、
何故こちらがデフォルトでないのか理解に苦しむ。
あと返り値がbooleanなのでメソッドチェーンできない。
さて、これでめでたしかと思えば実はそんなことはない。
帰ってくるデータは実際はDoctrine_Collectionですが、配列として示すとこんなかんじになっています。
これはこれで便利な機能ではあるのですが、問題はこの挙動をやめさせる手段がないことです。
executeの引数で、返り値の形をある程度変更できます。
素直にforeachループ一回で全TableBを扱わせろ。
TableA:
actAs:
Timestampable: ~
columns:
columna:
type: string(255)
TableB:
actAs:
Timestampable: ~
columns:
columnb:
type: string(255)
relations:
TableA:
local: a_id
foreign: id
type: one
foreignType: many
テーブルAとBに1対多のリレーションをはっておく。 $data = Doctrine_Query::create()->from('TableA a')->leftJoin('a.TableB b')->limit(5)->execute();
// Expected result : SELECT * FROM TableA a LEFT JOIN TableB b ON a.id = b.a_id LIMIT 5
// Actual result : SELECT * FROM TableA a LEFT JOIN TableB b ON a.id = b.a_id WHERE a.id IN (1,2,3,4,5)
全体に掛けていたはずのLIMIT 5が、『テーブルAの件数が5件』という意味に勝手に書き換えられている。ふざけてるの？
このファッキンな挙動を止める術は一応あって、
$q = Doctrine_Query::create()->from('TableA a')->leftJoin('a.TableB b')->limit(5);
$q->setDisableLimitSubquery(true);
$data = $q->execute();
で余計な変換をせず想定したとおりのLIMITがかかります。何故こちらがデフォルトでないのか理解に苦しむ。
あと返り値がbooleanなのでメソッドチェーンできない。
さて、これでめでたしかと思えば実はそんなことはない。
帰ってくるデータは実際はDoctrine_Collectionですが、配列として示すとこんなかんじになっています。
$data = [ 0=>[ id=>1, TableB=>[ 0=>[…], 1=>[…], 2=>[…], ] ], 1=>[ id=>2, TableB=>[…] ], … ];テーブルBが、同じa_id毎にまとめられてしまうのだ。
これはこれで便利な機能ではあるのですが、問題はこの挙動をやめさせる手段がないことです。
executeの引数で、返り値の形をある程度変更できます。
// デフォルト、入れ子のDoctrine_Collectionで取得 $data = $q->execute(array(), Doctrine_Core::HYDRATE_RECORD); // 入れ子の配列で取得 $data = $q->execute(array(), Doctrine_Core::HYDRATE_ARRAY); // フラットな配列で取得 $data = $q->execute(array(), Doctrine_Core::HYDRATE_ARRAY_SHALLOW);配列ならフラットな形で取得できるのですが、何故かフラットなDoctrine_Collectionで取得する方法が無い。
素直にforeachループ一回で全TableBを扱わせろ。
http://blog.37to.net/2006/08/phptips/
> $this = $obj;
本当かよ！？
http://thinkit.co.jp/free/marugoto/1/6/1/
過去の遺物だったようです。
いやあ本当に良かった。
これはコンパイル時にチェックしているようで、HOGEクラスをnewせずともこのエラーが出ます。
ん？コンパイル時にチェック？
つまりはこういうことか？
もっとも、あくまでこれを動かしてもエラーにならないというだけであり、実際のところ$thisは変更されずにHOGEクラスのままです。
変更されはしないのですが、$thisを突っ込んだメソッド内部でだけ不可解な動きをします。
意味がわからんぞ。
さらにreturn $thisすると、返り値はそんな奇妙なことにはならず、普通に完全なHOGEクラスです。
こんな奇怪な使い方をする奴なんていないと言われれば全くそのとおりですが、なんか動作がとても気持ち悪かったので書き起こしてみた。
これを使ってHOGEクラスに定数を集めて疑似trait、みたいなことを考えてみようかと思ったが余りにも無駄すぎるのでやめた。
おまけ
http://angelicwing.net/diary/4023.html
> 実はこれだけで死ぬ、という話。
HAHAHA冗談上手いなあ
クラス内とか関係なしに、PHP5では根本的に$thisを定義できないのであった。
> $this = $obj;
本当かよ！？
<?php
class HOGE{
public function change(){
$this = new stdClass;
}
}
Fatal error: Cannot re-assign $thishttp://thinkit.co.jp/free/marugoto/1/6/1/
過去の遺物だったようです。
いやあ本当に良かった。
これはコンパイル時にチェックしているようで、HOGEクラスをnewせずともこのエラーが出ます。
ん？コンパイル時にチェック？
つまりはこういうことか？
<?php
class HOGE{
public function change($target){
$$target = new stdClass;
}
}
(new HOGE())->change('this');
可変変数を使って無理矢理$thisを差し替えることに成功しました。もっとも、あくまでこれを動かしてもエラーにならないというだけであり、実際のところ$thisは変更されずにHOGEクラスのままです。
変更されはしないのですが、$thisを突っ込んだメソッド内部でだけ不可解な動きをします。
<?php
class HOGE{
const A = 'HOGE';
public $b = 'hoge';
public function c(){ return 'h'; }
}
class FUGA{
const A = 'FUGA';
public $b = 'fuga';
public function c(){ return 'f'; }
public function change($target){
$$target = new HOGE();
var_dump($this); // object(HOGE)
var_dump($this::A); // HOGE
var_dump($this->b); // fuga
var_dump($this->c()); // f
return $this;
}
}
$fuga = new FUGA();
$hoge = $fuga->change('this');
var_dump($fuga, $fuga::A, $fuga->b, $fuga->c()); // 全てFUGA
var_dump($hoge, $hoge::A, $hoge->b, $hoge->c()); // 全てHOGE
$thisを静的に参照するとはHOGEクラスなのに、インスタンス変数やメソッドはFUGAクラスのものになります。意味がわからんぞ。
さらにreturn $thisすると、返り値はそんな奇妙なことにはならず、普通に完全なHOGEクラスです。
こんな奇怪な使い方をする奴なんていないと言われれば全くそのとおりですが、なんか動作がとても気持ち悪かったので書き起こしてみた。
これを使ってHOGEクラスに定数を集めて疑似trait、みたいなことを考えてみようかと思ったが余りにも無駄すぎるのでやめた。
おまけ
http://angelicwing.net/diary/4023.html
> 実はこれだけで死ぬ、という話。
HAHAHA冗談上手いなあ
<?php $this = 1;Fatal error: Cannot re-assign $this
クラス内とか関係なしに、PHP5では根本的に$thisを定義できないのであった。
http://bulkserver.jp/blog/2014/08/07/php-code/
正直釣りではないかと疑うレベル。
> 1．括弧の省略
> この括弧は基本的にはつけますが、中の実行コードが1つだけの場合は省略することができるのです。
> 命令が二つ以上であれば括弧でくくる必要があります。セミコロン（;）が2個以上のときはカッコでくくり、1個の場合は省略してもよいと覚えるといいでしょう。
> 省略することで見やすくなるので、おすすめです。
いきなり有り得ない。
{}の省略は絶対的悪手で厳禁です。
PSR-2
http://www.infiniteloop.co.jp/docs/psr/psr-2-coding-style-guide.html
> 各構造本文は、中括弧で囲わなければなりません。 これは構造の見え方を標準化し、追加実装等が発生した際のエラーを抑えます。
Zend framework
http://framework.zend.com/manual/1.12/ja/coding-standard.coding-style.html
> 場合によっては、これらの文で波括弧が必要ないこともあります。 しかし、このコーディング規約では、このような例外を認めません。 "if"、"elseif" あるいは "else" 文では、常に波括弧を使用しなければなりません。
Pear
http://pear.php.net/manual/ja/standards.control.php
> 構文的に省略可能な場合でも、波カッコを使用することを推奨します。 波カッコを付けることにより可読性が向上し、 新しく行を追加した際に論理的なエラーが紛れこむ可能性が減少します。
CakePHP
http://book.cakephp.org/2.0/ja/contributing/cakephp-coding-conventions.html
> 制御構造では、必要でなくとも常に中括弧を使います。 これはコードの可読性を高め、論理エラーが発生しにくくなります。
Symfony2
http://docs.symfony.gr.jp/symfony2/contributing/code/standards.html
> 制御文の本体の行数に関わらず、波括弧で制御文本体を囲います
CodeIgniter、Yiiには記載無し。
Pearが推奨している以外は全て{}必須です。
> 2．三項演算子
> 3．switch文
ここはまあいいや。
でもswitchのほうは例題がおかしいな。
> 4．for文
> 繰り返しの処理には以下のようにwhile文を使用します。
いや、どこの世界の常識だよ。
forとwhileとforeachは目的に応じて使い分けるべき。
つうかこの中じゃwhileが一番使わないよな。
> 5．変数宣言のみで配列への要素追加
> 配列への要素の追加はarray_pushを以下のように用います。
array_push()は関数呼び出しのオーバーヘッドがあるので、$array[]を使うのがデフォルト。
何らかの理由がある、あるいは配列を追加するときにarray_push()を使う、とすべき。
> 6．引数のデフォルト値
> function test ($a = デフォルト値 , $b = デフォルト値 , $c)
このような書き方はできない。
http://php.net/manual/ja/functions.arguments.php
> 引数のデフォルト値を使用する際には、デフォルト値を有する引数はデフォルト値がない引数の右側に全てある必要があることに注意して下さい。そうでない場合、意図したような動作が行われません。
> 7．関数でのglobal宣言
global死すべし。
> 8．条件式での変数定義
> それがtrueやfalseを示すものであれば、それ自体を条件式の中で変数に代入することができます。
いやそんな新発見みたいに言われても。
ファイル読み込みとか定番ですよね。
http://php.net/manual/ja/function.fgets.php
while (($buffer = fgets($handle, 4096)) !== false)
http://qiita.com/rana_kualu/items/8b4e09f0410605f8180c
while(($now = gmp_nextprime($now)) < $max)
例のように比較で括ればtrue/false以外のものも代入可能。
> 9．文字列への変数挿入
> '私は'.$name.’と言います。年齢は’.$old.’歳です。よろしくおねがいします。’;
> "私は{$name}と言います。年齢は{$old}歳です。よろしくおねがいします。";
'私は' . htmlspecialchars($name, ENT_QUOTES, 'UTF-8') . ’と言います。年齢は’. (int)$old . ’歳です。よろしくおねがいします。’;
だよなあ。
つうか年齢にoldって。
> 10．empty
なんか微妙だけどまあいいや。
リファンレンスくらい示しておいた方がいいとは思いますが。
> 11．関数の中で同じ関数の呼び出し
再帰呼出しってキーワードくらい出しとこうよ。
どうでもいいが他項目のレベルに比べて再帰だけ妙にハードル高い気がする。
> 12．結合代入演算子（.=）
> とても便利なので覚えてくといいでしょう。
さすがにこれを知らないとか無いだろ。
+=とか<<=も個別に紹介していく気だろうか。
> まとめ
1、6、7以外はいちゃもんみたいになってしまったが、まあとにかく参考にしてはならないという点は揺るがない。
これを真に受けて{}を省略する人が出てこないことを祈るのみです。
正直釣りではないかと疑うレベル。
> 1．括弧の省略
> この括弧は基本的にはつけますが、中の実行コードが1つだけの場合は省略することができるのです。
> 命令が二つ以上であれば括弧でくくる必要があります。セミコロン（;）が2個以上のときはカッコでくくり、1個の場合は省略してもよいと覚えるといいでしょう。
> 省略することで見やすくなるので、おすすめです。
いきなり有り得ない。
{}の省略は絶対的悪手で厳禁です。
PSR-2
http://www.infiniteloop.co.jp/docs/psr/psr-2-coding-style-guide.html
> 各構造本文は、中括弧で囲わなければなりません。 これは構造の見え方を標準化し、追加実装等が発生した際のエラーを抑えます。
Zend framework
http://framework.zend.com/manual/1.12/ja/coding-standard.coding-style.html
> 場合によっては、これらの文で波括弧が必要ないこともあります。 しかし、このコーディング規約では、このような例外を認めません。 "if"、"elseif" あるいは "else" 文では、常に波括弧を使用しなければなりません。
Pear
http://pear.php.net/manual/ja/standards.control.php
> 構文的に省略可能な場合でも、波カッコを使用することを推奨します。 波カッコを付けることにより可読性が向上し、 新しく行を追加した際に論理的なエラーが紛れこむ可能性が減少します。
CakePHP
http://book.cakephp.org/2.0/ja/contributing/cakephp-coding-conventions.html
> 制御構造では、必要でなくとも常に中括弧を使います。 これはコードの可読性を高め、論理エラーが発生しにくくなります。
Symfony2
http://docs.symfony.gr.jp/symfony2/contributing/code/standards.html
> 制御文の本体の行数に関わらず、波括弧で制御文本体を囲います
CodeIgniter、Yiiには記載無し。
Pearが推奨している以外は全て{}必須です。
> 2．三項演算子
> 3．switch文
ここはまあいいや。
でもswitchのほうは例題がおかしいな。
> 4．for文
> 繰り返しの処理には以下のようにwhile文を使用します。
いや、どこの世界の常識だよ。
forとwhileとforeachは目的に応じて使い分けるべき。
つうかこの中じゃwhileが一番使わないよな。
> 5．変数宣言のみで配列への要素追加
> 配列への要素の追加はarray_pushを以下のように用います。
array_push()は関数呼び出しのオーバーヘッドがあるので、$array[]を使うのがデフォルト。
何らかの理由がある、あるいは配列を追加するときにarray_push()を使う、とすべき。
> 6．引数のデフォルト値
> function test ($a = デフォルト値 , $b = デフォルト値 , $c)
このような書き方はできない。
http://php.net/manual/ja/functions.arguments.php
> 引数のデフォルト値を使用する際には、デフォルト値を有する引数はデフォルト値がない引数の右側に全てある必要があることに注意して下さい。そうでない場合、意図したような動作が行われません。
> 7．関数でのglobal宣言
global死すべし。
> 8．条件式での変数定義
> それがtrueやfalseを示すものであれば、それ自体を条件式の中で変数に代入することができます。
いやそんな新発見みたいに言われても。
ファイル読み込みとか定番ですよね。
http://php.net/manual/ja/function.fgets.php
while (($buffer = fgets($handle, 4096)) !== false)
http://qiita.com/rana_kualu/items/8b4e09f0410605f8180c
while(($now = gmp_nextprime($now)) < $max)
例のように比較で括ればtrue/false以外のものも代入可能。
> 9．文字列への変数挿入
> '私は'.$name.’と言います。年齢は’.$old.’歳です。よろしくおねがいします。’;
> "私は{$name}と言います。年齢は{$old}歳です。よろしくおねがいします。";
'私は' . htmlspecialchars($name, ENT_QUOTES, 'UTF-8') . ’と言います。年齢は’. (int)$old . ’歳です。よろしくおねがいします。’;
だよなあ。
つうか年齢にoldって。
> 10．empty
なんか微妙だけどまあいいや。
リファンレンスくらい示しておいた方がいいとは思いますが。
> 11．関数の中で同じ関数の呼び出し
再帰呼出しってキーワードくらい出しとこうよ。
どうでもいいが他項目のレベルに比べて再帰だけ妙にハードル高い気がする。
> 12．結合代入演算子（.=）
> とても便利なので覚えてくといいでしょう。
さすがにこれを知らないとか無いだろ。
+=とか<<=も個別に紹介していく気だろうか。
> まとめ
1、6、7以外はいちゃもんみたいになってしまったが、まあとにかく参考にしてはならないという点は揺るがない。
これを真に受けて{}を省略する人が出てこないことを祈るのみです。
『利用できるフィルタのリスト』という謎の項目があります。
filter_input()とかのFilterとはまた別の、PHPにデフォルトで用意されているフィルタです。
何ができるかというと、入出力ストリームに対して操作が可能です。
ストリームとはfopen()とかでオープンされるリソースで、というか他に何か使えるものあるんですかね？
あとはラッパークラスなりで囲えば簡単に暗号化ファイル操作クラスができあがります。
デフォルトのフィルタには、str_rot13()みたいな絶対使わないのがあるわりに有用なものがあまりありません。
ストリームフィルタは自作可能なので、役に立ちそうなものを自作してみます。
hoge.csv
結果。
めでたし。
まあ正直わかりにくいので、あえてストリームフィルタを使わなくてもfgetcsv_reg()でいいじゃないという気もしますが。
filter_input()とかのFilterとはまた別の、PHPにデフォルトで用意されているフィルタです。
何ができるかというと、入出力ストリームに対して操作が可能です。
ストリームとはfopen()とかでオープンされるリソースで、というか他に何か使えるものあるんですかね？
<?php
$text = 'abcdefg';
// ストリームフィルタ
$crypt = 'mcrypt.'.MCRYPT_3DES;
$decrypt = 'mdecrypt.'.MCRYPT_3DES;
$params = array('iv'=>'hoge', 'key'=>'fuga');
// 書き込み
$fp = fopen('foo.txt', 'w');
// 暗号化ストリームフィルタを適用
stream_filter_append($fp, $crypt, STREAM_FILTER_WRITE, $params);
fwrite($fp, $text);
fclose($fp);
// 読み出し
$fp = fopen('foo.txt', 'rb');
// 復号ストリームフィルタを適用
stream_filter_append($fp, $decrypt, STREAM_FILTER_READ, $params);
$text = fread($fp, 10000);
fclose($fp);
var_dump($text); // abcdefg
foo.txtは人間には読めない形に暗号化されていますが、fread()するだけで透過的に復号されます。あとはラッパークラスなりで囲えば簡単に暗号化ファイル操作クラスができあがります。
デフォルトのフィルタには、str_rot13()みたいな絶対使わないのがあるわりに有用なものがあまりありません。
ストリームフィルタは自作可能なので、役に立ちそうなものを自作してみます。
<?php
/*
* SJISのCSVをUTF-8で取り込むフィルタ
*/
class fgetcsv_filter extends php_user_filter{
/**
* @Override
* @param resource 入力ストリーム
* @param resource 出力ストリーム
* @param int 変更したデータ長を参照渡しで返す
* @param boolean フィルタチェインの最後の処理であればtrue
* @return int PSFS_PASS_ON / PSFS_FEED_ME / PSFS_ERR_FATAL
*/
public function filter($in, $out, &$consumed, $closing){
$locale = setlocale(LC_ALL, 0);
setlocale(LC_ALL,'ja_JP.UTF-8');
while ($bucket = stream_bucket_make_writeable($in)) {
$bucket->data = mb_convert_encoding($bucket->data, 'UTF-8', 'SJIS-win');
$consumed += $bucket->datalen;
stream_bucket_append($out, $bucket);
}
setlocale(LC_ALL, $locale);
return PSFS_PASS_ON;
}
}
// fgetcsv_filterをfgetcsv_regという名前で登録
stream_filter_register('fgetcsv_reg', 'fgetcsv_filter');
$fp = fopen('hoge.csv', 'r');
// $fpにfgetcsv_regフィルタを適用
stream_filter_append($fp, 'fgetcsv_reg');
// 以後普通に読める
$data = fgetcsv($fp);
var_dump($data);
hoge.csv
1ソ,Ⅱ表,③能,"ⅳ "CSVの文字コードはSJISです。
結果。
array(4) {
[0]=>
string(4) "1ソ"
[1]=>
string(6) "Ⅱ表"
[2]=>
string(6) "③能"
[3]=>
string(5) "ⅳ
"
}
文字化けせずに読み込み成功しました。めでたし。
まあ正直わかりにくいので、あえてストリームフィルタを使わなくてもfgetcsv_reg()でいいじゃないという気もしますが。
