アルゴリズム講習会

講習会の目標

C++を使って実践的なアルゴリズムを使えるようにする。
ICPC国内予選のD問題までを解けるように！

第1回

C++

C++とは

C++は、C言語に色々な機能を追加した言語。
C言語と後方互換性がある。
- C言語で書いたプログラムはそのままC++で書いたプログラムとしても（ほぼ）動作する。
- 今までの講習会でもC++を使っていたが、実のところC言語の機能しか使っていなかった。
とにかくできることが多い言語だが、その分とても難解。
- 講習会ではそんなに難しいことはしないつもりですが。
ICPCでも最もよく使われている言語。
- Cより高機能で、Javaより高速なので。
- Cに比べ明らかにタイプ量が減るので、講習会でも今後はC++を使っていきます。

C++風にプログラムを書く

以下のプログラムは、標準入力で与えられた2つの整数の和を表示するC言語プログラム。

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("A+B = %d\n", a+b);
  
    return 0;
}

これをC++風に書いてみると、次のようになる。

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << "A+B = " << a+b << endl;
  
    return 0;
}

主な違い

先頭の#includeの辺りが変わっている。
- C++の標準入出力（cinとcout）を使うにはiostreamをインクルードする。
- using namespace std; は標準の名前空間を使うという意味
scanfがcinに、printfがcoutになっている。
- cin >> (変数) とすれば、変数に標準入力の内容が代入される。変数の型は自動で判別されるので、%dとか%sとか書かなくていい。
  - ここでの>>と<<は入出力演算子。cinからデータが右に流れ出ていて、coutへ向かってデータを左に流し込んでいくという感覚。
改行文字がendlになっている。

使い分け

多くの場合cin・coutを使ったほうが便利だけど、scanf・printfの方がいいときもある。

printf("%04d %2.4lf", 32, 7.3);のように、桁数指定をするときとか。
scanf("%d,%d:%d", &a, &b, &c);のように、入力が空白区切りでないときとか。
動作速度はcinよりscanfの方が速い。
使い分けよう。

問題1

AIZU ONLINE JUDGEの問題10010「Simple Calculator」

cinとcoutを使い、#include <stdio.h>を使わずに解いてください。

標準ライブラリを使う

上の例では入出力が少し変わっただけだが、C++の標準ライブラリ（STLとも呼ばれる）を使うとコードを一気に簡略化できることもある。

C++の標準ライブラリには普段のプログラミングでよく使うツール（スタック、キュー、動的配列、文字列など）が事前に用意されている。

便利。

Cで作ったプログラムを標準ライブラリを使って簡略化

以下はコマンド入力を使ってスタックを操作するプログラム。去年のスタックの資料の解答そのまま。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STACK_SIZE 1010
#define STR_SIZE   7

int top;
int stack[STACK_SIZE];

// メッセージを表示してプログラムを終了
void error(char *message)
{
   puts(message);
   exit(1);
}

int stack_empty()
{
   return top == 0 ? 1 : 0;
}

void push(int x)
{
   if(top >= STACK_SIZE - 5) {
      error("stack overflow");
   }
   stack[++top] = x;
}


int pop()
{
   return stack[top--];
}

int main()
{
   int m, tmp;
   char str[STR_SIZE];

   scanf("%d", &m);
   while(m --> 0) {
      top = 0;   // topを初期化
      for(;;) {
         scanf("%s", str);
         if( !strcmp(str, "push") ) {
            scanf("%d", &tmp);
            push(tmp);
         }
         else if( !strcmp(str, "pop") ) {
            if( stack_empty() ) continue;   // popする前に空かどうか確認
            else pop();
         }
         else if( !strcmp(str, "end") ) {
            break;
         }
      }

      if( stack_empty() ) {
         printf("Stack is empty.\n");
      }
      else {
         printf("%d\n", pop());
      }
   }

   return 0;
}

これをC++標準ライブラリを使って書き換えると、以下のようになる。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
   int m, tmp;
   string str;

   cin >> m;
   while(m-- > 0) {
      stack<int> st; // スタックを宣言＋初期化

      for(;;) {
         cin >> str;
         if(str == "push") {
            cin >> tmp;
            st.push(tmp);
         }
         else if(str == "pop") {
            if( st.empty() ) continue;   // popする前に空かどうか確認
            else st.pop();
         }
         else if(str == "end") {
            break;
         }
      }

      if (st.empty()) {
         cout << "Stack is empty." << endl;
      }
      else {
         cout << st.top() << endl;
      }
   }

   return 0;
}

自前でスタックを作っていた部分がなくなり、コードが30行ほど短くなった。
文字列を表すのにchar配列ではなくC++のstring型を使っているので、==による文字列比較ができるようになった。
- これは演算子オーバーロードというC++の機能の効果。
- 余談だが、等号演算子=もオーバーロードされているのでCでは意図通りに動かないstr = str2;でも文字列の代入ができる。
C++のコードのほうがより直観的なのがわかると思います。

よく使う標準ライブラリ

vector：動的配列
- 便利なので普通の配列の代わりとしても使う。
stack：スタック
queue：キュー
- priority_queue：プライオリティキュー
map：キーと値のペアの集合
- pair：キーと値のペア
string：文字列
algorithm：アルゴリズムつめあわせ
- sort：ソート
- find：値の検索
- lower_bound・upper_bound：2分探索
- min・max：最大最小
- next_permutation：順列

参考ページ

C++編（標準ライブラリ）- Programming Place Plus：標準ライブラリの解説（サンプルコード付き）
Reference - C++ Reference：標準ライブラリのリファレンス（英語）
サークル室にあるSTLのリファレンス本も読んでみるといいです

問題2

AIZU ONLINE JUDGEの問題13「Switching Railroad Cars」

標準ライブラリのstackを使って解いてください。以下にスタックの使い方例を載せています。

#include <iostream>
#include <string>
#include <stack> // スタックをインクルード
using namespace std;

int main() {
    stack<int> intStack; // 整数値を格納するスタックを宣言
    stack<string> strStack; // 文字列を格納するスタックを宣言
    
    intStack.push(6); // スタックに値を追加
    strStack.push("hello,");
    strStack.push("world!");
    
    intStack.top(); // スタックの先頭の値を見る（ここでは6）
    cout << strStack.top() << endl; // 「world!」と表示
    
    intStack.pop(); // スタックの先頭の要素を取り出す
    
    strStack.size(); // スタックに入っている要素数を返す（ここでは2）
    strStack.empty(); // スタックに要素が1つも入っていないならtrue（ここではfalse）
    
    return 0;
}

問題3

AIZU ONLINE JUDGEの問題1166「迷図と命ず」

2010年ICPC国内予選B問題。やや難しい。以下にキューの使い方例を載せています。

#include <iostream>
#include <queue> // キューをインクルード
using namespace std;

int main() {
    queue<int> ique; // 整数値を格納するキューを宣言
    
    ique.push(70); // キューに値を追加
    ique.push(46);
    
    ique.front(); // キューの先頭の値を見る（ここでは70）
    cout << ique.front() << endl; // 「70」と表示
    
    ique.pop(); // キューの先頭の要素を取り出す
    
    ique.size(); // キューに入っている要素数を返す（ここでは1）
    ique.empty(); // キューに要素が1つも入っていないならtrue（ここではfalse）
    
    return 0;
}

次回やること（予定）

次回も引き続きC++をやる予定。内容は未定

内容案：

STLの使い方
- vector
- map
- pair
- algorithm
- イテレータ
structでクラス作成
- 演算子オーバーロード（大小比較可能なクラスを作る）

余談（defineマクロとか）

#include <....> と毎回書くのは面倒なので、最初にテンプレを作っておくと便利。こんな風に。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
typedef long long ll;

int main() {

     return 0;
}

コーディング量を減らすため、include文のほかに色々なdefineマクロやtypedefを最初に書いている人もいる。

上記のテンプレでも#define rep(i,n)なるものが定義されているが、これはfor文を略記するためのもの。下記のように使える。

vector<int> vec(10, 1); // 要素10個の配列を初期値1で作成

for(int i = 0; i < vec.size(); i++) {
    cout << vec[i] << endl;
}
// ↑同じ↓
rep(i, vec.size()) {
    cout << vec[i] << endl;
}

include・defineマクロやtypedefの使い方に決まった形式はなく、好みによっていろんなバリエーションのものが使われている（全然使われないこともある）。

Codeforcesで見つけた、include/define/typedefを多用しているコードの例：

個人的にはdefine/typedefを多用するのはそんなに好きではないけど、実際便利なので他の人がコードを読んで無理なく理解できるレベルならどんどん使っていいと思う。

余談2（コンパイラについて）

Maximumの最初の講習会では、c++コンパイラとしてbcc（Borland C++ Compiler）を導入するようにしている。しかし、各種プログラミングコンテストではg++（GNU C++ Compiler / gccのC++版）が使われることが多い。

bccとg++は基本的な部分ではほとんど変わりはないが、細かい違いがある。特に重大なのが、64bit整数型（Javaで言うlong型）の扱いの違い。

上記のテンプレにはtypedef long long ll;というものがあるが、これはbccではコンパイルエラーになる。なぜなら、g++で64bit整数を表すlong long型はbccでは使えないから。 bccではtypedef __int64 ll;としないといけない。

これ以外にも、scanfやprintfでのlong値やdouble値の表現法が異なるなど、微妙な違いがある。できればg++に統一したいところ。