2011年9月29日

GoogleCodeJamに挑戦。挫折寸前


お昼休みに激安弁当つつきながらGoogleCodeJamの練習問題というのを解いてみました。

まあ、あれです。昼休みなのに客先サーバの動作が不安定っていう理由で座席に縛り付けられているのです(;-_-) =3
なので気分転換にやってみました。
とりあえずは「数珠繋ぎ」だけですが、
C#で解いたよっ♪
っていう記事が見当たらなかったのでC#で解いてみた結果を載せてみます。

ロジックとしては単純な処理しかしていません。
というか、複雑な処理を組む気はないっす(;´▽｀A``

問題としては、

  • １個以上の電気的スイッチが存在している
  • スイッチの終端には電球がセットされている
  • 終端以外のスイッチの出力には次のスイッチが接続されている
  • スイッチは指を鳴らすという動作によってON/OFFが切り替わる
  • 先頭のスイッチは電力を供給するプラグに接続されている
  • スイッチは電力が供給されている場合のみON/OFFを切り替え、電力が遮断されている場合には変化しない

さて、指をＮ回鳴らしたとき、Ｋ個連結されたスイッチの終端にある電球は光るでしょうか？

脳内で解読した限りこんな感じの要点ではないかと。
興味の出た人はCodeJamのページを読んでみてください。
(練習問題が消えてしまってたらごめんちゃい)

さて、どう解こうかな～、と紙にスイッチの動きを書き出してみたところ
「４個のスイッチ(Ａ－Ｂ－Ｃ－Ｄ)がつながっている場合」
試行回数：スイッチの状態(0:OFF/1:ON)
０：０－０－０－０
１：０－０－０－１
２：０－０－１－０
３：０－０－１－１
４：０－１－０－０
５：０－１－０－１
中略
１３：１－１－０－１
１４：１－１－１－０＠まだ電球は点かない
１５：１－１－１－１＠ここで電球点灯
１６：０－０－０－０＠また消える

・・・うん。２進数だ。
２進数でスイッチの数の桁数下位ビットがすべて１の時に点灯するな、これ(^_^;)

てことは。
指を鳴らした数を２進数で変数にセット
その数にスイッチの数だけ下位ビットから１を並べた２進数を論理積する
論理積した結果がスイッチの数とイコールであれば電球は点く
ということではないかと。

紙にちょっと書き出して検算中・・・検算中・・・β(□-□ )
うん。たぶんおっけー

で、こんなソースになりましたとさ

view plainprint?
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.ComponentModel;  
  4. using System.Data;  
  5. using System.Drawing;  
  6. using System.Text;  
  7. using System.Windows.Forms;  
  8. using System.IO;  
  9.   
  10. namespace GCM_A  
  11. {  
  12.     public partial class Form1 : Form  
  13.     {  
  14.         public Form1()  
  15.         {  
  16.             InitializeComponent();  
  17.         }  
  18.   
  19.         string Fileadd = string.Empty;  
  20.         int counter = 0;  
  21.         int[] snapper;  
  22.         int[] finguer;  
  23.         bool[] light;  
  24.   
  25.         private void button1_Click(object sender, EventArgs e)  
  26.         {  
  27.             //ファイルを開くボタンを用意して、ファイルを開くと同時に処理スタート  
  28.   
  29.             OpenFileDialog ofd = new OpenFileDialog();  
  30.   
  31.             if (ofd.ShowDialog() == DialogResult.OK)  
  32.             {  
  33.                 Fileadd = ofd.FileName;  
  34.             }  
  35.             else  
  36.             {  
  37.                 return;  
  38.             }  
  39.   
  40.             //FileLoad  
  41.             //全データをStringの配列に突っ込む  
  42.             string[] lines = System.IO.File.ReadAllLines(Fileadd);  
  43.   
  44.             //先頭に問題数が記載されているのでそれを取り出して各配列の初期値に使う  
  45.             counter = int.Parse(lines[0]);  
  46.             snapper = new int[counter];  
  47.             finguer = new int[counter];  
  48.             light = new bool[counter];  
  49.   
  50.             for (int i = 1; i <= counter; i++)  
  51.             {  
  52.                 //スイッチの数と指を鳴らす回数はブランクで繋がっているので数値に変換して取り出す  
  53.                 snapper[i-1] = int.Parse(lines[i].Split(' ')[0]);  
  54.                 finguer[i-1] = int.Parse(lines[i].Split(' ')[1]);  
  55.   
  56.             }  
  57.   
  58.             //電球点灯状態を一括チェック  
  59.             Calc();  
  60.   
  61.             //結果を出力  
  62.             OUTPUT();  
  63.   
  64.             //めでたしめでたし  
  65.         }  
  66.   
  67.         private void Calc()  
  68.         {  
  69.   
  70.             for (int j = 0; j < counter; j++)  
  71.             {  
  72.                 //指を鳴らした数  
  73.                 uint a = (uint)finguer[j], x;  
  74.                 //スイッチの数から論理積に使用するビット列を作る。－１するのを忘れないように  
  75.                 int n = (int)Math.Pow(2, (snapper[j]));  
  76.                 uint b = (uint)n-1;  
  77.                 //指を鳴らした数と１になっているべき値を論理積  
  78.                 x = a & b;  
  79.                 //電球が点灯しているかを判断  
  80.                 if (x==b)  
  81.                 {  
  82.                     light[j] = true;  
  83.                 }  
  84.                 else  
  85.                 {  
  86.                     light[j] = false;  
  87.                 }  
  88.   
  89.             }  
  90.   
  91.         }  
  92.   
  93.   
  94.         private void OUTPUT()  
  95.         {  
  96.             //ファイルに一気に出力する  
  97.             StreamWriter sw = new StreamWriter(@"z:\output.txt");  
  98.             for (int k = 0; k < counter; k++)  
  99.             {  
  100.                 if (light[k])  
  101.                 {  
  102.                     sw.WriteLine("Case #" + (k + 1).ToString() + ": ON");  
  103.                 }  
  104.                 else  
  105.                 {  
  106.                     sw.WriteLine("Case #" + (k + 1).ToString() + ": OFF");  
  107.                 }  
  108.   
  109.             }  
  110.             sw.Close();  
  111.             sw.Dispose();  
  112.         }  
  113.   
  114.     }  
  115. }  

Largeの問題を１秒程度で解いてくれると思っています。
さらに速度を上げるのであれば、、、そうすなぁ～
スイッチの数であらわすことのできる２進数値よりも指を鳴らす回数のほうが小さいときは即座にOFFと判断できるんじゃないかと。

ここまで書いておいてなんですが、
きっと毎回参加される方々はもっと早くプログラム作って解けるんだろうなぁ～と。
C#でビット演算ってあまりやらないよなぁ～と。

こういうの好きな高校とかの先生は次回のテストで
＋αのボーナス問題に穴埋めにしてこの問題使いそうだな
と思ったところでお開き。

土曜の予選に参加できるかどうかはサーバが安定するかにかかっている(￣▽￣;)
ラベル: