ACM/ICPC模擬国内予選

ACM/ICPC模擬国内予選 6/27 14:30~17:30

ACM-ICPC OB/OGの会では，毎年ACM-ICPC 国内予選の練習会を開催しています．ということで参加してきました．

チームの詳細は以下．
・大学名
Tokyo National College of Technology(東京高専)
・チーム名
nyama
・メンバ
todo
nyama
ando(都合により模擬予選は不参加)

■Problem A 連続する整数の和
入力される数値が小さいため，単純な2重ループで通す．
ちなみに，実装担当はtodo．

■Problem B ムーンライト牧場
todoがProblem Aを解いている間，問題をnyamaに読んでもらい，収入効率の計算式を作ってもらう．計算式が間違っていたため，一度WAを食らった．計算式を直したら問題なくAC．
式が分数だったため，分数の比較にした方がいいかなと思ったが，実数の(愚直な)比較のまま通ってしまった．
本当は，整数a，b，c，dに対し，
a/b<c/d
を判定するためには，
ad<bc
と書いたほうが良い．
あるいは，実数a，bに対し，
a<b
を判定するには，
(a-b)<EPS

この時点で上位のチームは4問提出していたので焦る．

■Problem C 差分パルス符号変調
二乗誤差を最小にする問題．ここで早くも息詰まる．2人で考えたが解法が思いつかないので一旦パスして他の問題にあたった．
その後，やっと[y_i][入力信号]のDPで解けばいいことに気付きサクッと実装．ほぼ一発で通った．

■Problem D Mr. リトー郵便局
最短移動時間を求める問題．全く解法が浮かばなかった．
解法はワーシャルフロイド法とのこと．

■Problem E 不死の宝石
問題内容は簡単．しかし，棒をどのように置けば良いかさっぱり検討がつかない．解法を話し合う内，nyamaの「2つの円の接線」という言葉でPOJにあった類似問題を思い出す．まず，2つの円に対し(今回は)高々16種類の接線を考えればよい．また，n個の円から2つの円を選び出すパターンはnC2通り，つまりO(n²)．そして，ある接線について，いくつの円が条件を満たしているかを調べるのはO(n)．ということで，せいぜいO(n³)．ここまでで脳内コーディングが終了したので後は実装するだけ．一度WAを食らったが，円が1つしか無い時の例外処理が間違っていて，入力がずれていた所為だった．時間がもう残り少ないのと，計算誤差が不安だったが，修正後は一発で通った．

■Problem F 閘門式運河: 上下に動く水面
実装ゲーっぽかったけど，そこまで解く時間が無かった．

■Problem G 魔法島物語2
二分法で解けるんじゃね?と思ったが，多角形(?)の内部に集落があるかの判定が難しかったのと，すでに時間が無かったので敢え無く終了．

■結果
○○○×○××
14/158

予想以上の結果に驚き．これが東京高専の本気(ｷﾘｯ

Codeforces Beta Round #19

Codeforces Beta Round #17(6/25 0:00~2:00)
悪夢再び…．

■A World Football Cup

□問題
nチームのリーグ戦の結果から，上位n/2チームを辞書式順に出力せよ．

□解法
ソートするだけ．

□コード

import java.util.*;

public class A{
 Scanner sc=new Scanner(System.in);
 HashMap<String, Integer> map=new HashMap<String, Integer>();
 Team[] teams;

 void run(){
  int n=sc.nextInt();
  sc.nextLine();
  teams=new Team[n];
  for(int i=0; i<n; i++){
   String s=sc.nextLine();
   map.put(s, i);
   teams[i]=new Team();
   teams[i].name=s;
  }
  
  for(int i=0; i<n*(n-1)/2; i++){
   String[] s=sc.nextLine().split(" ");
   String[] team=s[0].split("-");
   String[] score=s[1].split(":");
   int t1=map.get(team[0]);
   int t2=map.get(team[1]);
   int s1=Integer.parseInt(score[0]);
   int s2=Integer.parseInt(score[1]);
   if(s1>s2){
    teams[t1].point+=3;
   }else if(s1<s2){
    teams[t2].point+=3;
   }else{
    teams[t1].point+=1;
    teams[t2].point+=1;
   }
   teams[t1].diff+=s1-s2;
   teams[t2].diff+=s2-s1;
   teams[t1].goal+=s1;
   teams[t2].goal+=s2;
  }
  
  Arrays.sort(teams, new java.util.Comparator<Object>(){
   @Override
   public int compare(Object o1, Object o2){
    Team t1=(Team)o1;
    Team t2=(Team)o2;
    if(t1.point!=t2.point)
     return t2.point-t1.point;
    if(t1.diff!=t2.diff)
     return t2.diff-t1.diff;
    return t2.goal-t1.goal;
   }
  });
  
  String[] s=new String[n/2];
  for(int i=0;i<n/2;i++)
   s[i]=teams[i].name;
  Arrays.sort(s);
  for(int i=0;i<n/2;i++)
   System.out.println(s[i]);
 }

 class Team{
  String name;
  int point;
  int diff;
  int goal;
 }

 public static void main(String[] args){
  Locale.setDefault(Locale.US);
  new A().run();
 }
}

そして，B，C，D，Eはどれ一つとして解けませんでした，無念…．

・Result
○××××

・Rating
1580 -> 1554

残念な結果です．

セルオートマトン #33 ルール31

ルール31
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	■	■	■

Fig.1 rule31

線形時間のソート

ソートアルゴリズムにおいて，ソート順が入力要素の比較にのみ基づいて決定されるものを比較ソート(comparison sort)といいます．比較ソートでは，n個の要素をソートするために最悪Ω(nlgn)回の比較を行わなければなりません．ということなので，定数倍を除くとマージソートやヒープソートより早い比較ソートは存在しないのです．

<!-- ここまでコピペ -->

そんな中，O(n)で動作するようなやばいソートもあります．例えば，計数ソート，基数ソート，バケットソートなど…．

■計数ソート(counting sort)
このソートでは，配列aがn個の要素a₀, a₁, …a_n-1,を持っていた時，以下を仮定します．
0≦a_i<k
で，次のように処理を進めます．
1.配列aにおいて，iに等しい要素の個数c_iを計算
2.1.の結果を用いて，c_iがi以下の要素の個数を含むように計算
3.配列aの各要素a_iがどこに位置するかをc_aiで調べ，出力配列bに順次代入．

k=O(n)の時，このソートの計算量はO(n)です．

□コード

// 計数ソート
void countingSort(int[] a, int k){
 int n=a.length;
 int[] b=new int[n];
 int[] c=new int[k];
 for(int i=0; i<n; i++)
  c[a[i]]++;
 // c[i]はiに等しい要素の個数を含んでいる
 c[0]--;
 for(int i=1; i<k; i++)
  c[i]+=c[i-1];
 // c[i]はi以下の要素の個数-1を含んでいる
 for(int i=n-1; i>=0; i--)
  b[c[a[i]]--]=a[i];
 System.arraycopy(b, 0, a, 0, n);
}

■基数ソート(radix sort)
基数ソートは，i桁目に関するソートを最下位桁から最上位桁まで繰り返します．
ソートは安定ソートなら何でもいいのですが，各桁の値のとる範囲が小さければ計数ソートを使うのが妥当です．
要素数がn，各桁の値の範囲が0からk-1(k種類)，桁数がdであるとします．各桁の計数ソートの実行時間は，O(n+k)となります．計数ソートはd回行われるので，基数ソートの実行時間はO(dn+kd)となります．dが定数，k=O(n)ならば，結局O(n)になるので，線形時間で動作するという事になります．

□適用例
ソートする配列

329

457

657

839

436

720

355

1桁目(1の位)に注目してソート

720

355

436

457

657

329

839

2桁目(10の位)に注目してソート．安定ソートを用いているので，下2桁はソートされています．

720

329

436

839

355

457

657

3桁目(100の位)に注目してソート．これで完全にソートされました．

329

355

436

457

657

720

839

□コード
各桁の値は，10進数ではなく2進数で計算しています．2進数では，各桁の値をシフト演算で求める事が出来る，という利点があります．

// 基数ソート
void radixSort(int[] a){
 for(int i=0; i<32; i++)
  // 安定ソートを用いてi桁目に関する配列をソートする
  countingSort(a, i);
}

void countingSort(int[] a, int d){
 int n=a.length;
 int[] b=new int[n];
 int[] c=new int[2];
 for(int i=0; i<n; i++)
  c[(a[i]>>d)&1]++;
 c[0]--;
 c[1]+=c[0];
 for(int i=n-1; i>=0; i--)
  b[c[(a[i]>>d)&1]--]=a[i];
 System.arraycopy(b, 0, a, 0, n);
}

■バケットソート(bucket sort)
バケットソートでは，配列の各要素が区間[0, 1)に一様分布する実数だと仮定します．
配列aの要素数をnとします．
このソートでは，区間[0, 1)をn等分し，n個の要素を各バケットに分配します．
例えばn=10なら，
[0,0.1)，[0.1,0.2)，[0.2,0.3)，[0.3,0.4)，[0.4,0.5)，[0.5,0.6)，[0.6,0.7)，[0.7,0.8)，[0.8,0.9)，[0.9,1)．
その後，各バケットをソートし，順に繋げていくだけです．
この時のソートアルゴリズムは挿入ソートを用います．
挿入ソートの計算量はO(n²)(n個の要素に対して)ですが，色々あってほぼΘ(1)となります．さらに，バケット数がnですので，結果的にO(n)になるのですよ．

□コード

// バケットソート
void bucketSort(double[] a){
 int n=a.length;
 LinkedList<Double>[] list=new LinkedList[n];
 for(int i=0; i<n; i++)
  list[i]=new LinkedList<Double>();
 for(int i=0; i<n; i++)
  list[(int)(n*a[i])].add(a[i]);
 for(int i=0, k=0; i<n; i++){
  Double[] b=list[i].toArray(new Double[0]);
  // リストlist[i]を挿入ソートでソートする
  insertionSort(b);
  for(double d : b)
   a[k++]=d;
 }
}

// 挿入ソート
void insertionSort(Double[] a){
 int n=a.length;
 for(int j=1; j<n; j++){
  double key=a[j];
  int i=j-1;
  while(i>=0&&a[i]>key){
   a[i+1]=a[i];
   i--;
  }
  a[i+1]=key;
 }
}

元ネタは，アルゴリズムイントロダクション第1巻より第9章 線形時間のソーティングでした．

専門書を読む #18

・アルゴリズムイントロダクション
第12章まで

順列生成

順列を生成．

再帰による辞書式順でない順列生成

public void generate(int[] a){
 recursive(a,0);
}

private void recursive(int[] a,int j){
 if(j==a.length){
  System.out.println(Arrays.toString(a));
  return;
 }
 for(int i=j;i<a.length;i++){
  // a[i]とa[j]を入れ替え
  int t=a[j]; a[j]=a[i]; a[i]=t;
  recursive(a,j+1);
  // a[i]とa[j]を入れ替え
  t=a[j]; a[j]=a[i]; a[i]=t;
 }
}

再帰による辞書式順順列生成

public void generate(int[] a){
 recursive(a,0);
}

private void recursive(int[] a,int j){
 if(j==a.length){
  System.out.println(Arrays.toString(a));
  return;
 }
 for(int i=j;i<a.length;i++){
  // j~iを循環右ローテート
  int t=a[i];
  for(int k=i;k>j;k--)
   a[k]=a[k-1];
  a[j]=t;
  recursive(a,j+1);
  // j~iを循環左ローテート
  for(int k=j;k<i;k++)
   a[k]=a[k+1];
  a[i]=t;
 }
}

辞書式順でない順列生成では，単純に2つの要素を交換していますが，辞書式順の順列生成では，その操作を右ローテートに置き換えています．
右ローテートだと辞書式順になる理由は以下の通り．

a₁a₂…a_n
と要素が並んでいて，
a_i>a_i+1
とします．(色々説明が面倒なので要素a_iを数とします)
a_iを先頭に置いた時，辞書式順で初めに来る列(=最小値)は何かというと，
a₁…a_i-1a_ia_i+1…a_n
のa_iを先頭に持ってきた
a_i[a₁…a_i-1a_i+1…a_n]
になります．ちょうどこれは，元の列のa₁…a_iを右にローテートしたものです．
というわけで，i=1~nについてこの操作を実行すると，
a₁[a₂a₃…a_n-1a_n]
a₂[a₁a₃…a_n-1a_n]
…
a_n-1[a₁a₂…a_n-2a_n]
a_n[a₁a₂…a_n-2a_n-1]
とn個の列が出来ます．
それぞれの列について再帰させ，[]内でも同様の操作を行うと，1つの列あたりn-1個の列が出来ます．

a₁[a₂[a₃a₄…a_n-1a_n]]
a₁[a₃[a₂a₄…a_n-1a_n]]
…
a₁[a_n-1[a₂a₃…a_n-2a_n]]
a₁[a_n[a₂a₃…a_n-2a_n-1]]

[[]]の一番内側の列は，2項目までを決定した時の最小値です．
というわけで，n回再帰することで，辞書式順の順列が作れます．

専門書を読む #17

ここ最近の記録．
・アルゴリズムイントロダクション第1巻
第11章まで
・Prologの技芸
3.5節まで

セルオートマトン #32 ルール30

ルール30
クラス3

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	■	■	□

Fig.1 rule30

Project Euler

problem 61
problem 76
problem 77

Project Euler

problem 91
problem 119
problem 203

PKU Judge Online

2028
3009

PKU Judge Online

1978
1979
1980
2684
2685
3006

Project Euler

problem 83
problem 85
problem 125

Project Euler

problem 82
problem 87
problem 117
problem 124

Project Euler

problem 74
problem 114
problem 115
problem 116
problem 206

Project Euler

problem 145
problem 187

PKU Judge Online

1019

ヒープソート

ヒープソート

■コード

int heapSize;
 int parent(int i){ return (i-1)/2; }
 int left(int i){ return i*2+1; }
 int right(int i){ return i*2+2; }
 void swap(int[] a, int i, int j){
  int t=a[i]; a[i]=a[j]; a[j]=t;
 }
 
 /**
  * iを根とする2分木がヒープとなるように，a[i]をヒープの中に“滑り落とす”
  * 但し，left(i)，right(i)を根とする2分木がそれぞれヒープであるとする
  */
 void heapify(int[] a, int i){
  int left=left(i);
  int right=right(i);
  int largest=i;
  if(left<heapSize && a[left]>a[largest])
   largest=left;
  if(right<heapSize && a[right]>a[largest])
   largest=right;
  if(largest!=i){
   swap(a, i, largest);
   heapify(a, largest);
  }
 }
 
 /** ヒープを構築 */
 void buildHeap(int[] a){
  for(int i=(a.length-1)/2; i>=0; i--)
   heapify(a, i);
 }
 
 /** Heap sort(ヒープソート) */
 public void heapSort(int[] a){
  heapSize=a.length;
  buildHeap(a);
  for(int i=a.length-1;i>=1;i--){
   swap(a, 0, i);
   heapSize--;
   heapify(a, 0);
  }
 }

■特徴
・ヒープ構造を用いる
・最悪計算量O(nlogn)
・データによる計算量の変化が小さい

セルオートマトン #31 ルール29

ルール29
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	■	□	■

Fig.1 rule29

Codeforcesへの参加方法（2011/9/23更新）

今回はCodeforcesへの参加方法について．

■登録方法

http://www.codeforces.com/registerにアクセス．



Handle
ハンドルネーム(例:todo)
Email
メールアドレス(例:hoge@gmail.com)
Password
パスワード(例:hogehoge)
Confirm Password
パスワード確認(上に同じ)

これらを入力した後，Registerで完了します． ちなみに，Gmailアカウントを持っている方は，Use Gmailをクリックすれば，それだけで登録が完了します(多分)．

■コンテストの登録

近々コンテストがある場合は， トップページhttp://www.codeforces.com/に

→ Pay attention Registration is running Codeforces Beta Round #18 (Div. 2 Only) 119:34:50 Register now »

こんな感じにコンテストのお知らせが常時表示されます． 登録は，Register nowをクリックするだけです． 開始までの時間が表示されているので便利．

■コンテストの流れ

Registerした状態で開始時刻になると，色々とダイアログが出て，コンテストが開始されます．
基本的には，120分で5問を解くことになります． 問題のそれぞれには，問題文とサンプルがあります． 入出力が標準入出力なので，慣れてない人は少し面倒かもしれません．
コードが完成したら，SUBMITから提出します． 初期のコンテストとは方針が変わり，まず，Pretest（テストケースが弱い）が行われます． これに通れば，ひとまず得点が与えられます． プレテスト通過後，Lock（鍵掛け）を行うことができます． ある問題をLockすると，自分は（その問題の）回答をResubmitできなくなりますが， その代わりとして他人のコードを見ることができます． ある人のコードが間違っていると思った場合は，バグを誘発するような入力を与えます（Hack）． 成功すれば+100，失敗すれば-50ポイント得点が変動します． ちなみに，自分の回答がHackされた場合は， その問題の得点が失われますが， （Lockしていないならば）再びコードを提出することができます．
コンテスト終了後は，System Test（厳密なテストケース）が行われ， このテストに通れば，最終的に得点が与えられす．

Codeforces Beta Round #17

Codeforces Beta Round #17(6/11 0:00~2:00)

時間的な都合でしばらくはTopCoderに参加できないので，Codeforcesに参加してきました．
Codeforcesは，SRM(TopCoder)のようなプログラミングコンテストの一つで，形式はICPCに近い感じです．SRMと違うと感じた点は，

・SRMが3問75分であるのに対し，Codeforcesは基本的に5問120分．
・SRMのように参加者をルーム毎に分けない．
・データの受け渡しには標準入出力を使う
・コードを提出したら，即座にシステムテストが行われる．また，テストに落ちても再提出できる．
・↑のため，Challenge PhaseやSystem Testが無い．

といった所です．

A Noldbach problem
正整数kとnが与えられる．2からnまでの素数で，
1+(i番目の素数)+(i+1番目の素数)
という形で表現出来るものがk個以上ある場合は"Yes"，そうでない時は"No"と出力せよ．

値の範囲が，2≦n≦1000，0≦k≦1000と狭かったため，簡単な実装ゲーでした．

import java.util.*;

public class A{

 void exe(){
  LinkedList<Integer> list=new LinkedList<Integer>();
  for(int i=2; i<=1000; i++)
   if(isPrime(i))
    list.add(i);
  Object[] primes=list.toArray();

  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int k=sc.nextInt();
  int cnt=0;
  for(int c=2; c<=n; c++){
   if(!isPrime(c))
    continue;
   for(int i=0; i<primes.length-1; i++){
    int p1=(Integer)primes[i];
    int p2=(Integer)primes[i+1];
    if(c==1+p1+p2){
     cnt++;
    }
   }
  }
  if(cnt>=k)
   System.out.println("YES");
  else
   System.out.println("NO");
 }

 boolean isPrime(int n){
  if(n<=1)
   return false;
  if(n==2)
   return true;
  if(n%2==0)
   return false;
  int m=(int)Math.sqrt(n)+1;
  for(int i=3; i<=m; i+=2)
   if(n%i==0)
    return false;
  return true;
 }

 public static void main(String[] args){
  Locale.setDefault(Locale.US);
  new A().exe();
 }
}

B Hierarchy
Nickの会社では，n人の従業員を雇用している．
Nickは，従業員の階層構造を作るため，1人を除いたn-1人の従業員に対し，それぞれ1人の監督者を設けることにした．
従業員a_iが，従業員b_iの監督者となる時の費用をc_iとした時，
a_i b_i c_i
の組がm個与えられる．
階層構造を作ったとき，最小のコストを計算せよ．

実際に木構造を作って階層構造を再現する必要があるかなと思いましたが，そんな必要ありませんでした．

import java.util.*;

public class B{
 int n, m;
 int[] q, a, b, c;

 void exe(){
  Scanner sc=new Scanner(System.in);
  n=sc.nextInt();
  q=new int[n];
  for(int i=0; i<n; i++)
   q[i]=sc.nextInt();
  m=sc.nextInt();
  a=new int[m];
  b=new int[m];
  c=new int[m];
  for(int i=0; i<m; i++){
   a[i]=sc.nextInt();
   b[i]=sc.nextInt();
   c[i]=sc.nextInt();
  }
  int max=0;
  for(int i=0; i<n; i++){
   if(q[i]>q[max])
    max=i;
  }
  int cost=0;
  for(int i=0; i<n; i++){
   if(i==max)
    continue;
   int minj=-1;
   for(int j=0; j<m; j++){
    if(b[j]-1==i){
     if(minj==-1||c[j]<c[minj]){
      minj=j;
     }
    }
   }
   if(minj==-1){
    System.out.println("-1");
    return;
   }
   cost+=c[minj];
  }
  System.out.println(""+cost);
 }

 public static void main(String[] args){
  Locale.setDefault(Locale.US);
  new B().exe();
 }
}

C Balance
文字列が与えられて，ごにょごにょ操作し，ある条件を満たす物は幾つ出来るかといった内容．

組み合わせ問題は苦手ですので，飛ばしました…．
＼(＾o＾)／

D Notepad
b進数でn桁の数を，1ページあたりc個書いた時，一番最後のページには幾つの数字が書かれているか?

最終的には，
bⁿ-b^n-1 mod c
を求めるという問題に還元出来ましたが，
2≦b<10¹⁰⁶, 1≦n<10¹⁰⁶, 1≦c<10⁹
という条件に阻まれました．
＼(＾o＾)／

E Palisection
＼(＾o＾)／

・Result
○○×××

D問題が解ければ良かったのですが…．

・Rating
0->1580

初挑戦でしたが，無事Div1に昇格する事が出来ました．

TopCoder SRM 472

SRM472(6/6 3:00~5:00)
久しぶりの参戦．

・PotatoGame(DIV1 Easy)
N個のポテトが積んである．太郎と花子は，交互にポテトをとっていく．ポテトをとる個数は，4のべき乗(1,4,16,64,…)になっている．ポテトを取れなくなった方が負け．お互いが最善を尽くした場合，どちらが勝つか．

しばらく考える．
→解法が思いつかないので，適当に再帰解法もどきを作る
→でも，これだとスタックオーバーフローになるので断念
→実は，単純な規則があるかも?と思って，↑のコードでN=100までの出力見てみる
→周期5のパターンになってる事が判明
→mod 5をとり場合分けして提出

import java.util.*;
import java.lang.*;
import java.math.*;
public class PotatoGame {
 public String theWinner(int n) {
  int a=n%5;
  if(a==1||a==3||a==4)
   return "Taro";
  else
   return "Hanako";
 }
}

// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

Result:Passed System Test(100.48p)

・TwoSidedCards(DIV1 Normal)
＼(＾o＾)／
Result:Opend(0p)

・ColorfulTiles(DIV1 Hard)
＼(＾o＾)／
Result:Unopened(0p)

・Challenges
あるコードを見て，間違っているなとは思ったんですが，撃墜できる入力を与えられず失敗．
-25p

・Score
75.48p

・Rating
1226->1276
意外にもレーティング上昇．それだけに，Easyをもっと早く解ければ…と思いました．

Prologの技芸 2.1節の練習問題

サザエさんデータベース

male(波平).
male(マスオ).
male(カツオ).
male(タラオ).
male(ノリスケ).
male(イクラ).
male(海平).
male(藻屑).
male(サケオ).
male(ノリオ).
male(鯛造).
male(トシオ).
male(カオル).
male(マコト).

female(サザエ).
female(ワカメ).
female(フネ).
female(タイ子).
female(なぎえ).
female(おこぜ).
female(ナナコ).

% Wife, Husband
married_couple(サザエ,マスオ).
married_couple(フネ,波平).
married_couple(タイ子,ノリスケ).
married_couple(おこぜ,鯛造).

father(藻屑,波平).
father(藻屑,海平).
father(藻屑,なぎえ).
father(波平,サザエ).
father(波平,カツオ).
father(波平,ワカメ).
father(海平,カオル).
father(海平,マコト).
father(ノリスケ,イクラ).
father(サケオ,ノリオ).
father(トシオ,ナナコ).

mother(フネ,サザエ).
mother(フネ,カツオ).
mother(フネ,ワカメ).
mother(サザエ,タラオ).
mother(なぎえ,ノリスケ).
mother(タイ子,イクラ).

(1)

% XはYの姉妹
sister(X,Y) :- parent(Z,X), parent(Z,Y), female(X), X \= Y.
% XはYの姪
niece(X,Y) :- daughter(X,Z), sibling(Z,Y).
% 完全な兄弟姉妹(父親，母親が同じ)
sibling2(X,Y) :- father(Z,X), father(Z,Y), mother(W,X), mother(W,Y), X \= Y.

(2)

% XはYの義母
mother_in_law(X,Y) :- mother(X,Z), married_couple(Y,Z).
mother_in_law(X,Y) :- mother(X,Z), married_couple(Z,Y).
% XはYの義理の兄弟
brother_in_law(X,Y) :- brother(X,Z), married_couple(Y,Z).
brother_in_law(X,Y) :- brother(X,Z), married_couple(Z,Y).
brother_in_law(X,Y) :- married_couple(Z,X), sibling2(Y,Z).
% XはYの義理の息子
son_in_law(X,Y) :- married_couple(Z,X), parent(Y,Z).

(3)

% OutputはInput1とInput2の論理ORである．
or_gate(Input1,Input2,Output) :-
 Input1 \= Input2,
 transistor(Input1,ground,Output),
 transistor(Input2,ground,Output),
 resistor(power,Output).

% OutputはInput1とInput2の論理NORである．
nor_gate(Input1,Input2,Output) :-
 or_gate(Input1,Input2,X),
 inverter(X,Output).

大体合っていると思いますが，保証は無いのでご了承を．

セルオートマトン #30 ルール28

ルール28
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	■	□	□

Fig.1 rule28

SuperCon 2010 予選問題

SuperCon(Supercomputing Contest)とは，高校生(含高専生)を対象としたプログラミングのコンテストです．

Supercomputing Contest - Supercomputing Programing Contest Official Site

まず，予選問題が公開されます．予選を通過した10チームは，大阪大学，東京工業大学のスーパーコンピュータを使って本選課題に取り組みます．提出されたプログラムは，審査委員によって評価され，最終的に結果発表，というわけです．

というわけで，予選問題が公開されました．ある図形に対して長方形のレンガを隙間なく並べる場合，その並べ方はいくつあるかといった問題です．それ程難しい問題では無いので，興味ある方はどうぞ．

Supercomputing Contest 2010/予選・認定問題 - Supercomputing Programing Contest Official Site

Project Euler

problem 60
problem 62
problem 68