2013/01/10

[競技プログラミング][PHP][AtCoder]超大型連休

B - 超大型連休

時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB

問題文

2011 年、AtCoder 国の高橋首相はある重大な決定を行った。
その決定とは...法改正である。国民の祝日に関する法律を変更し、休日を増やすことにした!!
国民の創造性を尊重するその決定が、霞が関を魔境へと変えたッ!

あなたは霞が関の国土交通省に勤務する職員であり、この法改正により上司から新たな任務を与えられた。
その任務とは、2012 年の「連休の最大日数」を計算することである。
連休の大きさを事前に計算することで国民の行動を予想し、
高速道路の部分的な値下げを行い、経済を活性させるためだ。
したがって、あなたに失敗することは許されない。国民の行動を正確に予想できなくなるからだ。

以下に、「連休」の定義と諸注意を記す。
AtCoder 国が使用する暦はグレゴリオ暦に従う。
「連休」とは、「休日」が連続して続くことである。
「土曜日」「日曜日」「祝日」「振替休日」が「休日」に相当する。
「祝日」が他の休日と同じ日に指定されていた場合、「振替休日」を必ず設置する。
「振替休日」は祝日の時系列順に決定していき、その祝日以降最も近い平日(休日を除いた日)となる。
2012 年 1 月 1 日は日曜日である。

入力

入力は以下の形式で標準入力から与えられる。
N
m1/d1
m2/d2
:
:
mn/dn
1 行目には祝日の日数を表す整数 N が与えられ、 0≦N≦366 を満たす。
2 行目から N+1 行目までの N 行で祝日の日付が与えられる。
mi は i(1≦i≦366) 番目に与えられる祝日の月で、 1≦mi≦12 を満たす。
di は i(1≦i≦366) 番目に与えられる祝日の日で、
mi=2 のとき、 1≦di≦29 を満たす。
mi=(4,6,9,11) のとき、 1≦di≦30 を満たす。
mi=(1,3,5,7,8,10,12) のとき、 1≦di≦31 を満たす。
mi と di はともに整数である。
mi と di は必ず/で区切られて与えられる。
祝日は時系列順に与えられるとは限らないことに注意せよ。
ただし、同じ日付が複数与えられないことは保証されている。

出力

法改正後における 2012 年の連休の最大日数を出力せよ。
出力は標準出力におこない、末尾には改行をいれること。

出典

B: 超大型連休 - AtCoder Regular Contest #010 | AtCoder

回答

Submission #65857 - AtCoder Regular Contest #010 | AtCoder
AtCoder/arc010_2.php at master · wada811/AtCoder · GitHub
<?php
// 土日の設定
$holidays = array();
for(
    $date = DateTime::createFromFormat('Y/m/d', '2012/01/01', new DateTimeZone('Asia/Tokyo')),
    $end = DateTime::createFromFormat('Y/m/d', '2012/12/31', new DateTimeZone('Asia/Tokyo'));
    $date->diff($end)->format('%R') === '+';
    $date->add(new DateInterval('P1D'))
){
    if($date->format('w') === '0' || $date->format('w') === '6'){
        $holidays[$date->format('Y/m/d')] = true;
    }else{
        $holidays[$date->format('Y/m/d')] = false;
    }
}
// 祝日の取得・設定
fscanf(STDIN, "%d", $n);
for($i = 0; $i < $n; $i++){
    fscanf(STDIN, "%d/%d", $month, $day);
    $date = DateTime::createFromFormat('Y/m/d', "2012/{$month}/{$day}", new DateTimeZone('Asia/Tokyo'));
    // 振替休日の設定
    while($holidays[$date->format('Y/m/d')]){
        $date->add(new DateInterval('P1D'));
    }
    $holidays[$date->format('Y/m/d')] = true;
}
// 最大連休日数の取得
$max = 0;
$count = 0;
foreach($holidays as $holiday){
    if($holiday){
        $count++;
    }else{
        $count = 0;
    }
    $max = $count > $max ? $count : $max;
}
echo $max . PHP_EOL;
?>
通らなかったコード。
AtCoderの回答を見るとわかるのだが一部の問題は何故か通らない。
サンプルなどは通ってしまって何が行けないのか全くわからなくなってしまった。
それにしてもfor文の初期化部でDateTime型の変数を宣言するというのはまぁ酷い。
そしてこれは解決しなそうな感じがする。
誰かわかったらコメントお願いします。

タグ(RSS)