TopCoder の傾向と対策（Ｊａｖａ編）

０、はじめに

TopCoder はアルゴリズムの勝負なので、
基本的にどの言語を使うと有利とかそういうことはありません。

ただし、TopCoder では圧倒的に C++ が多数派です。
どうしても java より実行時間が早いので、
２秒ギリギリのコードを書いたときに、
java では通らないけど同じやり方で C++ で通った、
とかいう話も聞きます。

しかし、問題はすべての言語で解けるようにできているので、
java でも十分に戦えます。
C++ の次に多いのが java で次に多い C# より圧倒的に多数派です。
ほかに java は BigInteger が使えるという利点があります。

１、数字の最大値に対する対策

java は int 型が符号ありで 32 ビット値になります。
問題は最大値が 2000000000 程度で抑えられることが多く、
int 型を使えばほとんどの値が扱えます。
問題によっては解答が int の最大値を超えることがありますが、
この場合は解答を 1000000007 で割った余りを返せという指示があります。
よって、答えを

ans += num;
ans %= 1000000007;

のように書いていけば、最大値を超えることはありません。
もちろん ans += num の時点で int の最大値を超える心配もあるので、
この場合は int を使わずに long を使っておくと安全です。
long は java では 64 ビット値のことです。
オーバーフローが心配な場合は long を使っておきましょう。
計算途中であっても１回でもオーバーフローしたらアウトです。
ちなみに int の最大値は 2^31 - 1 で Integer.MAX_VALUE で定義されています。
また、long の最大値は 2^63 - 1 で Long.MAX_VALUE で定義されています。
long をオーバーフローする問題はまず出ないと思います。
心配であれば BigInteger を使っておくと確実です。

２、総当り

すべての基本になるのが総当りです。
総当りはすべてのケースを試すので正解する確率が高い。
ただし総当りで解けるのは Easy のケースくらいです。
Midium 以降では単純な総当りでは解けません。
なぜなら普通に探索していると実行時間が足りなくなるからです。

総当りの方法には単純な総当り、深さ優先探索、幅優先探索などがあります。

総当りのことを brute force (ブルート・フォース)と呼びます。
深さ優先探索は dfs、幅優先探索は bfs とか呼ばれます。

単純な総当りは、
与えられた配列から２つの数を選んだ和が７の倍数であるものはいくつか、
という問題があるときに。

int count = 0;

int[] array = {1,4,3,6,5,3,2,1};

for(int i1 = 0; i1 < array.length - 1; i1++){
  for(int i2 = i1 + 1; i2 < array.length; i2++){
    if((array[i1] + array[i2]) % 7 == 0){
      count ++;
    }
  }
}

と書くことができる。

ただし、この書き方は場合によっては for ループを何重にも書く必要があるし、
迷路探索などより複雑な探索を書くことが難しい。

深さ優先探索は、
与えられた配列内のいくつかを足して解が偶数になる場合の最大値を返せ、
という問題があるときに。

int max = 0;

int[] array = {1,4,3,6,5,3,2,1};

void dfs(int index, int sum){
  if(index == array.length){
    if(sum % 2 == 0){
      max = Math.max(max, sum);
    }
    return;
  }

  dfs(index + 1, sum);

  dfs(index + 1, sum + array[index]);
}

と再帰で書ける。

幅優先探索は、
配列の中から５つの数字を選んだ和が偶数になる場合の最大値を返せ、
という問題があるときに。

class P{
  int index;
  int count;
  int sum;
}

int max = 0;

int array[] = {1,4,3,6,5,3,2,1};

void bfs(){
  Queue<P> que = new LinkedList<P>();

  for(int i = 0; i < array.length; i++){
    P p = new P();

    p.index = i;
    p.count = 1;
    p.sum = array[i];

    que.offer(p);
  }

  while(!que.isEmpty()){
    P pf = que.poll();

    if(pf.count == 5 && pf.sum % 2 == 0){
      max = Math.max(max, pf.sum);
    }

    for(int i = pf.index + 1; i < array.length; i++){
      P pa = new P();
      pa.index = i;
      pa.count = pf.count + 1;
      pa.sum = pf.sum + array[i];
      if(pa.count <= 5){
        que.offer(pa);
      }
    }
  }
}

このように Queue を使って実現する。

深さ優先探索と幅優先探索は全探索する場合には違いはありません。
ただし、深さ優先は早い段階から深い探索をするので、
結果がひとつでも成り立つかどうかをチェックする場合などに使える。
幅優先探索であるとその深さに達するまでのすべての深さを試す無駄がある。
逆に、幅優先探索は最短距離を検出する場合などに使える。
深さ優先探索を使うとその深さが最短なのかどうかわからないので、
結局は全探索をしないとその地点が最短かどうかがわからない。

探索の方法を理解して使い方を考える必要がある。

３、動的計画法

動的計画法とはいちど計算した結果を記録しておき、
再度同じ計算をする必要が無いように工夫する方法です。

以下の例ではまず array にすべて -1 を入れておきます。
fib(n) の答えが無ければ（array[n] == -1）であれば計算を行い、
fib(n) の答えがあればすでに計算してあれば array[n] を返します。
答えをメモしておくのでメモ化とも呼びます。

int array[10000000]; // すべて -1 で初期化しておく。

int fib(n){
  if(array[n] != -1){
    return array[n];
  }

  if(n == 0){
    array[0] = 1;
    return 1;
  else if(n == 1){
    array[1] = 1;
    return 1;
  }
  else{
    array[n] = fib(n - 1) + fib(n - 2);
    return array[n];
  }
}

４、データの記録と操作１ 配列

配列は最初にサイズを指定できるが途中経過でサイズの増減ができない。
配列のサイズは length で得ることができる。 

Integer[] d = new Integer[100];

for(int i = 0; i < d.length; i++){
  d[i] = new Integer(0);
}

また、ソートや２分岐探索もできます。

Arrays.sort(d);
Arrays.binarySearch(d, key);

５、データの記録と操作２ Stack

データをどのように記録するかにはいろいろな方法がある。
変数、配列の次に簡単な構造に Stack がある。
データを上に積んでいき取り出すときは上から取り出すデータ構造。

Stack<Integer> stack = new Stack<Integer>();

stack.push(num) で値を入れ、stack.pop()で取り出す。

データの有無を調べる stack.empty() や、
取り出したデータを消去しない stack.peek() がある。
また、stack.search(num) で num のある index を得ることができる。

６、データの記録と操作３ AllayList

AllayList は複数のデータを記録することができます。
データの順番を管理し、記録する値の重複を許します。
a.add(n) で値を追加し、 a.get(i) で i 番目のデータを得ます。

利点はデータの領域を動的に増加させることができる点。
また、Collections を使ってソートや二分探索が行えます。
二分探索(binarySearch)の前には必ず sort をすること。

ArrayList<Integer> a = new ArrayList<Integer>();

Collections.sort(a);
Collections.binarySearch(a, num);

binarySearch は値があればその index を返す。
無ければあるべき index にマイナスをつけ -1 した値を返す。
この結果を使えば upper_bound や under_bound も実装できる。

ソートは Comparator を使うと逆順ソートなども行える。

Collections.sort(a, new rev_co());

class rev_co implements Comparator {
  public int compare(Object a, Object b) {
    return (((Integer)b).intValue() - ((Integer)a).intValue());
  }
}

ArrayList は配列に変換できる。

Integer[] d = (Integer[])array.toArray(new Integer[0]);

また、ArrayList と似たリストに LinkedList があります。
ArrayList はメモリ上に順に固定されたリスト。
ArrayList は要素のリスト内の挿入や削除に弱い。
LinkedList は要素をリンクして連結されたリスト。
LinkedList は先頭から探索するのでランダムアクセスに弱い。

７、データの記録と操作４ Set

Set は複数のデータを記録することができます。
データは順番を管理せず重複を許しません。

与えられた配列から２つの数を選んだ和の解は何通り存在するか？
という問題では答えが下のコードで s.size() で得られます。

int count = 0;

Set s = new HashSet(); // TreeSet は自動でソートするが遅くなる

int[] array = {1,4,3,6,5,3,2,1};

for(int i1 = 0; i1 < array.length - 1; i1++){
  for(int i2 = i1 + 1; i2 < array.length; i2++){
    s.add(array[i1] + array[i2]);
  }
}

s.contains(num) で num が含まれるかどうかを boolean で返します。
また、ArrayList への変換が可能です。

ArrayList<Integer> a = new ArrayList<Integer>(s);

８、データの記録と操作５ Map

Map はキーと値のセットです。
値は重複が許されますが、キーは重複が許されません。
値は map.put(key, val) でセット、map.get(key) で値を取り出します。
サイズは map.size() で得ることができます。

次の例はまず値でソートし次にキーでソートしています。

Map<String, Integer> map = new HashMap<String, Integer>();

map.put("A", 2);
map.put("C", 1);
map.put("B", 1);

ArrayList entries = new ArrayList(map.entrySet());
Collections.sort(entries, new Comparator(){
  public int compare(Object obj1, Object obj2){
    Map.Entry ent1 =(Map.Entry)obj1;
    Map.Entry ent2 =(Map.Entry)obj2;
    String str1 = (String)ent1.getKey();
    String str2 = (String)ent2.getKey();
    Integer val1 = (Integer)ent1.getValue();
    Integer val2 = (Integer)ent2.getValue();
    if(val1 != val2){
      return val1 - val2;
    }
    else{
      return str1.compareTo(str2);
    }
  }
});

Set s = map.entrySet(); 
Iterator itr = s.iterator(); 
     
while(itr.hasNext()){
  Map.Entry obj = (Map.Entry)itr.next();        
  String key = (String)obj.getKey();  
  Integer value = (Integer)obj.getValue();
  System.out.println(key + ":" + value);
}

containsKey や containsValue で要素の有無を boolean で得ることができます。

９、グラフ

グラフとはある状態からある状態に移動できるかを記録したものです。

例えば下のコードは０→１、０→３の移動は許可するが０→２のアクセスを許可していません。
０→２へ行こうと思えば０→１→２と移動する必要があります。
グラフを使うと０→１へは移動できるが１→０への移動は禁止するなどの構造が実現できます。
グラフの移動は深さ優先探索などを使用して行うことができます。

int n = 4;

List<Queue<Integer>> list = new LinkedList<Queue<Integer>>();

for(int i = 0; i < n; i++){
  list.add(new LinkedList<Integer>());
}

list.get(0).add(1); // 0 → 1
list.get(0).add(3); // 0 → 3
list.get(1).add(0); // 1 → 0
list.get(1).add(2); // 1 → 2
list.get(2).add(1); // 2 → 1
list.get(2).add(3); // 2 → 3
list.get(3).add(0); // 3 → 0
list.get(3).add(2); // 3 → 2

９、文字列対策 String

TopCoder は英語のコンテストなので２バイト文字は出ません。
そして文字列に関しては String 型を標準で使います。
length()、substring(b, e)、equals(str) などをよく使う。
str.length() は文字列の長さを返す。
str.substring(b, e) は b 文字目から e-1 文字目までを String で返す。
str1.equals(str2) は str1 と str2 が同じかどうかを boolean で返す。
文字列の結合は str1 + str2 でできる。

例えば、最後の文字が "Z" で終わっているかを確認するには、

if((str.substring(str.length() - 1, str.length())).equals("Z")){
  // ok
}

また、次のようにも書ける。

if(str.charAt(str.length() - 1) == 'Z'){
  // ok
}

String には文字列を char 型に変換、辞書順に比較、文字列の検索、
文字列の置換、文字列の分割、数字を文字列に変換などの機能がある。
java では検索や置換の場合には正規表現が使える。

String にないものは自分で実装するしかない。
よくでそうなものはあらかじめ書いておくと良い。
例えば、以下は文字列を反転する。

// 文字列の反転
public static String reverse(String s){
  String s1 = s;
  if(s.length() > 1){
    char c = s.charAt(0);
    s1 = reverse(s.substring(1)) + c;
  }

  return s1;
}

これを応用すれば上から読んでも下から読んでも同じか？という判定もできる。

あと文字列内でソートを行うこともよくある。

// 文字列内ソート
private String str_sort(String str){
  byte[] b = str.getBytes();

  Arrays.sort(b);

  return new String(b);
}

１０、数学問題の対策

数学の問題はたくさんでます。
数列、順列、組み合わせの数、確率などがよく出る気がします。
高校の数学ができる程度の知識は必要だと思われます。

以下によく使いそうなものを用意してみました。

// 素数であるかを判定
private int isPrime(int n){
  int i;

  if(n < 2){
    return 0;
  }
  else if(n == 2){
    return 1;
  }

  if(n % 2 == 0){
    return 0;
  }
 
  for(i = 3; i * i <= n; i += 2){
    if(n % i == 0){
      return 0;
    }
  }

  return 1;
}

// 最大公約数
private int gcd(int a, int b){
  return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
private int lcm(int a, int b){
  return a * b / gcd(a, b);
}

// 素因数分解
public class factorization {
  public static void main(String[] args){
    int m = 1234567890;
    // 2 で割れるだけ割り算する
    while(m % 2 == 0){
      System.out.print(2);
      System.out.print(" ");
      m /= 2;
    }
    // 奇数で割り算していく
    for(int i = 3; i * i <= m; i += 2){
      while(m % i == 0){
        System.out.print(i + " ");
        m /= i;
      }
    }
    if(m > 1)System.out.println(m);
  }
}

// 順列の作成
public class Permutation{
  static void print_perm(int[] perm){
    for(int x: perm){
      System.out.print(x + " ");
    }
    System.out.println();
  }
  
  static void make_perm(int n, int[] perm, boolean[] flag){
    if(n == perm.length){
      print_perm(perm);
    } else {
      for(int i = 1; i <= perm.length; i++){
        if(flag[i]) continue;
        perm[n] = i;
        flag[i] = true;
        make_perm(n + 1, perm, flag);
        flag[i] = false;
      }
    }
  }

  public static void main(String[] args){
    make_perm(0, new int [4], new boolean [5]);
  }
}