2014年10月12日日曜日

Greedのカスタマイズ

TopCoderのArena用プラグイン「Greed」のカスタマイズに挑戦。




Greedは高機能なので、ほとんど何の設定をしなくても、Arena参戦するのに困る事は無い。
しかし、他のSRM参加者のソースを見ていると、ソースの初めに

#define REP(i, N) for (int i = 0; i < (int)N; i++)

とか書かれていたりする。
これが、なんか出来る人っぽくてカッコいいので自分でも使ってみたくなった。というより、きっと、こういうのは定番なので、ちゃんと技術を盗んでいかねばならないのだ!!


greed.confファイルの作成


Greedの導入時の唯一の設定項目は、workspaceディレクトリを設定することだった。
Greedの設定は、その指定したworkspaceディレクトリ内にgreed.confというファイルを作って行うことになる。なので、とりあえず、空のgreed.confを用意する。


カスタマイズ用のテンプレートファイルの作成

greed.confの次に、テンプレートファイルと呼ばれるファイルを用意する。

Greedは、アリーナから問題を開くことで、ローカルにソースやテストケースのファイルを作成してくれるが、この作成されるファイルのひな形をテンプレートファイルという。

そこで、デフォルトのテンプレートファイルに代えて、自分の好きなテンプレートファイルを作り、そのファイルをテンプレートファイルとして使いますよということをgreed.confで設定してあげれば目的が達成できるようだ。

まず、デフォルトのテンプレートファイル(C++用)の内容は以下の通り。

https://github.com/shivawu/topcoder-greed/blob/master/src/main/resources/templates/source/cpp.tmpl


このファイルをダウンロードして、「my_template.cpp」というファイル名にし、workspaceディレクトリに置く。このmy_template.cppを好きに書き換えることで、カスタマイズをする。


カスタマイズ用のテンプレートファイルとして指定する


先に述べた通り、カスタマイズ用のテンプレートを使うように設定するにはgreed.confに次の一行を書き込む。

greed.language.cpp.templateDef.source.templateFile = my_template.cpp

ここまでで、デフォルトと同じ状態のソースコードが生成される。


C++のマクロ


テンプレートファイルでは、${と}で囲まれた部分が、テンプレートエンジンによって置き換えが行われる部分で、それ以外の部分は、書いたらそのまま出力される。

なので、あまり難しく考えなくても、C++用のマクロは、テンプレートファイル前半部分にべた書きしておけばOK!


以前に紹介した、greedの設定を紹介してくれている人のページを参考にすると、インクルードファイルは#include <bits/stdc++.h>することで、必要そうな色々なものを呼び出してくれるらしいので、それにしてみた。

その他、C++の便利なマクロってどんなのがあるのかな?と思って検索してみると

TopCoderから学ぶ美しいマクロや型宣言 C++

というのが、みつかった。
そこで、初心者でもよく使いそうな奴だけ抜き出して整理してみた。



もっと使いこなせるようになったら、付け足していけば良いのかなと思う。

2014年10月7日火曜日

Greedというプラグイン


土曜日に「今日は思う存分、過去問を楽しもう!」と思ってTopCoderのアリーナ起動したら、過去問の数がいつもと違ってものすごく少ない。なんで??と思ってあれこれみていると、Active Contestsの欄に大会のお知らせのようなものが。

というわけで、TopCoderのSRM大会に初参戦!!

私は、練習問題を解く時には、Arenaで起動されるエディタを使って直接ソースを書いていたのだけれど、他の人のソースを見るとエディタのプラグインのコメントのようなものがあったので、そういうのがあるんだろうなとは思っていた。


Arena用のプラグインGreed


そこで、せっかく大会に出るんだから、環境も適当に整えよう!と思ってネットで検索。
どうやら、Greedというプラグインが評判良いらしい。
https://github.com/shivawu/topcoder-greed

そして、「これいいよー」と紹介している人のページ(日本語)
http://qiita.com/ororog/items/42a9032f20bd9d239f95


上でも書いた通り、SRMの問題に対する回答は、Arenaアプレットのフォームにプログラムを直接書き込むことで提出する。

しかし、このGreedプラグインを使うことで、問題に対する解答のためのソースファイルの雛形がローカル(自分のパソコン)に作成されるので、そのファイルを自分がいつも使っているエディタで編集することが出来るようになる。しかも、このローカルのソースファイルはGreedによってArenaと連動されているので、ファイルがローカルにあるということを意識せず、Arenaアプレット側のコンパイルやテスト、サブミットボタンを押すだけで、通常のアプレット上でのテストやサブミットが行われる。

また、ここで作成してくれるソースの雛形は、問題で指定されている提出用のクラスとメソッドを定義してくれるので、あとは中身を書くだけの状態になっている。そして、このソースはそのまま、ローカルでコンパイルして実行すると、問題に付随してくるテストケースをを試して、その結果を表示てくれるプログラムもつけてくれている。(提出時には、これらテストケースを実行するメイン部分は自動的に省いてくれるので、何も気にすることはない。)

更に更に、問題文をHTML形式にしたファイルもローカルのディレクトリに作成してくれる。Arenaのアプレットで読むよりも、いつも使っているブラウザで見る方が字も読みやすいし、翻訳とかもブラウザからのほうがしやすい。

すなわち、このプラグインは「とっても便利!Greed最高!」なのだ。


SRM初参戦日記


さて、そんな感じに、環境は万全に整ったのは良いが、肝心のプログラミング技術の方が素人。

その日までの間に、Div2 Easyの問題にいくつか挑戦していたが、C++のコンパイルってどうやるんだっけ?から始まって、vectorやstringのメソッドをネットで適当に検索しながらプログラムを書くというレベル、、、大体、問題の英語を読んで、問題を理解するのも時間かかるので、今回の大会は、まずは1問を時間内に解けることを目標にしようと思って、エントリー開始時間を待っていた。


エントリー開始は、午後10時。
同意書みたいなのに同意して、エントリー。

参加者の一覧みたいなのが見れるので、覗いてみると、あこがれのレッドコーダーは日本人にもいっぱいいた。というか、日本人の参加者が結構多いんだなぁという印象を受けた。白色のNON-RATEDの人は多分大会初挑戦なんだろうけれど、その時点では日本人の白色は3人程度で、なんとなく、怖気づく。。

大会開始5分前、午前12時55分頃。
チャット画面では、エントリー締め切りがアナウンスされ、なんとなくチャット画面ごしに参加者達がざわざわしている雰囲気が伝わってくる。

そして、各部屋に移動。Div2のとある部屋に振り分けられた。
午前1時開始なのだが、Arenaで、問題の選択が出来るようになっている。
「このメニューもう触っていいの??時間まで、触らない方がいいのなか?」とかと動揺しつつ、大人しくじっと待つ。

午前1時!!!
問題を開いてみる。Div2Easy、250点問題だ!

一見して、問題文がやたら短い!!
短い英文は、英語が不得意だと逆に分かり辛く、正確な意味がわからなかった。
が、しかし、Test casesをみる事でなんなく把握できた。

コーディングしてコンパイルすると、一発でコンパイル完了。
実行してみると、全部のテストケースをパス!!すぐさま、サブミット。

開始からたぶん15分くらいしか経っていなかった。
「何か奇跡がおこっている!!」
そう思って、今まで練習でも一回しか挑戦したことのない500点問題、div2Mediumを開いた。

問題文の英語はなんとなく理解できた。
さっそくプログラムを書き始めたが、使われている変数の型が「long long」とかなっているのが気になる。

私のプログラム技術はforもしくはwhileで単純に調べて回る全探索しか使えないので、あまり扱う数が大きくなると、単純にプログラムの時間が掛かりすぎて、制限時間オーバーになる可能性が高いという認識があった。

だから、long longみたいに「大きな数」を扱うのはヤバそうだったが、どうしょうもない。

とりあえず、プログラムが書けたのでローカルでコンパイル、そして実行。
案の定、実行時間が2秒を超えるテストケースがあった。つまり、時間オーバーだ。

しかし、どこかのページで「TopCoderのサーバーは、自分達が使っているパソコンより性能が高く早い、、」というのを見たのを思い出し、とりあえず、サーバー側でコンパイルしてテスト。

すると1.6秒くらいで実行できており、制限にかからないようだった。
そこで、「改善する方法探すより、次に行こう!!」ってことで、そのままサブミット。

なんと、未知の1000点問題Div2Hardに辿り着いてしまった。
多分、残り時間30分くらい。

勇敢に開いてはみたものの、問題文が何を言ってるかさっぱりわからない。
何度も読み返しているうちに、いわゆる「木構造」とかいうものの話なのかな?とか、edgeって点を繋ぐ線のことかな?とか、それくらいまで想像しつつ、、疲れて飽きてきた。

多分、これは問題が読み解けたところで、コーディングは全く無理と判断して、のんびり、問題文の意味を考え続けていたら制限時間が近づいてきた。
そこで、とりあえず、Greedが生成した空のソースをサブミットしておいた。

で、制限時間到来!!
5分の休憩時間。

この時、(その部屋の?)順位みたいなのが発表されていた。
ちらっと見たら、私のハンドル名がリストの上から2番目にあったような気がしていた。

暫くして、TopCoderに特有のチャレンジフェーズという、他人のソースを見てバグを発見し、ポイントをゲットする競争が始まった。そして、チャレンジフェーズが始まってみると、一覧のさっきの場所に、私の名前がなくなっていて「ん???」と思った。

私のHardの問題がチャレンジされて撃墜されていたのだ。
つまりは、Hardまでサブミットしていたので、その時点で点数が入っていて、上位に名前があったらしい。

しかし、あっという間の撃墜だった。まぁ、慣れてる人が見て、「こいつ、なめすぎ!!糞ニュービー」っていって、落とされたに違いないwww

チャレンジフェーズは、私も他人のソースをあれこれと眺めみるが、いまいち把握できない。この辺はきっと訓練が必要だ。

で、チャレンジフェーズが終わったら、システムテストが始まって、システム自体がサブミットしたソースを検証してくれる。これにパスすればポイントが確定してレーティングが計算されるみたい。

参加者の結果一覧をみていると、次々とシステムテストに通ったとか通らないとかの表示が出てくる。私の分もチェックされたらしく、何かのウインドがポップアップしていた。あまりよく読んでいなかったけれど、部屋を入りなおすとレイティングが更新されてるよみたいなことが書いてあったんだと思う。
チャット参加者の一覧から人がどんどん抜けていくので、私も追随。

入りなおしてみると、、、、
私のハンドルネームがブルーに!!!!

なんと、「ザクとは違うのだよ、ザクとは」だったのだ。


2014年10月3日金曜日

xmonadとHaskell(その16:レイアウトのスクリーンショット)

拡張モジュールにあるレイアウトモジュールは凄く沢山あるが、幾つかの視点から整理してみる。


基本的レイアウト

単独でレイアウトになれる型のデータを含むモジュール。
重なりか、非表示かがわかりやすい様にターミナルを透明にしてスクリーンショットを取ってみた。

工夫次第で使えそうな勧めレイアウト


XMonad.Layout.OneBig
一つだけ大きく



XMonad.Layout.TwoPane
XMonad.Layout.DragPane
画面を二分割で固定。マスターとそれ以外の2ウインドウ制。それ以外は非表示。
DragPaneの方が縦、横の選択等のカスタマイズができる。



XMonad.Layout.GridVariants
GridVariantsモジュールでは、Tallのメイン部分を任意の固定行x列にした上で、サブ部分がグリッド配置になるようにできたりする。



XMonad.Layout.ThreeColumns
メイン1行、サブ2行の固定



XMonad.Layout.MultiColumns
メイン1行、サブ行どんどん増えるが各行のウインド個数を指定できる



XMonad.Layout.Simplest
メイン1画面固定。
サブは非表示ではなく、メインの後ろに表示されている点でFullと異なる。



XMonad.Layout.StackTile
stacktileはdishesに似ているがメイン部分の高さが固定、サブ部分が増えるとサブの高さが小さくなる。



Tall改良版

hintを重視(文字がちゃんと表示される高さとか)

XMonad.Layout.FixedColumn
大きさ等指定を割合じゃなく文字数で

XMonad.Layout.ResizableTile
サブ側の高さがリサイズ出来る


その他のレイアウト

XMonad.Layout.Accordion
複数ウインドを開くとフォーカスのあるもの以外帯状に縮んだ状態になる。



XMonad.Layout.Circle
マスタが真ん中に、サブはその後ろで円状に配置



XMonad.Layout.Cross
マスタが真ん中に、サブはその後ろで十字形状に配置



XMonad.Layout.Roledex
斜めに綺麗に並べられる



XMonad.Layout.Spiral
渦巻き状にタイリング



XMonad.Layout.Mosaic
XMonad.Layout.MosaicAlt
各ウインドウの面積がある一定の法則になってる?


XMonad.Layout.Column
隣接ウインドウとの高さの比を規定



XMonad.Layout.Grid
XMonad.Layout.HintedGrid
Grid系は規則正しく格子状になるように配置をする。



XMonad.Layout.Dishes
メインの下にサブがお皿の用に積み重なっていく。



デコレーション系

xmonadでもタイトルバー的なものを付けることも出来るし、マウスによるボタンクリックによるウインドウ操作も可能にできる。

XMonad.Layout.DecorationAddons
XMonad.Layout.ButtonDecoration
XMonad.Layout.ImageButtonDecoration
各ウインドにバーを付ける



XMonad.Layout.TabBarDecoration
レイアウトにタブを追加する



XMonad.Layout.DwmStyle
各ウインドにDwmスタイルのタグを付ける



XMonad.Layout.DecorationMadness
幾つかのレイアウト(circle,accordion,tall)に飾りを付けたものを提供してくれる


XMonad.Layout.Decoration
テーマやシュリンカをカスタマイズする時のデフォルト値とか


    TopCoder

    本屋さんで「最強最速アルゴリズマー養成講座」という本を買ってみた。

    別に「アルゴリズマー」になろうとしたわけではなく、世の中には「プログラムコンテスト」なるものがあって、その筆者曰く、初心者こそ参加すべきという文言に目が留まったからだ。

    しかし、それよりもなによりも、そのコンテストは「TopCoder」といわれるものなのだが、このコンテストの優秀者(トップ0.2%)達は「RedCoder」と呼ばれ、これまた筆者曰く「『"赤いヤツは3倍早い"』というのはアニメだけの話ではありません。Redcoderは、素早くしかし華麗なコードを書き上げ、Challenge phaseでは容赦なく他人を撃墜していく存在であり、参戦者からすると恐怖の対象でもあります。」とかいう文句に心躍らされてしまった。

    昭和世代のおっさんは、アルゴリズマーであろうがなかろうが、少なくとも皆「ガンダマー」

    なので、参加しないわけには行きません。
    そう、「ザクだからって、なめるな!」なのです。


    http://www.topcoder.com/


    先の本が書かれたころよりも、ページが進化しているらしい。
    とりあえず、「Arena」に行くためには、ページ上段に並ぶ「challenges」からドロップダウンされるメニューの一番下「Topcoder arena」をクリック。

    ContestAppletProd.jnlpとかいうファイルがダウンロードされる。

    さて、windozeの場合、JREがインストールされていれば、このファイルをダブルクリックするなりでArenaが起動するが、archlinuxの場合は、すんなりいかないこともあるので、幾つか確認。


    1. icedtea-webパッケージのインストール
    *.jnlpというのは、JavaのJava Web Startという仕組みを使うらしく、そのために必要なパッケージが「icedtea-web」らしい。

    http://d.hatena.ne.jp/pogin/20120331/1333222488

    そのページを参考に

    #pacman -S icedtea-web

    で、インストール。

    そして、ダウンロードしたContestAppletProd.jnlpを以下のように実行。

    $javaws ContestAppletProd.jnlp

    セキュリティーの確認画面がいくつか出て、了解していけばArenaが立ち上がる。


    2.xmonadとjavaアプレットのFAQ

    xmonad上で、javaのアプレット扱う時にはFAQがある。
    何も設定しないと、アプレットに何も表示されない状態になって、びっくりしてしまうので、以下のページを参考に設定しておくのを忘れずに。

    http://qiita.com/xorphitus/items/efcca6652558bc5cc785


    #include XMonad.Hooks.SetWMName
    defaultConfig {startupHook = setWMName "LG3D"}

    みたいにstartupHookを設定しとけばOK(インクルード忘れずに)