ICPC国内予選直前会議

細かなコーディングテクニックについて

自己紹介

SRM: tomerun

Marathon: tomerun

Codeforces:tomerun

小さな会社で何でも屋な感じのプログラマやってます

Java・C++・C#・Ruby・Objective-C

※ICPC参加経験はありません

内容

注意

紹介するのは、コンテストのコードを書くために特化したスタイルです。

仕事や研究で使うような、長期的にメンテナンスする可能性のあるコードで使うのは推奨されないものも多くあります（推奨できるものもあります）。

（1）大きな定数の打ち間違え防止

よくある問題：「〜の組み合わせ数を 1,000,000,007 で割った余りを求めよ」

よくあるコード：

    const int MOD = 1000000007; // 桁数あってる？
    …
    dp[i] %= MOD;

（1）大きな定数の打ち間違え防止

ぱっと見で桁数がわかるように書くと安心：

    const int MOD = 1000 * 1000 * 1000 + 7;

または

    const int MOD = (int)1e9 + 7;

コピペできる場合はそれで良いわけですが…

（2）簡易的なdoubleへのキャスト

たとえば、int同士の割り算の結果をdoubleで欲しい場合

    int distance,speed;
    …
    double time = (double)distance / speed;

（2）簡易的なdoubleへのキャスト

キャストの構文を書くよりも、1.0を掛けてdoubleへ変換した方がタイプ量が少なくて済む

    double time = 1.0 * distance / speed;

さらに1文字少なくできる

    double time = 1. * distance / speed;

（3）探索での番兵

よくある二次元グリッドでの探索問題：次のようなH*Wのセル内でスタートからゴールまでうんたらかんたら

..X.
.XS.
G..X

よくあるコード：

    int DX[4] = {1, 0, -1, 0}; int DY[4] = {0, 1, 0, -1};
    …
    for (int k = 0; k < 4; ++k) {
        int nextX = x + DX[k];
        int nextY = y + DY[k];
        if (nextX < 0 || W <= nextX || nextY < 0 || H <= nextY) continue;
        …
    }

（3）探索での番兵

(nextX < 0 || W <= nextX || nextY < 0 || H <= nextY) とか超めんどい

次のように、自分で周囲を壁で覆ってやれば境界外へはみ出ることのチェックは不要になる

XXXXXX
X..X.X
X.XS.X
XG..XX
XXXXXX

座標が1つずれることに注意

（4）プログラムできることは手動でやらない

問題「与えられた文字列の各文字が母音だったらうんたらかんたら」

まず思いつくコード：

    for (int i = 0; i < str.size(); ++i) {
        if (str[i] == 'a' || str[i] == 'i' || str[i] == 'u'
           || str[i] == 'e' || str[i] == 'o') {
            …
        }
    }

（4）プログラムできることは手動でやらない

手でたくさん並べて書きたくない。コピペしてるうちにミスりそうだし

プログラムにやらせよう

    for (int i = 0; i < str.size(); ++i) {
        if (string("aiueo").find(str[i]) != string::npos) {
            …
        }
    }

これ以外にも、何かの数を数えてテーブルを生成するような場合は、手で数えた結果を埋め込むよりプログラムにやらせた方がミスしにくい

（5）Off-by-Oneエラー防止

文字列処理をやる問題で、始点と終点が1ずれてバグることがよくある→紙に書きましょう

気をつけること：

（6）できるだけルートを取らない

ユークリッド距離はもちろん sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) ですが

処理の途中ではsqrtをせずに距離の2乗で扱えば良いケースも多い。最大の距離のものを調べる場合とか。

速度が速くなるのと、処理途中での誤差を気にしなくてよくなるのと

スローガン「除算より乗算、べき根よりべき乗」

（6）できるだけルートを取らない

もう1つの例：整数の約数を調べるときなんかに「sqrt(N)まで調べれば良い」ということで次のようなコードを書くが

    for (int i = 2; i <= sqrt(N); ++i) {
        …
    }

ルートより2乗にした方が安心できる

    for (int i = 2; i*i <= N; ++i) {
        …
    }

（これはこれでオーバーフローの可能性があるのでどっちもどっちかな…）

（7）積極的に関数化する

やろうとしていること：「配列の各要素について、自分よりも前に自分と等価な要素があったら何かする」

    for (int i = 0; i < N; ++i) {
        bool found = false;
        for (int j = 0; j < i; ++j) {
            if (a[i] == a[j]) {
                found = true;
                break;
            }
        }
        if (found) {
            …
        }
    }

この例はSTL使ったらもっと簡単に書けますが、いったんそれは置いておいて。

（7）積極的に関数化する

問題点：ネストが深くて読みにくい・foundという本質的じゃなさそうな変数が出現する

→関数化しましょう

    bool any(int s, int e, int v) {
        for (int i = s; i < e; ++i) {
            if (a[i] == v) return true;
        }
        return false;
    }

    for (int i = 0; i < N; ++i) {
        if (any(0, i, a[i])) {
            …
        }
    }

（8）（C++）配列のゼロ埋め

C++の配列は、ローカル変数の場合には最初ゴミの値が入っているので自分で初期化しないといけません。

memsetでも良いですが

    int a[1000];
    memset(a, 0, sizeof(a));

空の初期化子を指定するだけで0埋めされます

    int a[1000] = {};

配列じゃなくて構造体でも同じように0初期化できます

（9）（Java）ペアをソートする

問題：整数の配列が与えられる。値が大きい順にそのインデックスを出力せよ。

C++の場合は配列の値とインデックスをpairに入れてソート、で済みますが

Javaだと標準でPairが無いので自分で比較用のクラスを作らないといけない。面倒

次のように、1つの整数の中の上下ビットに分けて埋め込めばクラス作らなくても良い

    int a = new int[N];
    for (int i = 0; i < N; ++i) {
        a[i] = (v[i] << 16) + i;  // オーバーフロー注意
    }
    Arrays.sort(a);

（10）（Java）ビット演算便利機能

java.lang.Integerクラスあたりに、ビット演算に便利な関数があります。把握しておきましょう。

わざわざ自分で書かなくて済むよう。

    Integer.bitCount(0x137F); // => 10
    Integer.highestOneBit(0x137F); // => 0x1000
    Integer.numberOfTrailingZeros(8); // => 3

あとjava.util.BitSetクラスも地味に便利（けど自分以外で使われてるのをあまり見たことがない…）

ふりかえり