プログラミングコンテストチャレンジブック第1章その1

今日からがらっとかわってこの本を読みます。第1章は各種プログラミングコンテストの紹介や参加方法などの紹介と、本書内でのルール(入力の取り込み部分は省いて変数に格納された状態とする)などの説明でした。

あと計算量のオーダーについての説明もあってそこの目安がおもしろいです。

実行時間制限が1秒のとき。O(n^2)のアルゴリズムでn>=1000だとしたら n^2 = 1,000,000
- 1,000,000 - 余裕を持って間に合う
- 10,000,000 - おそらく間に合う
- 100,000,000 - 非常にシンプルな処理でない限り厳しい

こういうざっくりした評価の尺度を載せているのははじめて読みました。もちろん計算機の速度や処理内容によって違ってくるでしょうけどだいたいの感覚はこんなものなんですね。

あとはウォーミングアップの問題。三角形の問題はとても単純なのですぐ終わりました。明日は POJ の Ants からやります。