AD - 3.06.その他の機能 /

Time Limit: 0 msec / Memory Limit: 0 KB

前のページ | 次のページ

キーポイント

  • コンピュータの内部では「文字」を数値として扱っており、文字に対応する数値を文字コードという
  • char型の値は実質的に数値なので、int型と同じように四則演算や比較ができる
  • 関数の外で宣言した変数をグローバル変数と呼び、プログラム全体がスコープになる
  • const修飾子を付けて宣言した変数は定数として扱える
  • 条件演算子を使うと「if文で分岐して値を選ぶ処理」を短く書ける
条件式 ? 真の時の式 : 偽の時の式
  • マクロを使うと変数を使う感覚でプログラムを置換することができる
  • ラムダ式を使うと関数の内部で関数を定義できる
  • do-while文とnext_permutation関数を使うと「順列の全列挙」が簡単に書ける
  • goto文は多重ループからの脱出に便利

3.06.その他の機能

このページでは競技プログラミングに役立つことがあり、今まで説明してこなかった細々とした知識について説明します。
今回の問題はこのページで説明した内容を使わなくても解けるので、読まずに問題を解いても良いです。

EX26.電卓を作ろう3


文字コード

コンピュータの内部では「文字」を数値として扱っています。
ある文字が内部でどのような数値になっているかは、char型の値をint型にキャストすることで見られます。
また、int型をchar型にキャストすることで、数値と対応している文字を見ることもできます。

次のプログラムは文字とそれに対応する数値を出力する例です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << (int)'A' << endl;
  cout << (int)'B' << endl;
  cout << (int)'Z' << endl;

  cout << (char)65 << endl;
  cout << (char)66 << endl;
  cout << (char)90 << endl;
}
実行結果
65
66
90
A
B
Z

「ある文字に対応する数値」のことを文字コードと呼びます。また、「全ての文字と数値の対応関係」をまとめて文字コードと呼ぶこともあります。
後者の意味で、文字コードには様々な物があります。char型やstring型は通常ASCII文字コード(アスキー文字コード)というものを用いています。
ASCII文字コードは基本的に半角英数字と半角記号('0''A''a''!'等)を扱うためのものです。char型やstring型では日本語がうまく扱えないのはそれらがASCIIコードを前提としているためです。

ASCII文字コードにおける文字と数値の対応はWikipediaで見ることができます。

これらの文字と数値の対応を覚える必要は全くありませんが、「『'0''9'』、『'A''Z'』、『'a''z'』がそれぞれ連続していること」と、
「大文字は小文字より小さい数値に対応していること」は覚えておくと役に立つことがあります。

文字コードを利用したプログラム

char型の値は実質的に数値なので、int型と同じように四則演算や比較ができます。

char型に対する加算

次のプログラムはこれを用いて'A''Z'を出力します。

#include <bits/stdc++.h>
using namespace std;

int main() {
  for (int i = 0; i <= ('Z' - 'A'); i++) {
    cout << (char)('A' + i);
  }
}
実行結果
ABCDEFGHIJKLMNOPQRSTUVWXYZ

i <= ('Z' - 'A')とすることで出力したい文字数分だけループし、(char)('A' + i)で「'A'からi文字進めた文字」を計算しています。
char型に対して四則演算をした結果はint型になるため、出力する前にchar型にキャストし直す必要があることに注意してください。

他にも、次のようにして大文字と小文字を変換することもできます。

(char)('x' + ('A' - 'a')) // 'X' 小文字→大文字
(char)('X' - ('A' - 'a')) // 'x' 大文字→小文字

この処理はC++で用意されている関数を使って行うこともできます。小文字→大文字の変換は(char)toupper(文字)、大文字→小文字の変換は(char)tolower(文字)で利用できます。

char型の比較

次のプログラムは文字コードを比較することにより、大文字と小文字の判定を行っています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  char c = 'X';
  if ('A' <= c && c <= 'Z') {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}
実行結果
YES

文字コード上で'A''Z'は連続しているため、'A' <= c && c <= 'Z'だけで判定ができます。

大文字の判定はC++で用意されている関数を使ってisupper(文字)で行うこともできます。同様の便利な関数として小文字の判定を行うislowerや、10進数の数字かどうかをチェックするisdigitなどもあります。


グローバル変数と定数

今まで出てきた変数のように、関数の中で宣言した変数をローカル変数と呼びます。
変数は関数の外で宣言することもできます。関数の外で宣言した変数はグローバル変数と呼びます。

グローバル変数の使い方はローカル変数と全く同じです。

#include <bits/stdc++.h>
using namespace std;

//グローバル変数
int number = 10;

int main() {
  cout << number << endl;
}
実行結果
10

グローバル変数のスコープ

グローバル変数のスコープはプログラム全体、つまり「宣言された場所からプログラムの終わりまで」になります。
そのため、複数の関数をまたいで使うことができます。

#include <bits/stdc++.h>
using namespace std;

//グローバル変数
int number = 10;

void change() {
  number = 5;
}

int main() {
  cout << number << endl;

  change();

  cout << number << endl;
}
実行結果
10
5

グローバル変数名の衝突

ローカル変数と同様に、同じ名前のグローバル変数は宣言できません。
まれにSTLで定義しているグローバル変数と衝突することもあるので注意してください。


const修飾子

const修飾子を変数の宣言時につけると、その変数を定数(変えられない値)として扱えるようになります。

宣言は次の形式になります。

const 型 変数名 = 値;

値が変えられないこと以外は変数と同じように使うことができます。

#include <bits/stdc++.h>
using namespace std;

int main() {
  const int a = 10;

  cout << a + 5 << endl;

  // 再代入はできない
  // a = 5;
}

const修飾子の使い所

const修飾子の使い所として、bitsetのビット数を指定する場合があります。
bitsetのビット数は定数でなければなりませんが、何度もbitsetの型を書かないといけない場合を考えると、直接数値を書くのは面倒な上に書き間違えの恐れもあります。
「const修飾子を付けた変数」を使えば直接数値を書くこと無く、楽かつ安全にbitsetのビット数を指定できます。

const int B = 100;

bitset<B> func1(bitset<B> a) {
  ...
}
bitset<B> func2(bitset<B> a) {
  ...
}

他にも1.13.配列の細かい話で紹介した「Cの配列」やarrayの要素数の指定も定数である必要があるため、「const修飾子を付けた変数」が利用できます。
また、値が変わらないことを保証することで安全にプログラムを書くという目的でconst修飾子を利用することもあります。

GCC環境では、ローカル変数であれば「Cの配列」の要素数は変数で指定できます。


条件演算子

if文の書き換え

条件演算子(または三項演算子)を使うとif文を短く書き換えられることがあります。
次のプログラムは2つの数値の入力のうち小さい方を出力をif文を用いて実装しています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  int answer;

  // 小さい方の値をanswerに代入する
  if (a < b) {
    answer = a;
  }
  else {
    answer = b;
  }

  cout << answer << endl;
}

これは条件演算子を使うと次のように書き換えられます。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  // 小さい方の値をanswerに代入する
  int answer = a < b ? a : b;

  cout << answer << endl;
}

このように、if文で分岐して値を選ぶ処理は条件演算子で短く書くことができます。

条件演算子の記法

条件演算子の書き方は次のようになります。

条件式 ? 真の時の式 : 偽の時の式

条件演算子のネスト

条件演算子もif文のようにネストさせることができます。
次のプログラムは3つの入力を受け取り、その中で最小の数値を出力しています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  int answer = a < b && a < c ? a : b < a && b < c ? b : c;

  cout << answer << endl;
}

このように条件演算子のネストを書いてしまうと読み辛くなりやすいため、次のように改行とインデントを用いて読みやすくした方が良いでしょう。

// インデントのパターンその1
int answer = a < b && a < c
  ? a 
  : b < a && b < c
    ? b 
    : c;

// インデントのパターンその2
int answer = a < b && a < c ? a 
  : b < a && b < c ? b 
  : c;

条件が複雑に入り組んでいる場合は条件演算子を使わないほうが読みやすいこともあります。状況に応じて読み書きしやすい方を使いましょう。

条件演算子の優先順位

演算子の優先順位の関係で、coutの内部で条件演算子を利用する場合は()で囲う必要があります。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  cout << (a < b ? a : b) << endl; // ()で囲う
}

細かく言うと、条件演算子は代入演算子=や複合代入演算子◯=の次に演算子の優先順位が低いです。
例えば次の2行のプログラムは同じ意味になります。

a + b < c ? x : y * z
(a + b < c) ? (x) : (y * z) // 明示的に()で指定

マクロ

マクロdefineディレクティブ)は付録4.ループの裏技repマクロで紹介した「repマクロ」を作成するために利用した機能です。
マクロを使うと、変数を使う感覚でプログラムを置換することができます。

次のプログラムはmy_coutという名前のマクロを定義しています。my_coutはその部分をcout <<に置き換えます。

#include <bits/stdc++.h>
using namespace std;

// my_coutというマクロを定義
#define my_cout cout << 

int main() {
  // 次の行は cout <<"hello"; に置き換わる
  my_cout "hello";
}
実行結果
hello

単純なマクロの記法

マクロは次のように書きます。半角スペースで区切って定義することに気をつけてください。

#define マクロ名 置き換えるプログラム

上のプログラムでは「マクロ名」がmy_coutであり、「置き換えるプログラム」がcout <<です。

引数を取るマクロ

マクロは関数のように引数を受け取ることもできます。

次のプログラムはis_not_5という名前のマクロを定義しています。is_not_5(n)はその部分をif (n != 5)に置き換えます。

#include <bits/stdc++.h>
using namespace std;

// is_not_5というマクロを定義
#define is_not_5(n) if (n != 5)

int main() {
  // 次の行は if (10 != 5) { に置き換わる
  is_not_5(10) {
    cout << "NOT 5" << endl;
  }
}
実行結果
NOT 5

引数を取るマクロの記法

引数を取るマクロは次のように書きます。

#define マクロ名(引数1, 引数2, ...) 置き換えるプログラム

複数行のマクロ

マクロの「置き換えるプログラム」が複数行に渡る場合、行末に\を書く必要があります。
以下はその定義の例です。

#define my_macro cout << "hello" << endl; \
cout << "AtCoder" << endl; \
cout << "C++" << endl;

repマクロの正体

repマクロの定義は次のようになっています。

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

ここまでの説明でわかるように、これは単にrep(カウンタ変数, 回数)for (int カウンタ変数 = 0; カウンタ変数 < (int)回数; カウンタ変数++)という形式に変換しています。

マクロの注意点

マクロを使うと短くプログラムを書くことができますが、「単純にプログラムを置換する」という動作の性質上、多くの落とし穴があります。
競技プログラミングのような小規模なプログラムではあまり問題になりませんが、大規模な開発では不用意にマクロを定義することは避けられることが多いです。

マクロの例 allマクロ

競技プログラミングでrepマクロの次に多く使われているマクロがallマクロです。
allマクロはsort等の関数呼び出しを簡潔にします。自己責任で利用してください。

#include <bits/stdc++.h>
using namespace std;

// allマクロの定義
#define all(v) v.begin(), v.end()

int main() {
  vector<int> v = { 2, 3, 1 };
  sort(all(v)); // 2回配列変数名を書く必要がない
  cout << v.at(0) << endl;
}

ラムダ式

ラムダ式を利用すると関数の内部で関数を定義できます。

次のプログラムはmain関数の内部で、ラムダ式を用いてmy_min関数を定義しています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  // my_min関数をラムダ式で定義
  auto my_min = [](int a, int b) {
    if (a < b) {
      return a;
    }
    else {
      return b;
    }
  };

  cout << my_min(5, 10) << endl;
}
実行結果
5

ラムダ式の記法

基本的なラムダ式の記法は次の通りです。セミコロンが末尾に必要だということに注意してください。

auto 関数名 = [](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 };

ラムダ式の外の変数の利用

[&]と書くことでラムダ式の外の変数を利用できます。
次のupdate_max関数はmain関数の内部で定義されているmax_numを利用しています。

#include <bits/stdc++.h>
using namespace std;

int main() {

  // 最大値を保持する変数
  int max_num = 0;

  // 今まで受け取った値の中から最も大きな値を返す関数
  auto get_max = [&](int n) {
    if (max_num < n) {
      max_num = n;
    }
    return max_num;
  };

  cout << get_max(5) << endl;
  cout << get_max(2) << endl;
  cout << get_max(10) << endl;
  cout << get_max(4) << endl;
}
実行結果
5
5
10
10

この他にもラムダ式にはいくつかの機能があります。気になる人は調べてみてください。

ラムダ式による再帰関数

ラムダ式で再帰呼び出しのある関数を定義する場合、autoではなくfunctionを型として指定する必要があります。
次のプログラムは0~Nの和を求める再帰関数sumをラムダ式で定義しています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  // 再帰関数の定義
  function<int(int)> sum = [&](int n) {
    if (n == 0) {
      return 0;
    }
    int s = sum(n - 1);
    return s + n;
  };

  cout << sum(3) << endl;
}
実行結果
6

ラムダ式による再帰関数の記法

再帰呼び出しのあるラムダ式は次のように定義します。
返り値の型と引数の型をfunction<>の中に書いたうえ、[&]と書く必要があることに注意して下さい。

function<返り値の型(引数の型1, 引数の型2, ...)> 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 };

ラムダ式の使い道

ラムダ式は短い関数をその場で定義したい時に便利です。その例として「sort関数の比較関数の変更」を説明します。
sort関数は通常sort(配列.begin(), 配列.end())のように呼び出しますが、三番目の引数に関数を渡して比較方法を変更することができます。
次のプログラムはsort関数に自分で定義した比較関数を渡すことで、大きい順にソートさせています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = { 2, 3, 1 };
  // 大きい順にソートさせる比較関数
  auto comp = [](int a, int b) { return a > b; };
  sort(v.begin(), v.end(), comp);

  cout << v[0] << endl; // v は {3, 2, 1}となっている
}
実行結果
3

名前をつけることを省略してさらに短く書くことも可能です。引数に直接渡す場合はセミコロンが不要になります。

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = { 2, 3, 1 };
  // 大きい順にソートさせる比較関数を直接渡す
  sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

  cout << v[0] << endl; // {3, 2, 1}となっている
}

do-while文

今まで説明してこなかったループ構文として、do-while文があります。
do-while文は通常のwhile文と異なり、条件式の判定を行うより前に一度だけループ内部の処理を実行します。
つまり、while文が「条件式→処理→条件式→処理...」という順番で実行するのに対し、do-while文は「処理→条件式→処理→条件式...」という順番で実行します。

次のプログラムは入力で受け取った数を0までカウントダウンして出力します。
ただし、入力が負の数だった場合は一度だけ出力してプログラムを終了します。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  // nが負の数でも一度だけ実行される
  do {
    cout << n << endl;
    n--;
  } while (n >= 0);
}
入力1
3
実行結果1
3
2
1
0
入力2
-5
実行結果2
-5

この例のように、条件式がはじめから偽でも一度だけ実行することが特徴です。ただし、ほとんどの場合はwhile文で十分なのでdo-while文を使うべき場面は基本的にありません。 ここでは次で紹介するnext_permutation関数の説明を行うためにdo-while文を紹介しました。

next_permutation関数

next_permutation関数は「順列の全列挙」を行うための関数です。
次のプログラムは{ 1, 2, 3 }という配列に対して、すべての順列を出力しています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = { 2, 1, 3 };
  sort(v.begin(), v.end());
  do {
    // 1行で今の並び方を出力
    for (int x : v) {
      cout << x << " ";
    }
    cout << endl;
  } while (next_permutation(v.begin(), v.end()));
}
実行結果
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

順列とはこの例のように、値の集合を順番に並べたもののことを言います。
また、より正確にはnext_permutation関数は「区別可能なn個の対象から重複を許してk個の対象を取り出して特定の順番で並べたもの」を全列挙するための関数になります。

next_permutation関数の使い方

next_permutation関数は次のように使います。
事前にsortが必要なことに注意してください。

sort(配列変数.begin(), 配列変数.end());
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));

「順列の全列挙」は再帰関数で実装することもできますが、next_permutation関数を使ったほうが簡単に実装することができます。

next_permutation関数の計算量

next_permutation関数を使って順列の全列挙を行った場合の計算量は、配列の長さをNとするとO(N!)になります。
Nが小さくても計算量は大きくなるので、使う際は計算量に気をつけましょう。

練習問題

以下はnext_permutation関数を使って解ける問題です。


goto文

最も単純な制御構文としてgoto文があります。goto文に到達すると、ラベルを付けた行に移動します。

次のプログラムはcout << "world" << endl;を飛ばしてSKIPラベルの行に実行を移します。

#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << "Hello, ";
  goto SKIP;
  cout << "world!" << endl; //この行は飛ばされる
SKIP:
  cout << "AtCoder!" << endl;
}
実行結果
Hello, AtCoder!

goto文の記法

goto文は以下のように使います。

ラベルの定義

ラベルは次のようにラベル名の後に:を書きます。

ラベル名:

goto文

gotoの後にラベル名を指定します。goto文を実行するとラベルの行に実行が移ります。

goto ラベル名;

goto文の使い道

goto文の使い道として最も便利なのが多重ループからの脱出です。
次のプログラムはgoto文を使ってループの外に飛ぶことで、多重ループから簡単に抜けています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cout << i << " " << j << endl;
      // この条件を満たしたら多重ループから抜ける
      if (i == 1 && j == 1) {
        goto OUT;
      }
    }
  }
OUT:
  cout << "fin" << endl;
}
実行結果
0 0
0 1
0 2
1 0
1 1
fin

goto文の注意点

goto文はシンプルな機能ですが、シンプルすぎるためにプログラムが何を意図しているのか分かりにくいことをはじめ、いくつかの落とし穴があります。
多重ループからの脱出など一部の状況では使っても良いですが、goto文が必要になるケースはほとんどないので、基本的には使わないほうが良いです。


今回の問題はこのページで説明した内容を使わなくても解けるので、読まずに問題を解いても良いです。

演習問題

リンク先の問題を解いてください。