僕用の競プロマクロまとめ
ひさびさなブログ更新な気がする。今日は僕が競プロで便利だなと思うマクロ置き場としてブログを使う。
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<map> #include<string> #include<algorithm> #include<functional> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define INF 1<<30 #define MP make_pair #define mp make_pair #define pb push_back #define PB push_back #define DEBUG(x) cout<<#x<<": "<<x<<endl #define ll long long #define ull unsigned long long
これらの何がいいかって言うとよく有るiとjを間違えてエラーチェックに時間がかかると言ったヒューマンエラーを減らせる点だとおもう。あと手が疲れない。pair
端末Vimでマウスを使う話
こんにちわ、お元気にしているでしょうか、私は元気です。
今日も今日とてvimの設定をいじってたりします。
最近したのはMacVim+日本語化パッチを導入したこととかですね。まず、いままでなんでデフォのVimを使っていたかはおいといて、補完機能に優れるというNeoCompleteという有名なプラグインを入れたんだけど、Vimのバージョンが古いと怒られていれた訳です。
まあそこまでは良かったんだけど、MacVImマウスが使えていいのだけれど、よくフリーズする。多分どこかの何かが干渉してるんだろうけど原因がよく分からない。でも、ターミナルなら動く←ターミナルでよくない？という話に。でもやっぱりターミナル上でマウスが使えないのは画面分割とかしたときにサイズ調整がすごくめんどくさい。という訳でマウスを有効にしましょうという話。
今回参考にしたのは以下のサイト
・端末vimでマウスを使う - Keep It Simple, Stupid
・河西 高明 Tech Blog: Macのターミナル上のvimでマウスホイールスクロール
はい、大変参考になりました。
まずぼくは勘違いしていたのは
・VImがマウス対応したのでコンパイルされてないといけない。
・そもそもMacのターミナルはマウス操作が有効ではない
の二点。それを解消するには、
easySIMBL, MouseTermをインストール（これらはターミナルの拡張のため）
~/.vimrcに以下の文を挿入
mouse=a
ttymouse=xterm2
これで晴れてターミナルでマウスが使えるし、もうGVimいらねえ。
まあ、なんで僕がGVim使わないのかってのは単純にターミナルになれてしまったのと、gvimはvimが開かれるからVimShellとかを経由しないとコマンドができないこと。VimShellPopとかがエラーしたりなんとなくプラグインと相性がよくなさそうっての、その他にも連続で同じファイルを開きたいときにいちいち GUI起動するのめんどくせえってのと¥と\が区別されてる文字コードっぽくて改行とかがめんどくせえっていう理由。
今はQuickRunを使ってるけど、競プロとちょっと兼ね合いが悪い（入力が与えられるので<=""見たいにやるのはちょっとめんどくさい）からEmacsのQuickRunみたいにファイルから標準入力を受け付けられるって方式のプラグインを作るためにVimScriptのお勉強してます。
続Project Euler
というわけで前回に引き続いて、Project Eulerについて書いていきたいと思いまし。
今回は良さげだと思った問題をあげていく。まあこういうのもアレなんだけれどProjectEulerにはよさげな問題とだるい系の問題があるので良さげな問題を列挙する。
・Problem3 シンプルに素因数分解をするだけ。でもアリゴリズムの勉強になるし素因数分解系の問題は多いので触れるべし。
・Problem5 これは愚直にやると死にそうになる。素因数の個数を求めればいいんだけど、アレをやると数式一つでいけるのはおーって思った。
・Problem14 題材はコラッツ数列。メモ再帰するのがよいかな？
・Problem16 unsigned long longしても足りないので多倍長を自作。多倍長使わせることが多いからなれておこう。
・Project18 メモ化再帰、DPどちらでもどうぞ。僕はそのときDPを知らなかったから、ケツから解くって解法だった。
・Problem21 友愛数が題材。約数だから素因数分解の延長
Problem25までしかといてないからおすすめはこれぐらい。ちなみにC++で解いてるけど何でもいいと思う。最近思うのはSTL便利って話。あとコンパイラによっては定数じゃなくても配列をとれるって話。
Project Eulerはじました
今日でゴールデンウィークが終わってしまう訳だけれど、僕がこの連休中何をやっていたかというとProjectEulerを解いたり解かなかったりしていた訳で。
ProjectEulerを知らない人も多いだろうから簡単に説明すると、プログラムで数学を解くコンテストみたいなものだ。（僕はサブミットしてないのでよくわからない）問題は英語だけれども和訳したものも乗っているし問題が理解できないなんてことはないと思う。
ここで簡単な例をだそう。
『1000未満で3の倍数または5の倍数のものの総和を求めよ(Problem 1)』
まあ、愚直にやるなら1000回ループをまわして条件を満たしたら足してやればいいだろう。でもこれはあんまりいい手じゃない。O(n)だから十分動くのだけどO(1)にすることができる。その方がスマートだ。ここでは回答については触れないけど、高校数学を見返したら回答がのってる。
まあこんな感じの問題をやっている訳だけれど、競プロっぽくもあり競プロっぽくないとこもある。競プロっぽいなあと思うところは
・再帰的な手法を使う
・オーダーに気をつけないと計算時間が跳ね上がる。
逆に競プロっぽくないと思うのは
・多倍長ばりばりの問題がでる
・入力が定数
・数学的素養？
まあなかなか面白い問題があるからやってみてもらいたい。
セルオートマトンとトキシック
昨日から今日にかけて久々に所属サークルっぽいことをした。久々にプログラムを組んだら無限に時間が溶けた。まだ作品とか実験とか形のあるものならいいのだけど、某情報演習みたいなクソみたいなプログラムを延々を書くのはさらに生産性がない。プログラムを書くプログラムが欲しくなる。しかも構文の指定が有るから自分の好きなように書くことができないのがストレッサーだ。
話が脱線したけど、今回作ってるのはセルオートマトンだ。セルオートマトンというのは、まあググってほしい。今回は六角形で34/2の形態をとってる（これはWikipediaに資料があったためだ）一見適当に見える34/2だけれどこれを変更してみるといかに絶妙なバランスなのかがわかる。
例えば23/2にしてしまうとあっという間に定常的な状態になって動きがなくなってしまう。これは隣接セルとの結びつきが強くなりすぎてしまうためだ。かといって34/4なんかにしてしまうとすぐに死んでしまう。こういうのをclass1とかclass2とかいう。かといって適当に値を設定すると全くのでたらめになってしまう。完全に乱雑で規則もへったくれもない。これがclass3。局所の影響が全体に広がり周期的な側面もみせる、そんないい感じなのがclass4という分類だ。
class4はめっちゃ貴重な存在だ。昔の研究者はこのような状態を複雑な生命現象を引き起こす源だと考えたそうだ。実際セルオートマトンは拡散方程式や流体のモデリングとして使われたりする。
で、今回作成してみたHex34/2だけどグライダーのような移動物体は生成されないっぽい感じがする。これは単なる推測だけど、六角形2状態だと対称性が強すぎて移動物体にならず周期的なものになってしまうのだろう。まあ、それでも対称性を生かしたような綺麗なパターンや周期はできたのでよしとする。見ていると万華鏡のようで一種の電子ドラッグ感がある。あと、ずっと細かい六角形を観察してたから目が錯覚でやられた感じになる、正直目の毒でもある感じだ。
