lecture

研究室で8台のマシンにDebianを入れることになったので、少し考えてみた。ネットワークブートを利用したネットインストール環境を素早く構築する方法を、建てるサーバを減らしてwwwへの通し方も含めてまとめる。(4 Steps)

Step 0. 必要なもの

一台のホスト用Linux（LiveCDでもいい）←文中のコマンドはこのroot
ホストに2口のNICが無ければBBルータ
インストールしたいマシン（PXEに対応）
全てのマシンをつなげるLAN

Step 1. インストール用ネットワークを構築する

ネットワークの設定をする。eth0がWAN（あるいは上流LAN）、eth1がLAN(192.168.123.1/24)。BBルータを使うときは設定不要で、ホストはクライアントと同様に並べる。

   eth0 +------+ eth1    (LAN) 192.168.123
<-------| Host |------+---------+---------+----...
  (WAN) +------+      |         |         |
                   +------+  +------+  +------+
                   |Client|  |Client|  |Client|        画像作るの面倒だし...
                   +------+  +------+  +------+

$ grep "^[^#]" /etc/network.interfaces
auto lo
iface lo inet loopback
allow-hotplug eth0
iface eth0 inet dhcp
allow hotplug eth1
iface eth1 inet static
  address 192.168.123.1
  netmask 255.255.255.0
$ ifup eth1    # LAN
...
$ ifconfig eth1    # だいぶ省略
eth1      inet addr:192.168.123.1  Bcast:192.168.123.255  Mask:255.255.255.0

Step 2. インストーラを取得する

インストーラのtarbalのURLはDebianのサイト(netinst)などから「netboot.tar.gz」という名前のファイルを探せば良い。gtk/netboot.tar.gzを選べば容量は大きいがgraphicalでマウスが使えるインストーラになる。

$ wget d-i.debian.org/daily-images/i386/daily/netboot/netboot.tar.gz
...
$ tar xzf netboot.tar.gz -C /srv/tftp/    # どこでもいい
$ ls -F /srv/tftp
debian-installer/  pxelinux.0@  pxelinux.cfg@  version.info
# pxelinux.0 が初期ブートイメージ（ブートローダ的な働き）

Step 3. PXEサーバを建てる

PXEのための2つのサーバ(DHCP,TFTP)と、www(HTTP)を提供する必要がある。以下で使用するソフトがもし使えなかったり設定に手間取るようならすぐ別の方法を考えてもいい。

dnsmasqはDNSフォワーダ/DHCPサーバでサブシステムとしてTFTPも提供できる。ここではDNSは必要ないが、簡単な設定でサブシステムと連携できるので採用した。Debianではdnsmasqの代わりにtftpd-hpaとdhcp3-serverを使うこともでき、これらには公式のガイドがある（というよりこの代わりにdnsmasqを使おうとした）。

$ apt-get install dnsmasq
...
$ grep "^[^#]" /etc/dnsmasq.conf
interface=eth1            # BBルータの場合はeth0でいい
dhcp-range=192.168.123.50,192.168.123.150,12h
                          # LAN（BBルータの場合はサブネット内で被らないIP）
#dhcp-option=3,1.2.3.4    # BBルータの場合はそのIPを指定
dhcp-boot=pxelinux.0      # /srv/tftp/以下のブートイメージのファイル名前
enable-tftp
tftp-root=/srv/tftp       # netboot.tar.gzを展開した場所
$ /etc/init.d/dnsmasq restart
Restarting DNS forwarder and DHCP server: dnsmasq.

squid3はウェブキャッシュプロキシで、wwwを提供できる。BBルータの場合はそっち経由でWANに行けるため不要。キャッシュが利くと嬉しいが、パッケージはでかいファイルが多いのであんまり期待できないかも。

$ apt-get install squid3
...
$ grep "^[^#]" /etc/squid3/squid.conf    # ほぼデフォルト、重要な箇所をハイライトした
acl manager proto cache_object
acl localhost src 127.0.0.1/32 ::1
acl to_localhost dst 127.0.0.0/8 0.0.0.0/32 ::1
acl localnet src 192.168.123.0/24
...
http_access allow localnet
...
http_port 3128                  # 覚えにくかったら8080でもおｋ
...
cache_dir /var/spool/squid3 100 16 256
...
$ /etc/init.d/squid3 restart    # インスト時に勝手に起動されてた
...

squidの代わりにNAPT(IP masquerade)の設定をする場合（BBルータの動作）

# これらの設定は全て一時的なもので再起動時に元に戻る
$ iptables -t nat -F    # 既存の設定を消す
$ iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
$ sysctl -w net.ipv4.ip_forward=1
$ sysctl -w net.ipv4.ip_dynaddr=1    # omake for DHCP-WAN

Step 4. インストールする

大抵のマシンでは起動直後にF12やEscなど（画面にガイドが出る）を押して Network boot に入る。 Installer boot menu （右図）が表示されない場合はPXEサーバの設定を見直す。 Install を押すとStep 1.の画像ようなインストーラが起動し、他の方法と同様にインストールできる。

squidを使用しているときは HTTP proxy に http://192.168.123.1:3128 を指定する。

補足

BBルータで構成したLANではDHCPサーバが2台あることになるが、 Network boot では大抵不適切なDHCP応答を無視しれくれるので起動できる。更にサブネットを合わせているのでルータをデフォルトゲートウェイに指定すればWANにも届く。

更に多くの台数にインストールする場合は preseed を利用したインストールの自動化することも考えてたほうがいい。

おはようございます、昨日の話です。

この前のJAPLJ contestが3ヶ月ぶりのコンテストでコーディング速度が非常に遅くなっていたので、またリハビリしないとなあと思いながら、SRMなんかも時間が合わなくて中々出れなかった中21:00という久しぶりに参加しやすい時間帯だったので参加したら4時間という長時間で非常に疲れました。因みに今回でyellow(Captain)になりました(・∀・)！

Aは極単純，Bは面倒なだけ，Cはリーディングハード，Dもややリーディングハード，Eは普通，F,Gは読んでません。アルゴリズムの難易度についてはとやかく言える身分じゃないので言及しません。

Eの解法について何人もに訊かれたので、書き留めておきます。

Problem E “Let’s Go Rolling!”

http://codeforces.com/contest/38/problem/E

$1 \le n \le 3000 \, , \, -10^9 \le x_{1..n},c_{1..n}\le 10^9$
直線上にn個のビー玉（質点）をx[i]置いて左（負方向）に転がします。ビー玉はピンで留める事もできて、転がっててきたビー玉もそこで止まります。各ビー玉のコストc[i]は転がった距離またはピン留めコストです。コストの総和を最小化して下さい。

DPです。右方向にビー玉を追加していきます。今n-1個のビー玉があって、n番目のビー玉を一番右に追加したとします。その時増加するコストは、次のようになります。

ピン留めする→そのビー玉のピン留めコスト分
ピン留めしない→（一番右の）最後にピン留めした位置までの距離

つまり、n-1個までの情報の内、解を求める為に必要な情報は、n-1個の中で最後にピン留めした位置とそのコストです。最後にピン留めした位置が同じならそれ以降の最適解は同じなので、ピン留めした位置毎に最適（最小）な値を残せばいいことになります。
よって、DPテーブルは次のようになります。下方向にビー玉の数n。右方向に最後にピン留めしたビー玉の番号。括弧書きは(x,c)。データは総コスト（解）。青い矢印はピン留めしないときの解。緑の丸はその行の最適解（最小値）。赤い矢印はピン留めしたときの解。最終的な解は最後の行の最小値です。

最後にC++のコードです。図の二次元の表で、新しい行を計算するときには直前の一行の値しか参照していないので、一次元配列を更新していくように実装しています。計算量は変わりません。

#include <iostream>
#include <vector>
#include <algorithm>
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ALL(cont) (cont).begin(), (cont).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vii;

int main() {
	int n;
	cin >> n;
	vii x(n);
	REP(i,n) cin >> x[i].first >> x[i].second;
	sort(ALL(x));
	vl c(1, x[0].second);
	FOR(i,1,n) {
		c.push_back(x[i].second + *min_element(ALL(c)));
		REP(j,i) c[j] += x[i].first - x[j].first;
	}
	cout << *min_element(ALL(c)) << endl;

	return 0;
}

ぬるてく

短時間で複数台のマシンにLinuxを入れる