社会人になってから始めるTopCoder
これはCompetitive Programming Advent Calendarの11日目の記事です。
Advent Calendarには入門記事が意外となさそうなのと、自分自身初心者なので、紹介記事を書きます。
きっかけ
今年の4月から競技プログラミングをはじめました。「人材獲得作戦」や「コーディングスキル判定」をやってみたらめちゃくちゃ時間がかかったりして漠然とどうにかしたいなと思っていたところ、Google Code Jam勉強会というのを取引先の人から教えてもらい参加しました。問題が面白いし、あまりにもコードが書けないのでTopCoderに登録してそれ以来はまっています。
TopCoderとは
競技プログラミングは文字通りプログラミング能力を競うものです。TopCoderは競技プログラミング環境を提供する会員制サービスで、要は、コーディングの速さと正確さを競うオンラインゲームです。
競技プログラミングサイトはいくつかありますが、以下の理由でTopCoderがお勧めです。
- 競技時間が比較的短い
年をとると集中力が続かないので短いほうが良いです。 - 頻繁に開催される
参加できる日は多いほうが良いです。 - 順位づけされる
個人練習より刺激になります。 - 履歴が充実している
問題の解説や、他の人が書いたコードを読むことができます。 - 参加者が多い
色々な方法で解いている人を見つけることができます。
はじめかた
ユーザ登録して、プラグインをインストールすれば誰でも参加できます。こちらの記事が大変参考になります。
- TopCoderで2年間プログラムしてみた
ニコニコ生放送で精力的に活動されている診断人氏。TopCoderとは何なのか、どういうスキルが必要で何が身につくかが解説されてます。 - 社会人からのTopCoder SRM参加のススメ
社内で一緒にやる人がいると始めやすいです。
参戦するまでの流れですが
- ブラウザにJava Runtime(JRE)をインストールする
- http://community.topcoder.com/tc でユーザ登録する (例えば pokutuna氏の解説記事)
- 上のメニューの「Algorithm Competitions」からARENAを開いてログインする
- プラグインをダウンロードして設定する (こちらを参照)
必須ではないですがおそらくほとんどの人が入れています
なおTZTesterについては更新版のほうがお勧め (例えば nitoyon氏のもの) - メニュー「Practice Rooms」から「SRMs」をクリックすると、部屋の一覧が出てくるので、適当な番号のDiv2というやつを選ぶ
- まんなかへんの「Coding Phase」の「Select one」の250を選ぶ
- 解いてsubmitする
- 2〜3問解いてみて感触がつかめたら、本番参戦
- 撃沈したら「プログラミングコンテストチャレンジブック」(通称蟻本)を買って読む
こんな感じです。
ちなみに「はてな」には「TopCoder部」というグループがあり、TopCoderの日記はそちらに書いています。
FAQ1 難しそう
Div2のEasyの問題は易しく作られていますので、がんばれば解けるかと思います。そのほかはまあ難しいです。でも楽しいです。
私は適当にぐぐって、当たって砕けろ的なゆるい感じではじめました。事前の準備を真面目に考えると、学ぶことが多すぎて尻込みしてしまうと思います。
FAQ2 英語が読めません
「競技プログラミング(主にTopCoder)に参加しない理由」を見ると英語だから敬遠している人も多いようです。私も英文を読むのが得意ではなく、最初の2〜3回は問題文を読むのに10分くらいかかっていました。
これは慣れるしかないのですが、おそらく10回くらい参加するとどういう意図の問題なのかはなんとなくつかめるようになってきます。20回くらい参加しましたが、最近は英文であること自体がボトルネックになることは減ってきました。題意が何かをつかめない問題もあるのですが、たぶん日本語になっていても同じだと思います。
日本語でないといやだという方には、AOJという素晴らしいサイトがあります。
FAQ3 時間帯が合いません
TopCoderが開催されるのは、(1)平日の10:00から(2)深夜の01:00から(3)土曜日、が多いようです。平日の10:00は社会人には難しいと思いますが、プログラマであれば、勉強したいのでと上司にかけあってみるのも手かと思います。もし裁量労働であれば1時間くらい都合をつけるのは可能ではないでしょうか。
FAQ4 競技プログラミングって役に立つの
業務でのコーディングに直結することはあまりないかもしれません。でも楽しいです。
トレードオフを意識してコードを書くという点では業務のコーディングに近い面もあります。
100行くらいのコードで色々な問題が解けるというのが競技プログラミングの素晴らしいところで、エラー処理や保守性というような観点で見るものではありません。1000行の仕様書を読んで10000行のテストコードを書かなければいけないとしたら萎えますし。
FAQ5 学生に勝てません
学生には勝てません。Twitterを眺めていると、最近の学生はよく勉強していて優秀だなあというのがよくわかります。学生の知識の1/100くらいでも吸収できればだいぶ実力がつきます。
FAQ6 レッドコーダーってどのくらいすごいの
TopCoderではレーティング(≒実力)により色分けされていて、赤が最上位です。目安としては、色が一段階違うと、同じ問題を解く速さが2倍くらい違います。色が二段階違うと、質的に難しい問題に取り組んでいます。
私はこの前ようやく青くなりました。まだまだですね。
参考: Petr伝説
CygwinかVMwareか
良い記事
- http://d.hatena.ne.jp/takuya_1st/20111121/1321865738
- http://d.hatena.ne.jp/takuya_1st/20111123/1322068116
そんな私はPutty + VMware Workstation派。
Cygwinだと困ること
ビルドできないものがあるのと、web開発だと、リリース環境との違いを意識するのが面倒。
ビルド速度については、coLinuxより速いケースもあるし、個人的にはCygwinを導入しない主因ではない。
それよりも色々気をつけないといけないという気がして、安心感がいまいち足りない。
なんだかんだでVMwareは楽。電車の中でもデバッグできるしスナップショットもある。
サスペンドすると接続切れる問題
これは重大。うろ覚えだが、Windows XP + VMware Workstation 5/6のときは、host onlyまたはNATにしていれば、ホストとゲストのSSH接続は切れなかったような記憶がある。
これがWindows 7だと、待機状態から復帰すると全ての接続が切れてしまいげんなりしていた(VMware Workstation 6と8で確認)。
が、試しにVMwareのNATの設定にあるゲストOSへのポートフォワーディングを設定して、そこ(127.0.0.1)へSSHを張ってみたところ、切れないことが判明。すごく快適になった。
PuTTYやPoderosaではポートフォワーディングできない
誤解。
むしろ、PuTTYのほうが、ポートフォワーディング先がいくつかあるとき(例えば会社では直接つながるけど、自宅では会社経由でつなぐとか)に、GUIで手軽に選べると思う。
怠惰なのでクリックして選びたい。ユーザ名とかFQDNを入力したくない。
PuTTY 0.61
なんとPuTTYは四年ぶりにバージョンアップしていて、Windows 7のタスクリストに対応している。
これがあると(設定画面を経由せずに)セッションを直接選べる。
Windows Vistaまでは、スタートメニューと同列にフォルダを作成しておいて、セッションのショートカットを置けばよかった。(画像左側)
Windows 7からはこれができないようなのだが、タスクリストに入れると近い感じになった。(画像右側)
スタートメニューにPuttyを表示させておいて、右端の矢印をクリックすると、Recent Sessionsなどが選べる。矢印をクリックしないといけないのがやや面倒ではある。
Recent Sessionsだと順番がばらばらなので選びづらいが、右クリックして「いつも表示」を選べば順番が固定されるのでましになる。
Explorer++ patch for TortoiseSVN
Windows環境をx64に移行したら、TortoiseSVNのオーバーレイアイコンに対応したファイラーが見当たらず、やや不便。
幸いExplorer++というソースが公開されているものがあったので、アイコンを更新するようにしてみた。
diff -Naur org/Explorer++/ShellBrowser/DirectoryModificationHandler.cpp new/Explorer++/ShellBrowser/DirectoryModificationHandler.cpp --- org/Explorer++/ShellBrowser/DirectoryModificationHandler.cpp 2011-04-23 07:43:20 +0900 +++ new/Explorer++/ShellBrowser/DirectoryModificationHandler.cpp 2011-08-27 02:41:54 +0900 @@ -448,6 +452,10 @@ } FindClose(hFirstFile); + + if (!bFolder) { + RenameItem(iItemInternal, FileName); + } } else {
ついでに、ドラッグアンドドロップを禁止してみた。フォルダをクリックしようとして移動してしまうことがあるので。(というかそれを防ぐためにファイラーを使っている)
diff -Naur org/Explorer++/Explorer++/ListViewHandler.cpp new/Explorer++/Explorer++/ListViewHandler.cpp --- org/Explorer++/Explorer++/ListViewHandler.cpp 2011-08-15 00:19:54 +0900 +++ new/Explorer++/Explorer++/ListViewHandler.cpp 2011-08-27 01:20:05 +0900 @@ -1384,6 +1384,9 @@ HRESULT Explorerplusplus::OnListViewBeginDrag(LPARAM lParam,DragTypes_t DragType) { +#if 1 + HRESULT hr = DRAGDROP_S_CANCEL; +#else IDropSource *pDropSource = NULL; IDragSourceHelper *pDragSourceHelper = NULL; NMLISTVIEW *pnmlv = NULL; @@ -1491,6 +1494,7 @@ } CoTaskMemFree(pidlDirectory); +#endif return hr; } diff -Naur org/Explorer++/Explorer++/TreeViewHandler.cpp new/Explorer++/Explorer++/TreeViewHandler.cpp --- org/Explorer++/Explorer++/TreeViewHandler.cpp 2011-04-26 11:51:32 +0900 +++ new/Explorer++/Explorer++/TreeViewHandler.cpp 2011-08-27 01:21:19 +0900 @@ -635,10 +635,12 @@ return OnTreeViewKeyDown(lParam); break; +#if 0 case TVN_BEGINDRAG: /* Forward the message to the treeview for it to handle. */ SendMessage(m_hTreeView,WM_NOTIFY,0,lParam); break; +#endif case TVN_GETDISPINFO: SendMessage(m_hTreeView,WM_NOTIFY,0,lParam);
ThinkPad T420購入
Sandy Bridgeに期待して購入。スペック
- Core i5 2540M 2.6GHz
- video 1600x900 Intel HD Graphics 3000
- memory 8GB (追加)
- SSD Intel SSDSA2CW300G3 300GB (置換)
エクスペリエンス インデックスは 7.1/7.4/5.9/6.3/7.7
なんかキー入力がひっかかるなあと思っていたら、特定のキーが入力されたりしなかったりするという初期不良だった。サポートに電話したら、代わりのキーボード(部品)を送ってくれて翌日届いた。不良はさておき、部品単位で送ってくれるのは大変ありがたい。
元々の部品はChiconyの45N2172だったが、届いたのはNMBだった。ブログとか見ると評価は ALPS>NMB>Chicony の順らしい。正直違いはわからないが、とりあえずNMBはThinkPadらしい打ち心地で、良い。
唯一の問題は、上段のキー配列が変わってしまったので、F2を打とうとするとF1が入ってしまうこと。あとEscキーが無駄にでかい。
T420sではなくT420にしたのは
- 2.5kgくらいまでなら許容範囲
- 薄型はファンがうるさいのでは
という理由。T420は常にファンは回ってはいるが、低負荷では無音といっていいレベル。
ここ http://www.lenovo.com/psref/pdf/tabook.pdf 見るとT420はT410より軽いとなっているが、誤記かも。
ホイールスクロールすると少しノイズが出る。グラフィック由来と思われるのでたぶん回避策はないが、ブラウザとかでは出ないので、普段は気づかない。
タスクマネージャーで見たらSynTPEnh.exeとかいうのが150MBくらいメモリを消費していたので、削除してTrackPointのドライバに差し替えてみた。なんかメモリリークで修正済みたいだが、タッチパッドを使うことはないので古きよきt4p*.exeで十分だ。
その他
PHPのunserializeとjson_decodeの速度を比較してみた
serialize後の文字列には長さが格納されている。一方、jsonは終端文字の検出が必要である。
そのため文字列が入っていた場合はunserializeの方が速いはず、という予想を立てて比較してみた。
数値の場合
配列に数値を格納。
10/100は10個の配列に100までの数を格納。
関数 | 10/100 | 100/10000 | 1000/1000000 |
serialize | 0.002965 ms | 0.026016 ms | 0.175710 ms |
unserialize | 0.002285 ms | 0.019043 ms | 0.139641 ms |
json_encode | 0.001065 ms | 0.008745 ms | 0.045797 ms |
json_decode | 0.002701 ms | 0.018625 ms | 0.192634 ms |
文字列の場合
連想配列に文字列を格納。
10/10は10個の配列に長さ10の文字列を格納。
関数 | 10/10 | 100/100 | 1000/100 | 100/1000 |
serialize | 0.002051 ms | 0.023947 ms | 0.221336 ms | 0.078479 ms |
unserialize | 0.002071 ms | 0.022763 ms | 0.335602 ms | 0.038826 ms |
json_encode | 0.003094 ms | 0.112962 ms | 1.140379 ms | 0.961482 ms |
json_decode | 0.004587 ms | 0.136636 ms | 1.447683 ms | 1.014543 ms |
環境はPHP 5.3.3-7+squeeze1 / core2duo E8600
予想通り、文字列の長さが長くなるほど、json_decodeよりunserializeの方が速かった。
ソース: https://github.com/firewood/test/blob/master/serialize_bench.php
WinDiffを少しだけ改良してみた
WinDiffは10年くらい使っていて慣れているのだが
という問題があった。
WinMerge使えばよいという話ではあるのだが、
- 何文字目から変化しているのか、ぱっと見わかりづらい
- 左右分割なので、diffっぽくない&桁数が減る
- 常に外部エディタで編集したい(右クリックメニューが遠い)
とかいう理由で、WinDiffを改造したほうが、慣れたインターフェースにできそうだったのでチャレンジ。
古いWinDiffはVisual C++ 6.0に付属していたような気がするが、これはバグっていて、右クリックメニューもない。
新しいものがPlatform SDKのサンプルに、SDKDiffという名前で付属していたので、これを使うことにした。
ちなみに最新版ではない(Vista用のものにはもっと細かいメニューがある)が、個人的には困っていない。
ライセンスについては、MSDNに「サンプルコードのうち、特記のないものはMICROSOFT LIMITED PUBLIC LICENSEに従う」という記述があったので、公開しても良いと判断した。
著作権表記と、プログラム名はそのままにする必要があるという認識です。
変更点は以下のとおり。処理はてきとーそのものです。
福島第一原発の水素爆発についてのメモ
原子力安全・保安院の会見を見てもよくわからなかったので、以下を見て理解した気になってみた。
- 3/18「福島原発事故の現状について」@原子力情報資料室
- 福島第一原発で何が起きているのか
- 福島原発問題について(科学者の眼)
- MIT原子力理工学部による1、3号炉の水素爆発に関する解説
- 原発がどんなものか知ってほしい
- 福島第一原子力発電所 設備の概要