プログラミングコンテストチャレンジブック2ｰ1

プログラミングコンテストチャレンジブック

初版。
自分の勉強メモ。*1
公開しちゃだめだと思うし、GitHubとかブログとかにコードはあげない。
やってみて、やっぱり二つ以上の言語で*2書いてみるのがいいような気がした。

2-1全ての基本 "全探索"

再帰関数

• 慣れてる（はず）
• 数列の定義通りに書くとすぐ遅くなる。配列にメモしておくことで効率よくできる。

→メモ探索や動的計画法で使う考え方

スタック

• C++やJavaの標準ライブラリに最初から用意されてる
• ギモン：

stack::pop

と

using namespace std
s.push

は何がどう違うの

(20121014追記)
今このエントリ見返したら、ここで疑問だといってるのが何を疑問に思ってたのかがわからなくなってしまった・・・
仕事関係でC++をかじったらこのへんわかったから削除ー
(追記ここまで)

キュー

スタックに同じ

深さ優先探索

• 再帰関数を使うと簡単に書けることが多いよ
• ギモン：配列で

int n = 4;
int a[n] = {5,6,7,8}

とか書いて

variable-sized object 'a' may not be initialized

って怒られてる。

幅優先探索

• 最短経路とか最短手数とか簡単に求めることができるよ
• C++の"typedef"ちょっとググろう*3
• （この探索に限らず）ちょっとOCamlとかで書きなおさないとスっと入ってこない
• 幅優先探索も深さ優先探索も、たどり着ける全ての状態を生成する。でも再帰関数とか使いたいから深さ優先使うことが多い

特殊な状態の列挙

• next_permutation（C++の標準ライブラリにある関数）

枝刈り

• 全探索なんてやってられないことも、あるよね
• でもコンテストだと枝刈りが必要な問題が出ることは殆ど無いらしい。むしろアルゴリズムを見なおしたほうが。*4

*1:アルゴリズムというよりC++に触れるための勉強みたいになってるけどね！

*2:パラダイムの違う言語で

*3:そもそもシンタックスをよく知らない

*4:これ本当？