Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Arduino

オライリーの新着情報で「Arduino」というものを知りました。

Prototyping Lab――「作りながら考える」ためのArduino実践レシピ

これはちょっと面白そうと思っていたところで,今度は「大人の科学」で"8ビットマイコン"というキーワードを見つけ,昔AKI-80でZ80のコードを書いたなぁということを思い出しながら,惹かれるままに公式サイトを見てみました。

大人の科学 vol.27

偶然にも,ここでも「Arduino」という単語が!これはもう買うしかないかなと。しかも昨日が発売日とのこと。
しかしながら,いまAmazonを見たら,まだ注文受付が開始されていませんでした。orz
明日あたり,ちょっと本屋を覗いてこようかと思います。


5/17追記
とりあえず地元の本屋で買いました。まだ開けていません。
amazonは売り切れのようですね。

スポンサーサイト

Google Code Jam 2010 Qualification Round

Google Code Jam への参加も2回目となり,だいぶ手馴れた感があります。Code Jam用のC++スケルトンコードも熟れてきました。

今回は予選ということで手を抜いてメモを取らずに頭の中で考えることとしたら,条件の考慮の抜け漏れが出てしまい,正解へ辿り着くまでに何回かのチャレンジを必要としてしまいました。英語を読み進めることに必死となり,読み取った条件が頭の中から抜けていってしまう傾向があるようです。次回のラウンドからは,しっかりとメモ上で検討を進めようと思います。

問題A

問題Aは,問題文の解釈に時間を取られました。初めは,Snapperがlightの機能を持っていると思い込んでしまい,問題文の解釈に苦しみました… "The light is plugged into the Nth Snapper"が目に入ってこなかったようです。
私の採った解法は,まずN番目のSnapperが初めてONになるまでを考えました。NがONになるには,n番目(1<=n<=N)がONになる必要があり,n番目がONになるには,n-1番目がONになってから2^(n-1)回のsnapが必要です。すなわちΣ 2^(n-1)回となります。そしてN番目のSnapperが一度ONとなった後に再度ONとなるのは,2^N 回後となります。こんな考えで実装してみました。
後ほど,2chに「1行で書ける」とあったので考え直してみたら,Σ 2^(n-1) = 2^N-1であり,そこから2^N回毎ということは,「snap回数 % 2^N = 2^N-1」が成立すればよいことに気づきました。

問題B

問題Bは,数学的なひらめきが必要そうでしたがすぐにひらめかず,またlongを解くには多倍長演算が必要であったので,パスしました。多倍長演算は「プログラミングコンテストの数学」の中で準備しておこうと思っていたのですが,面倒になって後回しとしていました。こんなことなら確認しておけば良かったと・・・

問題C

問題Cは,ローラーコースターの乗車をR回試行すれば良さそうですが,愚直に毎回乗れる人数を算出すると時間切れになりそうなので一工夫必要です。乗れる人数は,どのグループが先頭になるかで決定的な値となるため事前に計算しておきます。このようにすれば試行ループの内側は配列参照と加算で済み,ループ回数Rの最大値は10^8なので,十分に間に合います。

Round1-Aは,5/22(土) 10:00 から。今年はなるべく早いRoundでの勝ち抜けを目指します。

プログラミングコンテストのためのSTL復習

TopCoder SRMやGoogle Code Jamのような短時間勝負のプログラミングコンテストにC++で挑むのであれば,STLを使いこなせることは必須であると言えます。しかしながらSTLは普段使うことが少ないため,いざ使おうと思っても仕様の詳細を思い出すことができず,使えない(もしくは回りくどい別のコードを書く)ということがよくあります。

プログラムコンテストでよく使いそうな事項を調べなおしてみましたので,メモしておきたいと思います。

多次元配列

初歩的な事項ですが,多次元配列はvector<>をネストさせて定義できます。例えば,vector< vector<int> >のよう。

▼初期化
多次元配列の初期化(初期サイズ設定)は次のコードで行えます。v[10][20]の配列となります。

vector< vector<int> > v(10, vector<int>(20));

▼初期値
初期値の設定が必要であれば,次のように書けます。nの値で初期化されます。

vector< vector<int> > v(10, vector<int>(20,n));

▼3次元配列
3次元配列であれば,次のようになります。v[10][10][10]の配列となります。

vector<vector<vector<int> > > v(10, vector<vector<int> >(10, vector<int>(10)));

▼assign()
vectorのメソッドassign()は配列(サイズ,初期値)を(再)設定するもので,上記のコンストラクタの引数と同一のものを指定できます。実行結果はコンストラクタで作成したものと同じ形となります。

vector< vector<int> > v;
v.assign(10, vector<int>(20));

lower_bound, upper_bound

lower_bound(), upper_bound()の定義は次のようになっています。

▼ lower_bound(first,last,val)の定義
   [first,i) の範囲の iterator j で *j < val となる。iterator i を返す。

▼ upper_bound(first,last,val)の定義
   [first,i) の範囲の iterator j で val < *j が false となる。iterator i を返す。

これでは良く分かりませんので,もっと直感的な理解を考えたいと思います。

lower_bound(), upper_bound()を把握するには,equal_range()を理解すれば良いようです。equal_range()は,lower_bound(), upper_bound()の結果をpairで返します。

equal_range(v.begin(), v.end(), 2)
  v : 0, 0, 1, 1, 1, 2, 2, 2, 2, 4, 5, 6
                     ↑          ↑
                   lower        upper
equal_range()は,配列(シーケンス)における指定値と同じ値の範囲を返すと考えれば良いようです。指定した値(上記例では2)は,[lower_bound, upper_bound)の範囲にあることになります。

指定した値が配列に含まれていない場合は,lower_bound = upper_bound となります。 例えば,上記の例で3を指定した場合は,lower_bound, upper_boundともに4の位置を返します。

lower_bound(), upper_bound() のその他留意点を纏めておきます。

  • lower_bound(),uppper_bound()は2分探索である。シーケンスはソートされてなければならない。
  • 連想コンテナ(set,map等)は,メソッドとしてlower_bound(),upper_bound()を具える。
priority_queue

priority_queue はヒープ構造を構成します。操作と計算時間は次のようです。

操作計算量
void push(value_type& x)O(log(size))
void pop()O(log(size))
value_type& top()O(1)

最大値(最小値)を定数時間で取得できます。

priority_queueの標準動作は,値が最大のものをtop()で返します。最小値が欲しい場合は,比較演算子を指定しておきます。

priority_queue<int, vector<int>, greater<int> > min_que;
デフォルトがless<int>なので,最小値のときは反対の演算子を指定します。

next_permutation

next_permutation()は,辞書順で次に大きいシーケンスに並べ替えます。 next_permutation()の動作は次のようです。

  • 次に大きいシーケンスがない場合はfalseが返り,辞書順で最小のシーケンスに並べ替えられる。それ以外はtrueが返る。

コード例:

sort(index.begin(), index.end()); // ソートされていないと全件回らない
do{
   ・・・ // index[] を使った処理
}while( next_permutation(index.begin(), index.end()) );

挿入と削除

insert(iterator pos, const T& x)メソッドは,posの前にxを挿入する。

erase(iterator pos)メソッドは,posを削除する。

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。