sulume – ページ 2 – ぬるてく

IE ESCを無効化可能にする

2011-07-302012-08-05 sulume

Windows Server 2008 R2, Internet Explorer 9

このPCは普段遣いしてるので、「Internet Explorerセキュリティ強化の構成(IE ESC)」を無効化（Usersで無効化可能に）している。普段IEを使わないから気にしてなかったけど、IE9に更新してからGUI上で無効化してもIEの設定項目が効かない問題が発生していた。そもそもActiveXを使うためにIEが必要になるケースが多いので、保護モードで動かすメリットはあまりない。

Internet Options (Harden) — 保護モードの項目がグレーアウトしている

レジストリ弄ったらできそうだけど分かり易かったりしないかなと思って覗いてみると速攻で如何にもそれらしいものを見つけた。消してみると普通に解決した。

[HKCU\Software\Microsoft\Windows\CurrentVersion\Internet Settings\ZoneMap]
IEHarden=dward:00000001

コマンドでちょちょいと消す場合は↓を実行する。

reg delete "HKCU\Software\Microsoft\Windows\CurrentVersion\Internet Settings\ZoneMap" /v IEHarden

Internet Options (Normal) — 保護モードの項目をアンチェック

Dropboxクライアントで選択的に同期

2011-07-302011-07-30 sulume

メニュー > 設定 > 高度 > 同期フォルダの選択

を開くとチェックボックス付きディレクトリツリーが表示され、既定で全てチェックが入ってるので同期したくないものを外していく。チェックを外したものはローカルから削除される。当然クライアントの設定なので複数台のマシンで使用していれば各々設定する必要があり、マシン毎に異なる設定ができる。

使い始めた頃はこんな機能無かった気がするけどいつの間にか便利になったな。

Gmailのaliasとdeliveredtoでスマートにラベル付け

2011-07-282011-08-29 sulume

@sulume 自分は、エイリアス(oo+xx＠gmail.com)で転送して、deliveredto:oo+xx＠gmail.com でフィルタしてラベル付けしてますよー
2011-07-27 17:02 via webReply RetweetFavorite
@hkobayash
H.Kobayashi @福岡

と教えてもらって初めてgmailのエイリアスの存在を知った。
別名アドレスを使用してメッセージを受信できますか。 – Gmailヘルプ
実はピリオドの仕様も最近まで知らなかった。
ユーザー名を変更する – Gmail ヘルプ
deliveredto:を使って賢くラベル付けできるらしい。
Using advanced search – Gmail Help
あまり知られていないらしいけどそもそも日本語版にdeliveredto:の欄がない。
詳細検索の使用 – Gmail ヘルプ

ref:

Gmailのエイリアスを使ってオシャレ♪にメールを送る

ICPC2011国内予選

2011-06-272011-08-03 sulume

先週(6/25)ICPC国内予選に参加しました。チームmisoは無事アジア地区予選には出れそうですが合宿は難しい感じです。WA出してないのにtimeがやばいことになってます。

A,Bはかんたん。
Cは全探索やるだけ。問題の読み違いに因るデバッグに時間がかかりDより後に提出。
Dも探索で重複排除する。bit使うといい感じ。計算量を見誤って杜撰なコーディングをしてしまい時間を食われる。
EはDP。たぶん早かった。
Fは面倒なだけ。時間切れ。

B,DとEの補助、あとFで残り時間の消費を担当しました。

結果
公式（問題もある） http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/common/guest_standings_en.php
まとめ http://imoz.jp/icpc/2011-domestic.html

6/29追記
予選通過チーム確定 http://icpc2011.ait.kyushu-u.ac.jp/ja/domestic-contest/result

なにかしらsystem系に問題が起きたときはemergeできなくなるケースが多い。例えばビルド系のbinutils,gcc,glibcの他、coreutils,libtool,sedあたりも致命的。
そんなときはビルド済みパッケージ。普段からbuildpkgしていれば過去のビルドを使えるが、そんなことしてなかったりするので配布されているものを使う。障害の原因のパッケージを究明する方法はここでは言及しない。
但し、電源を落としても問題が無く、他のレスキューシステム（デュアルブートやLiveCD）が使えるなら当然その方法を取った方がいい。

# 初めて使うときはディレクトリがないかも
$ sudo mkdir /usr/portage/packages
# app-portage/portage-utilsが有効な場合
$ sudo QMERGE=1 qmerge -K <pkgname>

入ってなかったり古かったりしてqmergeが使えないときは、

$ sudoedit /etc/make.conf
# このURLはportage-utilsのバイナリに内蔵されているものと同じ
PORTAGE_BINHOST=http://tinderbox.dev.gentoo.org/default-linux/x86/
$ sudo emerge -gK <atom>

更に致命的なのはパッケージの配布に使われてるbzip2が壊れたとき。tarはもう知らない。

# 別のシステムでトランスコード
$ bzip2 -cd bzip2.tbz2|gzip > bzip2.tgz
# 対象のシステムに転送したのち
$ sudo tar -xvzpf bzip2.tgz -C /
# ※危険（いい方法あれば教えて）

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

2011-06-102012-08-05 sulume

研究室で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 を利用したインストールの自動化することも考えてたほうがいい。

[obsolete] stringの実装(vc,g++)と扱い方

2011-01-302013-08-25 sulume

この記事は陳腐化しました。C++11 から Copy on Write は実装禁止になりました。g++4.5 以降でも消えました。但し、終端文字を必要とする仕様は健在です。

(2013/08/25 追記)

std::stringを参照渡しにすると高速化した。何を言っているのか（ｒｙ

なんて記事を見ると改めてstringの扱いはハマるとこ多いよなあと感じる。結論から言うと可能な限りconst&やiterator-pairを使えばいいんですが。

stringは一つの文字列プールを指す文字列クラスで、vectorと次の点で似ています。

連続したアドレス上に保管される
メモリは自動で管理される（大抵は一定量から倍々）
要素に’\0’（NULL文字）を使用可能

但し、その実装は処理系によって結構違います。細かいところまでは読んでいませんが、大まかにvcとgccの実装の特徴を紹介します。

g++4.3.4

実装の特徴は、

格納する文字列に必要なプールは常にアロケータから確保
プールにCopy on Write(CoW)の実装

stringのコピーの際に文字列プールを共有（参照カウント）して不要な複製をコストを削減しています。以下捕捉です。

sizeof(string)がプールへのポインタ一つ分なので引数の受け渡しなどで有利
非constの添字アクセスはほんのちょっと余計な処理が入るかも
空文字列は専用のプールが用意されており領域の確保は起きない
文字列定数は必ずコピーされる
常に終端文字が入っている

実際に変更しなくても、非constで要素にアクセスしたときプール全体のコピーが発生するので、コピーを回避するにはconst必須です。

VC2010

実装の特徴は、

終端文字を含めて16B以下はstringのインスタンス内に入る
それ以上はアロケータから確保

16B以下（15文字/wstringなら7文字）の文字列の生成や結合が高速です。短い文字列を大量に扱う場合特に効果を発揮します。以下捕捉です。

sizeof(string)は16B+3ポインタ分と大きめ（Debugビルドでは+1ポインタ）
文字列定数は必ずコピーされる
常に終端文字が入っている

主観的な意見

コピーを回避したいならconst&やshared_ptrを使うので、CoWは余計なお節介だと思います。しかもゲームなど応答性が必要な場合、遅延実行の発動タイミングを意識する必要あります。というか長い文字列を扱う場合は別のクラスを使った方が無難です。個人的にはメモリプールの管理と文字列ポリシーを分けてアダプタで繋ぐような実装が欲しいです。

どちらも常に終端文字が入っていますが、本来C形式である必要はなく、それ故data()とc_str()が用意されています。Cと親和性が必要でない限りc_str()は使わなくていいので、特にvcで16文字格納できないのはちょっと勿体無く感じます。またCの関数にdata()を突っ込んでも動くので誤解される原因でもあります。実際は仕様上の制約でデメリットが大きいため終端文字を付けない実装は見たことがありませんが。

ついでに検査用のソースも載せておきます。でも細かい実装は読んだ方が分かり易いです。

#include <iostream>
#include <string>
using namespace std;
int main() {
	string s1, s2 = "a";

	cout << "size of string: "
	     << sizeof(s1) << endl;
	cout << "initial capacity: "
	     << s1.capacity() << endl;

	while ((char*)&s1 <= s1.data() && s1.data() < (char*)(&s1 + 1))
		s1 += s2;
	cout << "capacity inside of string: "
	     << (int)s1.size()-1 << endl;

	s1 = s2;
	cout << "copy on write: "
	     << (s1.data() == s2.data()) << endl;

	return 0;
}

MySQLのテーブルが壊れた

2011-01-172011-04-10 sulume

エラー: データベースに接続できません

WordPressのトップにたった一行でかでかと表示されてた。ブレーカーが落ちたせいだな。

WordPress側から復元とかできる仕組みがあるらしいけど、うまく動かなかった。エラーメッセージ的にMySQLの方の問題だろうと思って、コマンドラインで試してみるとデータベースには普通に繋がる。とりあえず片っぱしからアクセスしてみると、

mysql> select * from wp_options;
ERROR 145 (HY000): Table './wordpress/wp_options' is marked as crashed and should be repaired

初めて見たエラーだけどググったら速攻で出てきたので何とかなりそう。それにしてもエラーメッセージがおかしい。｢テーブルを読み取れません｣とまで分からなくても「データベースに問題があります」程度にしてくれないと原因究明し辛い。

mysql> check table wp_options;
+----------------------+-------+----------+-----------------------------------------------------------------------------------------+
| Table                | Op    | Msg_type | Msg_text                                                                                |
+----------------------+-------+----------+-----------------------------------------------------------------------------------------+
| wordpress.wp_options | check | error    | Table upgrade required. Please do "REPAIR TABLE `wp_options`" or dump/reload to fix it! |
+----------------------+-------+----------+-----------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> repair table wp_options;
+----------------------+--------+----------+------------------------------------------------------+
| Table                | Op     | Msg_type | Msg_text                                             |
+----------------------+--------+----------+------------------------------------------------------+
| wordpress.wp_options | repair | info     | Wrong bytesec:  58- 34- 34 at 296176; Skipped        |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 7572    |
| wordpress.wp_options | repair | info     | Found block with too small length at 194732; Skipped |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 194744  |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 204696  |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 207436  |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 207532  |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 217276  |
| wordpress.wp_options | repair | info     | Key 1 - Found wrong stored record at 244464          |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 246936  |
| wordpress.wp_options | repair | info     | Found block that points outside data file at 297132  |
| wordpress.wp_options | repair | warning  | Number of rows changed from 161 to 150               |
| wordpress.wp_options | repair | status   | OK                                                   |
+----------------------+--------+----------+------------------------------------------------------+
13 rows in set (0.48 sec)

なんとかなった。

もう2011ですか

2011-01-092011-07-30 sulume

新年あけましておめでとうございます。今年もよろしくおねがいします。
年賀状は各SNS(non-public)に上げているので知り合いの方は参照してください。

暫く間が開いてしまいました。編入生はやはり忙しい様で、2月中旬まで気を抜けません。下手すると本当に留まります。因みに大学や学部だけじゃなく学科によってまちまちなので、編入を考えている高専生は出来る限り同じ学科（あればコース）の先輩に聞くようにしてください。

年末に友人とサークル（電子工作関係）の製作としてマジキチ仕様のCPUを作ろうとしていました。まだ完成していませんが、ALUの代わりにFPUを作りました。規模はでかいけど組み合わせ論理回路です。加減乗除を実装しています。一応任意精度で使えるように作って単精度，倍精度で動作確認しまた（バグ持ってるかもしれない）。VHDLは大学の演習で触った程度の知識しか無かったので、大半がVHDLやIDEとの格闘でした。丸二日掛かりましたしんどかったです。製作は計画的に。

今週提出の１年の授業の課題でPascalを触る羽目になっているんですが、先行宣言ができず相互再帰関数を定義できないことに失望して課題が放置されています。ダブらないように気をつけます。

Codeforces Beta Round #38

2010-10-312012-08-05 sulume

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

この前の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;
}