Google Code Jam Japan 2011練習問題 数珠つなぎ


Google Code Jamの過去問、数珠つなぎをPHPで解いてみた。

Snapper はちっちゃな電化製品で、片側に入力プラグ、反対側に出力ソケットがついています。 この出力ソケットには、電球などの電化製品や、他の Snapper の入力プラグを接続することができます。

Snapper は ON か OFF の状態を持っていて、状態が ON で入力プラグから電力を受け取っているときのみ、出力ソケットに電力が供給されます。 また、あなたが指をパチリと鳴らすと、その破裂音に反応して、入力プラグから電力を受け取っている Snapper は ON/OFF の状態が切り替わります。

ある日、私は N 個の Snapper を買ってきて、1 個目の Snapper の入力プラグを電源ソケットに接続、2 個目の Snapper の入力プラグを 1 個目の出力ソケットに接続、といった要領で数珠つなぎにし、N 個目の Snapper の出力ソケットに電球を取り付けました。

はじめの状態では、Snapper はすべて OFF で、1 個目の Snapper のみに電力が供給され、電球は付いていません。 一回指を鳴らすと、1 個目の Snapper は ON になり、2 個目の Snapper に電力が供給されます。 もう一度指を鳴らすと、1 個目と 2 個目の Snapper の状態が切り替わり、2 個目の Snapper は ON であるものの電源が供給されていない、という状態になります。 3 回目には、1 個目の状態が切り替わり、1 個目と 2 個目の両方が ON になります。 もし、ここで 2 個目の出力ソケットに電球が接続されていたとすると、電球が光ります。

私は指を何時間にもわたって鳴らし続けました。 指を K 回鳴らしたとき、果たして電球は光っているでしょうか? 電球は仕掛けのないどこにでもあるようなもので、直前の Snapper から電力を供給されているときにのみ光ります。

http://code.google.com/codejam/contest/1343486/dashboard


問題文で大事なのは3点。
 ・指を鳴らすたびに受電しているSnapperだけが状態を反転させる
 ・受電していてなおかつONのSnapperだけが次のSnapperに給電出来る
 ・受電元のSnapperが給電していなければそのSnapperにも電気はこない


スイッチの状態と受電状態を持つSnapperクラスを作り、
配列として状態を保持する形で実装してみた。ちなみにPHPではクラスはArrayObjectを継承しないと配列として扱えない。

<?php

class Snapper extends ArrayObject {
   var $isElectrified;
   var $isON;

   public function __construct() {
      $this->isElectrified = "false";
      $this->isON = "false";
   }

   public function changeElectroStats() {
      if($this->isElectrified == "false") {
         $this->isElectrified = "true";
      } else {
         $this->isElectrified = "false";
      }
   }

   public function changeSnapperStats() {
      if($this->isON == "false") {
         $this->isON = "true";
      } else {
         $this->isON = "false";
      }
   }

   public function getIsElectrified() {
      return $this->isElectrified;
   }

   public function getIsOn() {
      return $this->isON;
   }
}

   $case = trim(fgets(STDIN));

   while($case--){
      $N = strtok(trim(fgets(STDIN)), ' ');
      $K = strtok(' ');

      $Snappers = new Snapper();
      for($i = 0; $i < $N; $i++) {
         $Snappers[$i] = new Snapper();
      }

      $Snappers[0]->changeElectroStats();
      for($i = 0; $i < $K; $i++) {
         for($j = 0; $j < $N; $j++){
            if($Snappers[$j]->getIsElectrified() == "true") {
               $Snappers[$j]->changeSnapperStats();
            }
            if($Snappers[$j]->getIsElectrified() == "true" && $Snappers[$j]->getIsON() == "true") {
               if($j+1 < $N && $Snappers[$j+1]->getIsElectrified() == "false") {
                  $Snappers[$j+1]->changeElectroStats();
               }
            } else {
               if($j+1 < $N && $j-1 > 0 && $Snappers[$j+1]->getIsElectrified() == "true" && $Snappers[$j-1]->getIsElectrified() == "false" && $Snappers[$j-1]->getIsON() == "true"){
                  $Snappers[$j+1]->changeElectroStats();
               }
            }
         }
      }

      $num++;
      $ans;

      if($Snappers[$N-1]->getIsElectrified() == "true" && $Snappers[$N-1]->getIsON() == "true") {
         $ans = "ON";
      } else {
         $ans = "OFF";
      }
      echo "Case #". $num . ":" . $ans;
   }
?>


ラーメン花月嵐の嵐げんこつらあめん食べました。