2016年10月21日金曜日

Lenovo ideapad s205(UEFIブート) に ubuntu 16.04LTS

Lenovo ideapad s205とかいうWindows7だと重くてしょうがない&UEFIでしか起動しないノートにUbuntu16.04LTSインストールしたところ、インストールは成功するも立ち上がってくれません。

なんの関係もないUSBメモリさしてインストールした2回目のtryで何故か立ち上がったので、これが再現性のあるコツかと思い一旦またWindowsをクリアインストール、Ubuntuのインストールを試みるも、以降一度もUbuntuで立ち上がってくれませんでした。

ネットでs205 ubuntuで検索するとみなさん苦労しているようでいろんな情報出てきますが、どれもうまく行かず、最終的に半分あきらめモードでドイツ語の読めるわけないサイトに書かれた方法ためしたら一発で立ち上がってくれました。

https://www.computerbase.de/forum/showthread.php?t=1349567

ここに書かれていることそのままではなく、以下の手順でいけました。
インストールメディアはUSBメモリ使いました。

1.インストールメディアから起動、「ディスクを削除してUbuntuをインストール」でインストール
2.インストールが終わったら、またインストールメディアから「ubuntuを試す」で起動
3.以下コマンド入力

$ sudo su
# mount /dev/sda1 /mnt
# cd /mnt/EFI
# cp -rfv ubuntu boot
# cd boot
# mv grubx64.efi bootx64.efi
# reboot

4.ころあいを見計らってインストールメディア抜き取り

2016年5月2日月曜日

今使っているUbuntuのカーネルのコンパイル

ある人が作ったドライバのパッチを当てたくてUbuntuのカーネルをコンパイルする必要があり、今使っているカーネルのカンタンなコンパイル方法ないかと探したらありました。

Ubuntu wikiのBuildYourOwnKernel

手順書けば、


# cd /usr/src
# apt-get source linux-image-$(uname -r)
# apt-get build-dep linux-image-$(uname -r)
# cd linux-4.4.0 (Ubuntu16.04.LTSの場合)
# fakeroot debian/rules clean
# fakeroot debian/rules binary-headers binary-generic
# cd ..
# apt-get -f install
# dpkg -i linux-*.deb


最後の行は、他に/usr/srcの下に*.debファイルがあるようならファイル名指定で。
Ubuntu16.04LTSでやったところ、以下の6つのdebファイルができました。


linux-headers-4.4.0-21-generic_4.4.0-21.37_amd64.deb
linux-headers-4.4.0-21_4.4.0-21.37_all.deb
linux-image-4.4.0-21-generic_4.4.0-21.37_amd64.deb
linux-image-extra-4.4.0-21-generic_4.4.0-21.37_amd64.deb
linux-tools-4.4.0-21-generic_4.4.0-21.37_amd64.deb
linux-cloud-tools-4.4.0-21-generic_4.4.0-21.37_amd64.deb


apt-get -f installの行は手順にありませんが、最後の2つのdebファイルlinux-tools-...debとlinux-cloud-tools-...debのインストールがコケたため追記しました。

Ubuntu16.04LTS、Ubuntu14.04.4LTSで確認済みです(2016/05/02現在)。

2016年4月26日火曜日

同じ最新のUbuntu14.04.4LTSでもカーネルのバージョンが違ったりする件

Ubuntu14.04のインストールメディアのイメージは今(2016/04/26現在)のところ14.0414.04.1〜14.04.4までの4つのポイントリリースの計5つがあります。
これらは古いリリースのものであってもOSのアップデートを適用していればlsb_release上最新の14.04.4になります。

ところがOSをアップデートして最新の14.04.4になっていても、カーネルのバージョンは各リリースでまちまちで、最初に入れたリリースから変わることがありません。

14.04, 14.04.1〜14.04.4のすべてについてOSをインストール、最新にアップデートした場合のカーネルのバージョンは以下の通りでした。

Ubuntuのリリースインストール時の
カーネルのバージョン
2016/04/26時点の
カーネルのバージョン
14.043.13.0-24-generic3.13.0-85-generic
14.04.13.13.0-32-generic3.13.0-85-generic
14.04.23.16.0-30-generic3.16.0-70-generic
14.04.33.19.0-25-generic3.19.0-58-generic
14.04.44.2.0-27-generic4.2.0-35-generic

Linuxカーネルのバージョンにより、あるデバイスドライバが含まれていたりいなかったりしたことでとある問題が発生、このことで最近気づいたんですが常識なんですかね?

どうゆう問題が発生したかはまたのちほど。

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();
    }
}


結局ライブラリ知ってるもん勝ちな問題でした。