蟻本


※上記の広告は60日以上更新のない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章