2016年2月5日金曜日

いまさらCode Jam Japan(2011) 決勝 問題B「バクテリアの増殖」 Small

もう5年近く前のことですが、私と同じように解いた解説が出てこないので書いてみます。

問題はこれです。
https://code.google.com/codejam/contest/1363489/dashboard#s=p1

要約すると、
a(0)=A
a(n)=a(n-1)a(n-1)
を満たす配列anの第B項をCで割った余りで答えよ。

このA,B,Cの値の組のテストケース数は500以下
Aの値は1,000以下
Bの値はSmallは2以下、Largeは1,000以下
Cの値は1,000以下

公開鍵暗号の原理と同じで周期から計算できるんだろーなとは思ったんですが、やはりGoogleの解説もそのようになっています。
https://code.google.com/codejam/contest/1363489/dashboard#s=a&a=1

このCode Jam Japanの決勝問題は問題Aが簡単、それに比べて問題B以降が難しく、終了時点で問題AのSmall, Largeだけ解けた人が112位から355位まで大渋滞しています。
https://code.google.com/codejam/contest/1363489/scoreboard#sp=91

200位以内に入れば景品のTシャツがもらえるんですが、問題Aを解いただけでは早く解いた者勝ちです。そこに入れない場合は、どの問題でもいいからSmallだけでも解ければTシャツ圏内に入れる、という状況でした。

で、この問題BのSmallはBが2以下なので、 第2項まで求めればいいようになっています。つまり(AA)(AA)までのmodが計算できれば解けることになります。

　X = AA mod C
として、
　X(AA)
を求めるわけですが、当然指数のAAはmodは効かずこれ自体が天文学的数字になる可能性があります。どうにかXの方をmodしながらべき乗していって求める方法を考えないとダメそうです。

で、苦し紛れに
　(XA)A
で同じにならないかな？と思ってもこれは
　X(A*A) = X(A2)
にしかなりません。

掛け算で並べて書けばわかりやすいんですが、例えばAが5とするとXの5乗は
　X*X*X*X*X
これのさらに5乗は縦に書き足せば
　X*X*X*X*X*
　X*X*X*X*X*
　X*X*X*X*X*
　X*X*X*X*X*
　X*X*X*X*X
Xが5*5個なので
　X(5*5) = X(52)
にしかなりません。

しかし、これをさらに5乗すれば
　X(5*5*5) = X(53)
になります。
ということは、この調子でXを5乗する、を5回繰り返せば
　X(5*5*5*5*5) = X(55)
が求まることになります。同様に、X(AA)を求めるためには、XをA乗するのをA回繰り返せばよい、ということになります。

A,B,Cがjavaのintとして与えられているとして、BigIntegerクラスのmodPowを使って書けば、
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.modPow(a, c);
for (int i = 0; i < A; i++)
    X = X.modPow(a, c);
とまあ、とても短いプログラムで求めることができます。

実際私はmodPowメソッドの存在を知らなかったのでこれ相当の関数を自分で作り、終了前15分で解答提出、260位(?)あたりから一気に89位に浮上、終了時点で96位、最終的に93位で無事Tシャツを頂きました。

BigIntegerを使ってキレイに書きなおせば以下のようなコードになります。
import java.math.BigInteger;
import java.util.Scanner;

public class B {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            System.out.println("Case #" + i + ": " +
                resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
    }

    private static int resolv(int A, int B, int C) {
        BigInteger a = BigInteger.valueOf(A);
        BigInteger b = BigInteger.valueOf(B);
        BigInteger c = BigInteger.valueOf(C);
        BigInteger X = a.modPow(a, c);
        if (B == 2)
            for (int i = 0; i < A; i++)
                X = X.modPow(a, c);
        return X.intValue();
    }
}

実はこのBigIntegerクラス、1,0001,000も扱えてしまうので、上で書いたようなことは全く考える必要もなく、そのまま素直にコーディングすれば解けてしまうのでした。

import java.math.BigInteger;
import java.util.Scanner;

public class B2 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            System.out.println("Case #" + i + ": " +
                resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
    }

    private static int resolv(int A, int B, int C) {
        BigInteger a = BigInteger.valueOf(A);
        BigInteger b = BigInteger.valueOf(B);
        BigInteger c = BigInteger.valueOf(C);
        BigInteger X = a.pow(A); // 最大1,0001,000
        BigInteger Xm = X.mod(c);
        if (B == 2)
            Xm = Xm.modPow(X, c); // そのまま計算
        return Xm.intValue();
    }
}

結局ライブラリ知ってるもん勝ちな問題でした。
投稿者 時刻: 0 件のコメント:
ラベル:

2016年2月3日水曜日

ブログタイトル変更しました。

どう見ても日記じゃなくて技術メモだし。
投稿者 時刻: 0 件のコメント:
ラベル:

2015年11月25日水曜日

Ubuntu14.04LTSでCassandra2.2のインストールがコケる件

Cassandraの2.2のインストールマニュアル通りにやってもコケてくれました(2015/11/25現在)。

$ sudo apt-get install dsc22
          :
The following packages have unmet dependencies:
 dsc22 : Depends: cassandra (= 2.2.3) but 3.0.0 is to be installed
E: Unable to correct problems, you have held broken packages.

これは2.1のインストールマニュアルを参考にバージョン指定したら行けました。

$ sudo apt-get install dsc22=2.2.3-1 cassandra=2.2.3
$ sudo apt-get install cassandra-tools=2.2.3

でこの件、2.1の時も同じ問題が起きていたようです。
ドキュメントの不備のようなので、すぐ改善されると思います。
投稿者 時刻: 0 件のコメント:
ラベル:

2015年8月28日金曜日

JavaVMがプロセスのMax open filesのソフトリミットを変更する件

JavaVMを起動するとそのプロセスのMax open filesのソフトリミット(soft limit:一般ユーザが変更できる上限値、ulimit -Snで参照可能)をハードリミット(hard limit:rootが変更できる上限値、ulimit -Hnで参照可能)まで引き上げます。

Ubuntu14.04LTSでは一般ユーザのMax open filesは以下のようにソフトリミット1,024、ハードリミット4,096になっています。

$ ps
  PID TTY          TIME CMD
 2447 pts/0    00:00:00 bash
 3766 pts/0    00:00:00 ps
$ cat /proc/2447/limits | grep 'Max open files'
Max open files            1024                 4096                 files   

以下のようなプログラムを作って実行、

$ cat > Test.java
public class Test {
    public static void main(String arvs[]) {
        try {
            while (true)
                Thread.sleep(1000);
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
}
$ javac Test.java
$ java Test

同様に/procの下を確認してみると、両方とも4,096になっています。つまりソフトリミットがハードリミットまで引き上げられています。

$ ps -ef | grep Test
sofnec    4007  2200  0 14:37 pts/13   00:00:00 java Test
sofnec    4030  2447  0 14:37 pts/0    00:00:00 grep --color=auto Test
$ cat /proc/4007/limits | grep 'Max open files'
Max open files            4096                 4096                 files   

この件、古いJavaVMのドキュメントには-XX:MaxFDLimitオプションで説明されていますが(http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html)、最近のLinix版のもの(http://docs.oracle.com/javase/8/docs/technotes/tools/unix/java.html)にはこのオプションが書かれていません。

ところが、Linux 版のJava8で試したところ、このオプションが使えてしまいました。

$ java -XX:-MaxFDLimit Test

これで起動して別のターミナルで確認すると、以下のようにソフトリミットは変更されていません。

sofnec@cassandra1:~$ ps -ef | grep Test
sofnec    4387  2200  0 14:51 pts/13   00:00:00 java -XX:-MaxFDLimit Test
sofnec    4398  2447  0 14:51 pts/0    00:00:00 grep --color=auto Test
sofnec@cassandra1:~$ cat /proc/4387/limits | grep 'Max open files'
Max open files            1024                 4096                 files

でこの動き、Ubuntu14.04LTSのOpenJDKでも一緒でした。こちらについてはソースレベルで確認された方がいました。

http://stackoverflow.com/questions/30487284/how-and-when-and-where-jvm-change-the-max-open-files-value-of-linux

というわけで最初に書きましたがもう一度。

JavaVMはそのプロセスのMax open filesのソフトリミットをハードリミットまで引き上げますが、-XX:-MaxFDLimitオプションにより無効にできます。

(ドキュメントに書いといてよ...)
投稿者 時刻: 0 件のコメント:
ラベル:

2015年4月6日月曜日

javaでRuntime.execしたプロセスのPIDを取得する方法

意外と日本語のページが引っかからなかったので書いときます。

        try {
            Field field = process.getClass().getDeclaredField("pid");
            field.setAccessible(true);
            int pid = field.getInt(process);
        } catch (NoSuchFieldException|IllegalAccessException ex) {
            ex.printStackTrace();
        }

processはRuntime.execが返したjava.lang.Process、Fieldはjava.lang.reflect.Field。
投稿者 時刻: 0 件のコメント:
ラベル:

2014年7月19日土曜日

SECCON 2014 オンライン予選 writeup - プログラミング300 あみだ

手動で2時間くらいかけて150問解いたところで挫折、 プログラムで解こうとコーディングを始めて１時間半で終了。 最初から組めや＞自分

手順は以下の通り。

*が開始座標
*の[上下右左]が[||--]ならそれが進行方向、1つ進む
while 現在位置が[||--]
    現在位置の進行方向横が[-|]なら[|-]になるまで横にスライド
    1つ進行方向に進む
現在位置の文字出力

import java.io.*;
import java.util.*;

public class T {
 public static final int NO_DIRECTION = 0;
 public static final int TO_DOWN = 1;
 public static final int TO_UP = 2;
 public static final int TO_RIGHT = 3;
 public static final int TO_LEFT = 4;

 public static void main(String args[]) {
  InputStream is = null;
  OutputStream os = null;
  try {
   Process p = Runtime.getRuntime().exec("./amida");
   is = p.getInputStream();
   os = p.getOutputStream();
  } catch (Exception ex) {
   ex.printStackTrace();
  }
  try {
   new T().go(is, os);
  } catch (Exception ex) {
   ex.printStackTrace();
  }
 }

 public void go(InputStream is, OutputStream os) throws Exception {
  int no = 1;
  while (true) {
   int c;
   int width = 0;
   int height = 0;
   while ((c = is.read()) != '\n') {
    if (c == -1)
     System.exit(1);
    System.out.print((char)c);
   }
   System.out.println();

   StringBuffer sb = new StringBuffer();
   String line = null;
   ArrayList list = new ArrayList();
   while ((c = is.read()) != '?') {
    if (c == -1)
     System.exit(1);
    // System.out.println("2:" + c);
    if (c == '\n') {
     line = sb.toString();
     if (line.length() > 0) {
      width = line.length();
      list.add(line);
      sb = new StringBuffer();
     }
    } else {
     sb.append((char)c);
    }
   }

   is.read();

   height = list.size();
   char amida[][] = new char[height][width];
   int startX = 0;
   int startY = 0;

   for (int i = 0; i < list.size(); i++) {
    line = list.get(i);
    System.out.println(line);

    for (int j = 0; j < line.length(); j++) {
     amida[i][j] = line.charAt(j);
     if (amida[i][j] == '*') {
      startY = i;
      startX = j;
     }
    }
   }
   //System.out.println(startY + ":" + startX);

   int direction = NO_DIRECTION;
   int y = startY;
   int x = startX;
   if (startY == 0 && amida[1][startX] == '|') {
    direction = TO_DOWN;
    y++;
   } else if (startY == height - 1 &&
    amida[height - 2][startX] == '|') {
    direction = TO_UP;
    y--;
   } else if (startX == 0 && amida[startY][1] == '-') {
    direction = TO_RIGHT;
    x++;
   } else {
    direction = TO_LEFT;
    x--;
   }

   //System.out.println("direction:" + direction);
   //System.out.println(y + ":" + x);

   while (amida[y][x] == '|' || amida[y][x] == '-') {
    // System.out.println(y + ":" + x + ":" + amida[y][x]);
    if (direction == TO_DOWN || direction == TO_UP) {
     if (x > 0 && amida[y][x - 1] == '-') {
      x--;
      while (amida[y][x] != '|')
       x--;
      if (direction == TO_DOWN)
       y++;
      else
       y--;
     } else if (x < width - 1 && amida[y][x + 1] == '-') {
      x++;
      while (amida[y][x] != '|')
       x++;
      if (direction == TO_DOWN)
       y++;
      else
       y--;
     } else {
      if (direction == TO_DOWN)
       y++;
      else if (direction == TO_UP)
       y--;
     }
    } else if (direction == TO_RIGHT || direction == TO_LEFT) {
     if (y > 0 && amida[y - 1][x] == '|') {
      y--;
      while (amida[y][x] != '-')
       y--;
      if (direction == TO_RIGHT)
       x++;
      else
       x--;
     } else if (y < height - 1 && amida[y + 1][x] == '|') {
      y++;
      while (amida[y][x] != '-')
       y++;
      if (direction == TO_RIGHT)
       x++;
      else
       x--;
     } else {
      if (direction == TO_RIGHT)
       x++;
      else
       x--;
     }
    }
   }

   os.write(amida[y][x]);
   System.out.println("Ans=" + amida[y][x]);
   os.write('\n');
   os.flush();
   no++;
  }
 }
}
No.79だけバグってる模様。これだけハードコードで7。 (バグってたのは自分の頭、2014/07/22訂正) 1,000問解いてやっとキーが出てきた。 
No.1000
            *  
| | |-| | | | |
|-| | |-| | |-|
| | | | | | | |
| |-| |-| | | |
|-| | | |-| |-|
| |-| | | | | |
|-| | |-| |-| |
| | |-| |-| |-|
| |-| |-| | | |
|-| | | | | |-|
| |-| |-| |-| |
| | |-| | | |-|
| | | | |-| | |
|-| |-| | |-| |
| |-| | | | | |
| | |-| | |-| |
|-| | | |-| | |
| | | |-| |-| |
| | |-| |-| |-|
1 2 3 4 5 6 7 8
Ans=3
FLAG{c4693af1761200417d5645bd084e28f0f2b426bf}
投稿者 時刻: 0 件のコメント:
ラベル:

2014年5月1日木曜日

CentOS 6.5 カーネル再構築 2.6.32-431.11.2.el6.x86_64編

CentOSのカーネル再構築メモ。
最新のLinuxカーネルで構築し直すんじゃなくて、今動いているシステムのカーネルソースいじって遊ぶぜ的な人向けの手順です。

バージョンによって前提パッケージが違ったり、ソースをダウンロードしてくるところが違ったり面倒だったので、なるべく汎用性ありそうな書き方で。

まずOS自体を最新バージョンにアップデート。
# yum update
# reboot
私がやったとき(2014/04/29)の最新バージョンは2.6.32-431.11.2です。64ビット版です。

続いて開発環境をインストール。これは他サイトからの受け売り。
# yum groupinstall "Development tools" 

で、次にその他の前提パッケージのインストール、ってのがありがちな書き方ですが、その前にソースをダウンロードして、インストールを試みます。ソースの置き場所もその時々で違ったりするので、CentOSのサイトで確認するといいんじゃないかと思います。
2014/04/29時点では、トップ→Get CentOS Linux Now→Need the Source?
とたどって、ソース置き場からとってきました。これを一般ユーザでインストールします。
$ wget http://vault.centos.org/6.5/updates/Source/SPackages/kernel-2.6.32-431.11.2.el6.src.rpm
$ rpm -ivh kernel-2.6.32-431.11.2.el6.src.rpm

で、rpmbuildを動かすと必要な前提パッケージを教えてくれます。 これがバージョンによって違ったりするようなので、違うバージョンの手順を真似るよりはrpmbuildに聞いた方が確実なんじゃないかと。 
$ cd ~/rpmbuild/SPECS
$ rpmbuild -bp kernel.spec --target=x86_64
ビルド対象プラットフォーム: x86_64
ターゲット x86_64 用にビルド中
エラー: ビルド依存性の失敗:
        xmlto は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        asciidoc は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        elfutils-libelf-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        elfutils-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        zlib-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        binutils-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        newt-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        python-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        audit-libs-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        perl(ExtUtils::Embed) は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
        hmaccalc は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています

で、これらをインストールします。perl(ExtUtils::Embed)はさすがにクォーテーションで囲まないとエラーになると思います。 
# yum install xmlto asciidoc elfutils-libelf-devel elfutils-devel zlib-devel binutils-devel newt-devel python-devel audit-libs-devel "perl(ExtUtils::Embed)" hmaccalc

この後もう一回rpmbuild実行、~/rpmbuild/BUILDの該当バージョンというか、できてるディレクトリの下に行ってmake、インストールします。 
$ rpmbuild -bp kernel.spec --target=x86_64
$ cd ~/rpmbuild/BUILD/kernel-2.6.32-431.11.2.el6/linux-2.6.32-431.11.2.el6.x86_64
$ vi Makefile
EXTRAVERSION = -selinux
$ make
# make modules_install
# make install
# reboot
ここではMakefileのEXTRAVERSIONを-selinuxにしています(個人的にSELinuxまわりの研究でやっているので)。
この場合OS起動時eをタイプすることで表示されるブートオプションの画面で、構築したカーネルが2.6.32-selinuxと表示されます。
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)