蟻本 - 擬音Wiki

1章

1-1 プロコンとは

2つの要素の複合競技

• 効率的で正しいアルゴリズムを考える
  • 柔軟な発想力
  • 基礎的なアルゴリズムの知識
• それを正しく実装

1-2 どんなものがある

• Google Code Jam
• TopCoder
• ACM/ICPC
• JOI/IOI
• オンラインジャッジ
  • PKU Online Judge
  • Aizu Online Judge
  • Sphere Online Judge
  • SGU online judge
  • UVa online Judge
  • Codeforces

1-3 この本での進め方

1-4 解答の提出方法

1-5 効率的なアルゴリズムを目指す

計算量

実行時間

計算量だけで決まるわけではないが、ループ中の処理の複雑さによる差はたかだか数十倍程度
一方、n=1000ならO(n^3)ののアルゴリズムとO(n^2)のそれは単純に考えて1000倍違う
つまり実行時間を短くするためにはアルゴリズムの計算量が重要
実行時間が1秒の場合

1,000,000	余裕
10,000,000	多分大丈夫
100,000,000	険しい

1-6 ウォーミングアップ

簡単な問題

http://poj.org/problem?id=1852
考えられる解法…全探索(すべてのアリの向いてる方向を全通り試す)
全探索→再帰関数など.
but アリの向き得る方向は2通り、n匹いたら2^n通り→指数時間のアルゴリズム(大きな入力は処理できない)
より効率的な解法を考える.
最小の時間→すべてのアリが近い方の端に向かう
このとき2匹のアリは出会わないし、これより早くすべてのアリが落ちることもない.
最大の時間を考えるためにアリが出会った場合のことを考える
お互い反対を向いて進む→すれ違ったと考えても問題はない！
以上よりすべてのアリを1度ずつ調べればよく,O(n)のアルゴリズムになる.n<=10^6という制限から、この時間で間に合うことがわかる.

2章