2011-07-06

AOJ Vol.0 0026 Dropping Ink

C/C++ AOJ

「Dropping Ink」に挑戦。

方針

マス目の状態を表す10x10の配列を用意
空白マスをカウントする変数を用意
インクが滴下される座標と滴の大きさを取得
座標を中心に，滴の大きさに応じて配列の数値をインクリメント
同時にそのマスが初めてインクで染められる場合は空白カウントをデクリメント

変数宣言。

int x,y,p[10][10],d,m,w=100;

x,y : 座標用
p[10][10] : マス目の状態
d : 滴の大きさ
m : インクの濃さの最大値
w : 空白マスの数

座標(x,y)にインクが染みこむ処理 r(x,y)。ここでのx,yはローカル変数。

r(x,y){
  if(!(x<0||9<x||y<0||9<y)){
    if(!p[y][x]) w--;
    p[y][x]++;
    if(m<p[y][x]) m=p[y][x];
  }
}

座標が有効範囲（0≦x,y≦9）であれば処理。
マスが空白（p[y][x]==0）であれば空白マスが一つ減ることになるのでwをデクリメント
マスの状態をインクリメント
濃さの最大値を更新

滴下されたインクの大きさに応じて適切な座標でr()を呼び出す処理 o(a,b)。

a,b : 中心座標(x,y)から何マス隔たった位置を処理するかを表現。
- a=1,b=0であれば(x,y)の右・上・左・下の4マス(x+1,y)(x,y-1)(x-1,y)(x,y+1)
- a=1,b=1であれば(x,y)の斜め隣り4マス(x+1,y+1)(x+1,y-1)(x-1,y-1)(x-1,y+1)

o(a,b){
  r(x+a, y+b);
  r(x+b, y-a);
  r(x-a, y-b);
  r(x-b, y+a);
}

main関数。

滴下された座標(x,y)とその上下左右はデフォルトで処理
滴の大きさが1より大きければ斜め隣りも処理
同じく2より大きければ上下左右に1つ隔たったマスも処理
入力分繰り返し
結果を表示

main(){
  for(; ~scanf("%d,%d,%d",&x,&y,&d); ){
    r(x,y);
    o(1,0);
    if(d>1) o(1,1);
    if(d>2) o(2,0);
  }
  printf("%d\n%d\n",w,m);
  return 0;
}

これを縮めて

int x,y,p[10][10],d,m,w=100;
r(x,y){
  (x<0||9<x||y<0||9<y)||(!p[y][x]++&&w--,m<p[y][x]&&(m=p[y][x]));
}
o(a,b){
  r(x+a,y+b);
  r(x+b,y-a);
  r(x-a,y-b);
  r(x-b,y+a);
}
main(){
  for(;~scanf("%d,%d,%d",&x,&y,&d);r(x,y),o(1,0),d>1&&o(1,1),d>2&&o(2,0));
  return !printf("%d\n%d\n",w,m);
}

空白除いて262バイト。

2011-05-19

画期的？なソートアルゴリズム - sleep sort

ruby アルゴリズム

http://dis.4chan.org/read/prog/1295544154で紹介されていたソートアルゴリズムが面白かったので，Rubyで実装してみた。

# sleep_sort.rb
def sleep_sort nums
  result = []
  threads = nums.map do |num|
    num = num.to_i
    Thread.new do
      sleep num
      result << num
    end
  end
  threads.each{|t| t.join}
  result
end

unless ARGV.empty?
  puts sleep_sort ARGV
end

実行結果

> ruby sleep_sort.rb 1 3 5 4 2
1
2
3
4
5

与えられた数値の個数だけスレッドを生成し，各数値を担当させる。
各スレッドは担当した数値の長さ（に比例する時間）だけSleepした後，結果を出力する。

ってことだけど，確かに画期的だｗ

2011-02-24

AOJ 0000 QQ

C/C++ AOJ

いくつかAOJの問題に挑戦したのでメモ。
Problem ID:0000の九九を表示する問題。
まずはベタに。

int main(){
  int a,b;
  for(a=1; a<=9; a++)
    for(b=1; b<=9; b++)
      printf("%dx%d=%d\n", a, b, a*b);
  return 0;
}

#include しなくても通るっぽい。
ここから縮めていく。

main(a,b){
  for(a=0;a++<9;)
    for(b=0;b++<9;printf("%dx%d=%d\n",a,b,a*b));
  return 0;
}

main関数の型(int)を省略
変数a,bをmain関数の引数として宣言し，型を省略
a,bのインクリメントとループ終了判定を同時に
printf文を内側forループに取り込む

これで空白削除すれば81バイト。
で，さらに

main(a,b){
  for(b=0; a<10;
    (b=++b%10)? printf("%dx%d=%d\n",a,b,a*b):a++
  );
  return 0;
}

main関数の最初の引数(a)は1に初期化されることを利用して初期化を省略
forループを一本化
bのインクリメント｜繰り返しとprintf出力｜aのインクリメントの処理を統合

これでやっと78バイト。
62バイトとかってどうやったらできるの？

2011-02-24

AOJ 0004 Simultaneous Equation

C/C++ AOJ

二元連立一次方程式の解を求めるプログラム。
行列式を使った解法を実装してみる。

行列式による解法

二元連立一次方程式
$\left\{\begin{array}ax%2bby=c\\dx%2bey=f\end{array}$
を行列式で表現する。
$\begin{pmatrix}a%26b\\d%26e\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}c\\f\end{pmatrix}$
両辺に逆行列を掛けて
$\begin{pmatrix}x\\y\end{pmatrix}=\frac{1}{ae-bd}\begin{pmatrix}e%26-b\\-d%26a\end{pmatrix}\begin{pmatrix}c\\f\end{pmatrix}=\frac{1}{ae-bd}\begin{pmatrix}ec-bf\\-dc%2baf\end{pmatrix}$
よって
$\left\{\begin{eqnarray}x%26=%26\frac{ec-bf}{ae-bd}\\y%26=%26\frac{af-dc}{ae-bd}\end{eqnarray}$
これを元にコードを書く。

main(){
  double a,b,c,d,e,f,t;
  for(;scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)==6;){
    t=a*e-b*d;
    printf("%.3lf %.3lf\n",(e*c-b*f)/t,(a*f-d*c)/t);
  }
  return 0;
}

ところが，このコードはAcceptされず“Wrong Answer”になってしまう。
これにしばらく嵌った。結局，

main(){
  double a,b,c,d,e,f,t;
  for(;scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)==6;){
    t=a*e-b*d;
    printf("%.3lf %.3lf\n",(e*c-b*f)/t+0.0,(a*f-d*c)/t+0.0);
  }
  return 0;
}

とすることでAcceptされた。よくわからない。勉強不足。
scanfがEOF(==-1)を返してきたときに，その補数をとることでループ終了判定する。

float a,b,c,d,e,f,t;
main(){
  for(;~scanf("%f%f%f%f%f%f",&a,&b,&c,&d,&e,&f);
    t=a*e-b*d,printf("%.3f %.3f\n",(e*c-b*f)/t+0.,(a*f-d*c)/t+0.)
  );
  return 0;
}

最終的に147バイトまで縮めた。

参考

Short Coding ~職人達の技法~

2011-01-28

Online Judge

C/C++

算数オリンピックの記事からいろいろ辿って「http://rose.u-aizu.ac.jp/onlinejudge/index.jsp」に着いた。
問題が豊富でおもしろそう。始めてみよう。

2011-01-13

Ubuntu8.04＋GW-USValue-EZ(PLANEX)で無線LAN

Ubuntu

Ubuntu8.04＋GW-USValue-EZで無線LAN接続するための設定覚え書き

作業の履歴

ndiswrapperを使ってドライバインストール→動作せず
ndiswrapperを1.52から1.56にアップグレード
ドライバ再インストール→動作した

作業内容

1.ndiswrapperを使ってドライバインストール

ndisgtkを起動し，WindowsXP用ドライバをインストール
USBデバイスとしては認識されるものの，iwconfigの結果にwlan0が表示されない。

2.ndiswrapperをアップグレード

開発環境を構築
ndiswrapperのソースをダウンロードしてきて解凍
解凍後のフォルダで

make uninstall
make
make install

3.ドライバ再インストール

ndisgtkからインストールしようとするとフリーズしてしまう
そこでターミナルから

sudo ndiswrapper -r net8888cu
sudo ndiswrapper -i net8888cu.inf

でGW-USValue-EZのLEDが点灯した。
NetworkManagerでも無線LANの項目が表示され，アクセスポイントが表示された。

…のに繋がらない。どうやらDHCPのIP取得がうまくいってない模様。
続きは後日。

追記

参考

2010-10-07

子どもに10回クイズを出してみた

雑記

5歳になる娘に「10回クイズ」を出題してみたところ，全く引っかからない。

(・ω・) 「“ピザ”って10回言ってみて」
(*･∀･) 「ピザピザピザ…」
(・ω・) （肘を指しつつ）「ここは？」
(*･∀･) 「ひじ！」（即答）

(・ω・) 「“みりん”って10回言ってみて」
(*･∀･) 「みりんみりんみりん…」
(・ω・) 「鼻の長い動物は？」
(*･∀･) 「ゾウ！」（即答）

このやりとりを横で聞いていた妻は，答えを声にこそ出さなかったが，「引っかかった」と言っていた。
出題者である自分ですら，危うく「首の長い動物は？」と問いそうになる。

なぜ引っかかる？

そもそも10回クイズとは，

唱える言葉と誤答の音が近く
誤答と正答が同じカテゴリに分類される

ものである。

たとえば最初の問題

ピザ（唱える）
ひざ（誤答）
ひじ（正答）

では，「ピザ」と「ひざ」の“音”が近く，「ひざ」と「ひじ」はどちらも身体の部位である。
二番目の問題

みりん（唱える）
キリン（誤答）
ゾウ（正答）

では，「キリン」と「ゾウ」は「動物」に分類される。どちらも体に突出して“長い”部位があり，通常動物園に行かないと見られない点で，さらに似通っている。

個別の具体的な対象からその特徴や性質を抽出し，分類することで物事は把握しやすくなる。OOPにおける基底クラスの抽出に似ているが，これは成長するにつれて鍛えられる能力だろう。こと10回クイズにおいては，その能力のために同じカテゴリに属する誤答へとスリップしてしまう。

なぜ引っかからない？

娘も「ひざ」「ひじ」がともに身体の部位であることは理解している（と思いたい）が，その分類を介して両者が結びつくほどではない。娘にとってキリンはキリンであり，ゾウはゾウなのだ。「動物」という分類について知ってはいても，それによって二者を大雑把にまとめて取り扱うことはしていない。
そういう意味で，娘の中ではこれらの「分類」が定着していないのだろう。だから引っかからない。

具体的なものに満ちた世界

今後，物事を抽象化し分類する能力が成長していくにつれ，娘が見ているであろう具体的なものに満ちた世界がどのように変わっていくのか，興味深い。