結論からいうとTest phaseでふるいにかかっちゃいました。750pt問題は落ちるだろうと思ってたんですが、250pt問題まで落としちゃったのはショックです。四捨五入の処理をミスったか無駄にほどこしてみた最適化が問題をおこしたのでしょうが、本当に簡単な問題だっただけにくやまれます。750pt問題もちゃんと冷静に考えて書けばとおっていたかもしれません（expired後に二時間かけて書いたコードはおそらく通る）。何より今回問題だったのが経験のなさと緊張です。緊張は脳みそを馬鹿にします。緊張していると総当たりしか思い付きません。k.inabaさんの偉大さを新ためて思い知りました。点数的には大差ない（つまり実装にかかった時間）のですが、Test phaseを確実に通るコードを書く実力とか冷静さとか、やはり雲の上の人です。

あと今回勉強になったのが、Codeing Areaでプログラミングせずにemacs + g++でプログラミングしつつ、Statementにのっていないようなtestcaseを用意して独自にテストするべきだったということです。一々Compile->Test->Example1->Testとかやってると時間かかってしかたありません。まあ今年始めてなわりには結構健闘できたかなと自己満足しています。

来年はちゃんとアルゴリズムと数学を勉強して挑みたいと思います。当日に徹夜でぷよぷよやっているようではまだまだ駄目です。

(wait for system test phase to end)

暇なときに他のqualification setもといてみようかと。

練習がてら解いてみる。かなり適当。

from math import ceil

class IMGroups:
  def optimalTime(self, N):
    res = 1000000
    for i in range(1, N):
      tmp = int(i + ceil(float(N) / i))
      if tmp < res:
        res = tmp
    return res

#include <iostream>
#include <vector>
#include <string>

#define MOD 10000

using namespace std;

int n;
int memo[18][1 << 15];
vector<string> b;

int go(int k, int d1, int mask) {
    int& res = memo[d1][mask];
    if (res != -1) return res;

    if (k == 0) return res = 1;
    if (d1 >= 2 * n - 1) return res = 0;

    res = go(k, d1 + 1, mask) % MOD;
    for (int i = 0; i < n; i++) {
        int j = d1 - i;
        int d2 = n - 1 + i - j;

        if (i < 0 || i >= n || j < 0 || j >= n) continue;

        if (!(mask & (1 << d2)) && b[i][j] == '.') {
            res += go(k - 1, d1 + 1, mask ^ (1 << d2));
            res %= MOD;
        }
    }

    return res;
}
 
class Bishops {
public:
    int count(int k, vector<string> board) {
        n = (int)board.size();
         b = board;
        if (k > 2 * n - 1) return 0;
        memset(memo, -1, sizeof(memo));
        return go(k, 0, 0);
    }
};

#if 0

int main() {
    vector<string> board;
    board.push_back("........");
    board.push_back("......#.");
    board.push_back("........");
    board.push_back(".#......");
    board.push_back("........");
    board.push_back(".....#..");
    board.push_back("........");
     board.push_back("...#....");

    Bishops bishops;
    cout << bishops.count(7, board) << endl;

    return 0;
}

#endif

class DeckShuffler:
  def getDeck(self, n, shuffled):
    res = range(1, len(shuffled) + 1)
    while n > 0:
      tmp = res[:]
      for i, x in enumerate(shuffled):
        tmp[i] = res[x - 1]
      res = tmp
      n -= 1
    return res

AAB
AAB
BBB

class SquareCounting:
  def howMany(self, grid):
    w = len(grid[0])
    h = len(grid)
    sq = {}
    res = 0
    def row(c, l, t, r):
      while l < r:
        if grid[t][l] != c:
          return False
        l += 1
      return True
    def include(c, l, t, r, b):
      for s in sq.get(c, []):
        if s[0] <= l and s[1] <= t and s[2] >= r and s[3] >= b:
          return True
      return False
    for l in range(w):
      for t in range(h):
        c = grid[t][l]
        r = l + 1
        while r < w and grid[t][r] == c:
          r += 1
        b = t + 1
        while b < h and row(c, l, b, r):
          b += 1
        r = l + min(r - l, b - t)
        b = t + min(b - t, r - l)
        if not include(c, l, t, r, b):
          sq.setdefault(c, []).append([l, t, r, b])
          res += 1
    return res

class ConvexityIssues:
  def howMany(self, values):
    res = 0
    n = len(values)
    for i in range(n - 2):
      for j in range(i + 2, n):
        a1 = float(values[j] - values[i]) / (j - i)
        for k in range(i + 1, j):
          a2 = float(values[k] - values[i]) / (k - i)
          if a1 < a2:
            res += 1
    return res

Plagger::Plugin::Publish::Maildirというモジュールがあるのを知り、先日書いたfetchrssの機能をそのままPlaggerで実現できるじゃんということでPlaggerをインストールしてみました。

% cpan -fi Plagger Plagger::Plugin::Publish::Maildir

ちなみにforceフラグなしでモジュールがインストールできた経験がありません。Portage経由ならCPANモジュールもさくさく入るんですが、あいにくPlaggerというebuildがないようで、いやいやながらCPAN経由で。それで以下のような設定ファイルを書いて早速テスト。

config.yaml:

global:
  timezone: Asia/Tokyo

plugins:
  - module: Subscription::Config
    config:
      feed:
        - http://somewhere/RSS

  - module: Publish::Maildir
    config:
      maildir: /home/foo/Maildir
      folder: plagger
      attach_enclosures: 1
      mailfrom: plagger@localhost

% plagger -c config.yaml
...
Plagger::Plugin [fatal] file error - mail.tt: not found at line 144

はやりなツールはことごとく僕を拒むようです。ログによるとmail.ttはちゃんとインストールされているはずなんですが、なんていうか初歩的すぎて直す気もおこりません。やはり僕はfetchrssでいいです。

普段urxvt + screen + emacs -nwをフルスクリーンにして作業している僕には最高に必要なさそうなCompizをインストールしてみました。環境は Gentoo Linux 2006.1, Ahtlon 64 X2, DDR2 1G, GeForce 7300GT です。最初はCompiz on Xglでやっていたのですが、操作するにつれ画面が徐々に真っ白になってうまく動かないので代替としてAIGLXを使いました。AIGLXはxorg7.1からサポートされたeffects用の正式拡張です。XglのようにXそのものを変えてしまうのではなくて、Xをeffectsに対応させる形に変更するだけなので、たとえばデスクトップマネージャでXglを起動したりするような面倒くさいことをしなくてすみます。詳しくは以下を参照。

http://gentoo-wiki.com/Compiz

http://gentoo-wiki.com/HOWTO_nVidia_GL_Desktop_Effects

http://gentoo-wiki.com/HOWTO_XGL

http://gentoo-wiki.com/HOWTO_AIGLX

手順としては、nvidiaのベータドライバをインストール、effectsを使えるように必要なパッケージを更新、/etc/X11/xorg.confをいじくる、.xsessionなどをいじくってcompizを起動できるようにするって感じです。

/etc/X11/xorg.confはAIGLXのところを読んでください。ちなみに僕は以下のように設定してうごきました。

/etc/X11/xorg.conf:

Section "DRI"
    Group 0
    Mode 0666
EndSection

Section "ServerLayout"
    Option "AIGLX" "true"
EndSection

Section "Module"
#    Load "dri"
EndSection

Section "Device"
    Option "nologo" "true"
    Option "XAANoOffscreenPixmaps" "true"
    Option "DRI" "true"
    Option "AllowGLXWithComposite" "true"
    Driver "nvidia"
EndSection

Section "Screen"
    Option "AddARGBGLXVisuals" "True"
EndSection

Section "Extensions"
    Option "Composite" "Enable"
EndSection

Xorg.0.logによると必要ないオプションも含まれているようですが動くのでいいでしょう。あまりよくわからないのですがglxがちゃんと動いているかはgrep -i glx /var/log/Xorg.0.logとかxdriinfoとかglxgearsとかで確かめられると思います。glxgearsは正常ならば5000fpsぐらい出ます。それをかなり下回るようではeffectsはちょっとつらいです。 で、compizを起動する方法。いろいろあるのですが僕はXfce4 + Custom Session(.xsession)を使っているのでそのやり方をかいときます。

まず、/etc/xdg/xfce4-session/xfce4-session.rcを以下のように編集します。

/etc/xdg/xfce4-session/xfce4-session.rc:

[Failsafe Session]
...
#Client0_Command=xfwm4
Client0_Command=compizrc
...

んで/usr/bin/compizrcを作ります。

/usr/bin/compizrc:

# Start window decorator
gtk-window-decorator --replace &

# Start compiz
LIBGL_ALWATS_INDIRECT=1 compiz --replace --use-cow --indirect-rendering --strict-binding gconf &

ちなみにこれは/usr/bin/compiz-*から拝借して手を加えたやつです。そして~/.xsessionに

rm -rf ~/.cache
execc xfce4-session

と書きます。なんか.cacheがあると二回目にcompizを起動したときに固まるのでrm -rfはそれの対策です。固まらない人は消したほうがいいです。

出来上がった感じはスクリーンショットで載せておきます。

compizの初期起動状態ではプラグインが何も選択されていないので、何もできません。gconftools-2を使うかgconf-editorでactive_pluginsに使いたいプラグインを指定してやらなければなりません。とりあえずはgconftools-2(-s,-g)かgconf-editorで/apps/compiz/general/allscreens/options/active_pluginsに[gconf,decoration,wobbly,fade,minimize,cube,switcher,move,resize,place,rotate,zoom,scale,water,screenshot]を指定しておきましょう。これで通常使う分には問題ありません。うにょうにょ動かしましょう。

ちなみに調子にのってberylもインストールしてみたのですが重すぎてだめでした。テーマの豊富さは魅力なんですが初期テーマがあれなのと重すぎるのとでやっぱりcompizに戻しました。

最後によく使うキーとマウス操作をば。

まだ使い始めたばかりですが、かなり便利です。やっぱり若者はこうでなくちゃ。

なかなかやる機会がない（やる気もない） emerge -Du world ですが、年末年始は絶好のチャンスです。是非やっておきましょう。ついでに kernel の更新もしておくといいかもしれません。

世界を更新:

% esync # or emerge --sync
% emerge portage
% emerge -avDu world
% etc-update

カーネルを更新:

% USE="symlink" emerge gentoo-sources
% cp /path/to/config /usr/src/linux
% cd !$
% make menuconfig
% make && make modules_install

ちなみに kernel を更新するとインストールしておいたドライバも消えるのでそれもインストールしなおしておきましょう。僕の場合は nvidia-drivers と alsa-drivers を入れていたので、それらをインストールしなおします。

% emerge nvidia-drivers alsa-drivers -av

それでまあ alsaconf とか pkill X gdm && gdm で compiz が正しく起動するか確認して一応更新完了。 gentoo にはこれからもバリバリとがんばってもらいます。

(会社のPCも更新したいな…)

オープンソースソフトウェアのソースコードを読むことは確かに勉強にはなるかもしれないけど、その知識でガチガチに防御を固めていざそのプロジェクトに貢献するってなったときに、その人がどれほど役に立つかというと全く勉強していない人と同じぐらいだと僕は思う。

ソースコードというのはそのソフトウェアの具体的写像でしかなくて、いかにソースコードを理解しようともそのソフトウェアを理解したことにはならない。ソフトウェアを理解していないというは結果的に貢献（改善）すべき場所の特定や斬新なアイデアの生成ができないということに等しい。もちろんソースコードを読むというのはスキル上げの面でも娯楽の面でも結構な事だと思う。が、しかし、それでいきなり自分が他人より貢献の力があると思ったりするのは良くない。

どういうわけか巷では、ソフトウェアを改造することよりもそのソースコードを読むことのほうが遥かに人気を博しているようだが、ソースコードを読むことのどこが楽しいのかよくわからない。僕が勉強と銘打って何かしらのソースコードを読んでいるときはいつも全然内容が身についてないなと感じる。それを避けるためか否かは自分でもはっきりしないが、結果的に必要のないときに概観や単語の取得するため以外にソースコードを読むことはやらなくなった。それよりか、今そのソフトウェアにどういう事が起きててどういう事が望まれるかをアンテナを張り巡らしてウォッチしたり考察したりするほうが好きだし、よっぽど生産的だと考えている。別にソースコードを読むのは何かやることを見つけてからでも遅くないし、それに加えておそらくそういう状況のほうが内容が身につくと思うのである。

しかし、アンテナを張り巡らしたり、毎日休むことなく具体的にあるいは漠然と何かやろうと考えるのはなかなか体力が必要で、結局ひとまずそういうことを未来の視野において、今のうちにソースでも読んでおこうという人が出てくるのだと思う。別に今やったって誰も困るわけでもないのに。

僕は人に言えた身分ではないけれども、少なくとも毎日 lkml を読んだり、何かしらアイデアを練ったり、バグを見つければすでにポストされているかを探すようにしている。何も貢献する気はないと言ってしまえばそれまでなのだが、しかしオープンソースソフトウェアに限った話ではなく、どのような世界でもそのようなアグレッシブさを発揮できる人のみが自分の力や知識を如何なく発揮できるポジションに付くものなのだろうと僕は思っている。

僕は周りの数人（カーネルに興味のある人も含まれている）に lkml を読むことを必死に薦めている(*)。しかし誰も読もうとしない。読まない理由を理解できないわけではないが（要するに英語やらなんやらで面倒くさいのだろう）、読まない理由で自分を制させる理由は理解できない。人間は自分の処理系を変化させることによって対象をどう捉えるかを変化させることができる。

つまるところ、もう少しアグレッシブに考えるようにして、自分を自分が居たいと思うポジションに向かうように自分を律するべきだと思うのだ。

(*)数少ない日本人kernel hackerの富士通・亀澤氏もそう提案している

全然まとまってなくて申し訳ない。自律に関してはまた今度書く。