はじめに
数学科を卒業してから10年以上も経過しますが
プログラミングに興味を持ちはじめた古い友人と話しているときに
正直なところ高校数学レベルの知識ってプログラミングに役立つの?
という話題になったのでそのとき紹介したTipsを書き留めておきます。
初歩的な競技プログラミングと高校数学
題材として 初歩的な競技プログラミングの問題を取り上げます。AtCoderの
beginner contest26 の1問目になります。
以下のような内容です。
問題文
正の偶数 A が与えられる。
x+y=A となる正の整数 x, y のうち、 x×y が最大となるものを選び、その値を出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。
A
1 行目には、正の偶数 A(2≦A≦100) が与えられる。
出力
x×y の最大値を出力しなさい。 出力の末尾には改行を入れること。
入力例1
10
出力例1
25
x=5, y=5 のとき、 x×y=25 となり、これが最大値となります。
熟練プログラマの方でも競技プログラミング慣れていない方（全然普通だと思います) は身構えてしまうかもですが、難しく考えずにまずは全探索する方法を考えるのが競技プログラミングの基本になります。
競技プログラミングと実務で必要とされる力はスコープが違う部分も多いので、できなくてもへこまないことです。村上春樹風に言えば、「完璧なプログラミングなんてない。完璧な絶望がないように」という感じでしょうか。
話を元に戻します。Javaで書きました。(AtCoderでACとなるのを確認済み)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
for ( int x = 1; x < n; x++) {
if ( x * (n -x) > max) {
max = x * (n-x);
}
}
System.out.println(max);
return;
}
}
愚直に1から一つずつ調べ上げていく方法ですね。
O(n)をO(1)に
このままでも正解となり得点は来るのですが、計算量という観点で見るとO(n)となっています。
つまり、入力サイズ n が増加するにつれて、実行時間が n に比例して増加する ということです。
実はこの問題 相加相乗平均 という公式を知っていると、O(1)にすることができます。
入力値がnが常に偶数ならば x=y=n/2 が常に答えとなります。問題文をよく見ると
「正の偶数 A が与えられる。」と書いてありますね！
以下のようになります。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(n/2 * n/2);
return;
}
}
これでももちろんAC(正解)がきます。
しかも、この場合計算量はO(1) つまり、nがどんな数字でも実行時間がそれに比例して増加することはありません。模範解答という点ではこちらでしょうか。
実行時間を気にしないプログラムはそんなにないはずなので、実務観点でも興味深い話ではないでしょうか。
まとめ
実際には、仕事であるいは趣味でプログラミングをする上で、
数学の専門的知識はほとんど必要ないと言えるでしょう。
(そうでないと採用難しい)
しかし、数学は現代においては実学であり、IT社会にいると知っておいて得をすることが多いよ、
というお話です。