C++でアルゴリズム入門Part1(備忘録)

こんにちは。

今日はちょっと参考書籍もC/C++のほうが多いし、アルゴリズムはC++で勉強しようかなって思いますてｗ

もちろん参考書籍はコチラ

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

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: 毎日コミュニケーションズ
発売日: 2010/09/11
メディア: 単行本（ソフトカバー）
購入: 52人クリック: 1,538回
この商品を含むブログ (80件) を見る

さぁ続きからこの本を噛み砕いてご紹介(備忘録)！綴ります。

サンプルコードはすべてTopCoderで使える形式でやっています。

とりあえずアルゴリズムはその時間をランダウのO-記法というもので書く。
たとえばこんな簡単な方の問題があったとして…

n本の棒があります。棒iの長さはaiです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形をつくろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には０を答えとしなさい。
制約
＊3≦n≦100
＊1≦ai≦10^6

でこれを単純にこう書いたとします。

public class Sample {
public:
  int solve(int n, int[] a) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
          int len = a[i] + a[j] + a[k];
          int ma = max(a[i], max(a[j], a[k]);
          int rest = len - ma;
          if (ma < rest) {
            ans = max(ans, len);
          }
        }
      }
    }
    return ans;
  }
}

え〜とコードは少ない僕のC/C++に関する知識で書き換えましたが…あってるよね？合ってると信ずる。間違ってたらコメントください。修正します。

で、これはfor文が三重になっていますね。なのでこれの計算量はO(n^3)時間とあらわせます。nというのは問題中のnだと思ってください。
目安として()内を計算したときに、実行制限時間が1秒だとしたら1000000であれば余裕で間に合うし、100000000ならおそらく間に合うといった感じ。

だからこのコードでのnの上限100でこのコードを考えると
10^6=1000000
となり実行に１秒かからないだろうと検討をつけることができます。

ではココで思考タイム！
僕も少し自分で頑張ってみようと思います。

挑戦は次の問題

Ants (POJ No.1852)
長さLcmの竿の上をn引きのアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下に落ちていきます。また、竿の上は狭くて擦れ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。各アリについて、現在の竿の左端からのXiはわかりますが、どちらの方向を向いているのかはわかりません。すべてのアリが竿から落ちるまでにかかる最少の時間と最大の時間をそれぞれ求めなさい。
制約
＊1≦L≦10^6
＊1≦n≦10^6
＊0≦Xi≦L

いまちょっとアルゴリズムをすこし思い出してしまったので、僕はC++にいきなり挑戦しますが、まずは慣れている言語で考えたほうがいいでしょう。

いいですか？

まずは僕の解答

public class Ants {
public:
  int Antsmin(int L, int n, int[] x) {
    // 方針：ぶつかっても同じなので無視する。
    int t = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      t = min(L-x[i], x[i]);
      ans += t;
    }
    return ans;
  }
  int Antsmax(int L, int n, int[] x) {
    int t = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      t = max(L-x[i], x[i]);
      ans += t;
    }
    return ans;
  }
}

なぜか鮮明におぼえてましたorz

だけどC++の文法まちがってる＆そもそもどっか間違えてるかもなんで本のとおりに解説＆模範解答。。。
まず、本はアリの向いている方向を前通り試す全探索のアルゴリズムを考えます。

しかしコレだと一匹のアリについて２通りずつ、つまりは2^n通りの試行を繰り返すことになり、この問題の上限などになったらそれは10の301030乗になってしまいます。

そこで効率なものを探した結果本ではアリがぶつかってもそのまま進み続けると考えます。
そして模範解答(改変したもの)がコチラ

public class Ants {
public:
  int Antsmin(int L, int n, int[] x) {
    int minT = 0;
    for (int i = 0; i < n; i++) {
      minT = min(minT, min(x[i], L - x[i]));
    }
    return minT;
  }
  int Antmax(int L, int n, int[] x) {
    int maxT = 0;
    for (int i = 0; i < n; i++) {
      maxT = max(maxT. max(x[i], L - x[i]));
    }
    return maxT;
  }
}