Anne Linux・Windowsをがんばるのだ

« Android is11sh SDカードの不具合 | HOME

遅ればせながら、Google code jamなんてものを今日知りました

こんな様なことをやってるのは知ってましたが、WEBから簡単に参加できるやつもあったんですね。

そこで、過去の練習問題「Code Jam Japan 2011 練習問題　A. 数珠繋ぎ」をやってみました。
Code Jam Japan

こんな問題でした。

----------------------------
〔問題〕

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 から電力を供給されているときにのみ光ります。
入力
1 行目にはテストケースの数 T が含まれています。その後ろに T 行が続きます。 それらの行にはそれぞれ 2 つの整数 N と K が含まれています。
出力
各テストケースにつき 1 行、 "Case #X: Y" と出力してください。ただし、X は 1 から始まるテストケースの番号です。Y は電球が光っているかどうかで、光っているならば "ON"、消えているならば "OFF" としてください。
----------------------------

ネットで探してみると、すでに多くの人が知っていてチャレンジしているようですね・・。２年も遅れて練習参加です。

みんないろんな手法でプログラムしてるようでしたが、僕はこんな感じになりました。
（出来上った結果ファイルをUPすれば、正解・不正解を判断してくれます。LargeにSmallの答えをUPしたら不正解と出たので、ちゃんと動いているようでしたよ。）


#include ＜stdio.h＞
#include ＜math.h＞

int main(void)
{
int size , n;
long sp_value;//（Snapperの数）
long value;//（切り替え数）
long maxvalue;
long count = 1;

scanf("%d",&size);
while(size--){
scanf("%ld" , &sp_value);
scanf("%ld" , &value);

//Snapper数のbitで表せる整数の最大
maxvalue = pow(2 , sp_value);
// 1 << bit数　の方が早そう・・

//切り替え回数がmaxvalueよりも多い時の為に
//ゼロもカウントしたいので、プラス１
value+=1;

if( (value % maxvalue) == 0 ){
printf("Case #%d: ON\n" , count++);
} else {
printf("Case #%d: OFF\n" , count++);
}

}
return 0;
}

Snapperが２つの時を考えてみます。
（右側が１つ目のSnapper、左側が２つ目のSnapperです）

SnapperはONかOFFしかないので、２進数でいう「０」と「１」で表せられて、最初の状態は
「OFF　OFF」

一回指を鳴らすと
「OFF　ON」

もう一回指を鳴らすと
「ON　OFF」

さらにもう一回鳴らすと
「ON　ON」

こんな感じで切り替わっていきます。
これを２進数にしてみると

00
01
10
11

となり、何のことはなく普通に数字が繰り上がっていくだけという事になります。

すべてのビットが「１」になった時に電球が光る事になるので、Snapperの数分のビットすべてが「１」のときの１０進数がわかればなんとなく答えになりそうな予感がします。
（すべてのビットが１の時の１０進数と、指を鳴らした回数が一致すれば光ってるってことです。）

maxvalue = pow(2 , sp_value);
これで、２進数（すべてのビットが１時）を１０進数にしています。

if( (value % maxvalue) == 0 ){
で、数字が一致しているかの判断です。（指を鳴らす回数が多いときも考えなくちゃいけないので）

結局、このこのプログラムの中でそれっぽいのは、pow()だけなんです。
この関数もはっきりと記憶しておく必要はなく、こんな感じの手法を見つけられるかが大切なんじゃないかと思います。
テストケースの数字を読み込むscanf()とかをなくせば、ほんとに数行で終わっちゃいます。
あの長い文書問題からこの程度のプログラムに落としこめる能力が大切ってことですね。
ほかにも手法はあると思いますが、大きくは変わらないでしょう。

---