クリスマスに競技プログラミングといた/その1

メリークリスマス。クリスマスはギークハウス高円寺と水道橋でしろくまさんのustみながらコードを書いていましたごんげです。
時間が空いてしまいましたが久しぶりに競技プログラミングの問題解きました。
まぁ@mojaieさんがもうだいぶ先まで解いてくれてるから、彼のコードと見比べて見るのもいいですね。
それでは早速いきます。前回の続きでlevel0の5問目からです。
==

0005: GCD and LCM

問題

Write a program which computes the greatest common divisor (GCD) and the least common multiple (LCM) of given a and b (0 < a, b ≤ 2,000,000,000). You can supporse that LCM(a, b) ≤ 2,000,000,000.
GCD and LCM | Aizu Online Judge

回答

import java.util.*;

class GCD {
    public static void main (String args[]) {
        Scanner scn = new Scanner(System.in);
        int a = scn.nextInt();
        int b = scn.nextInt();
        int i = 0;
        ArrayList<Integer> gcd = new ArrayList<Integer>();
        while (i>=0) {
            if (i==0) {
                gcd.add(a % b); 
            } else if (i==1) {
                gcd.add(b % gcd.get(i-1));
            } else {
                gcd.add(gcd.get(i-2) % gcd.get(i-1));
            }   
            if (gcd.get(i)==0) {
                System.out.println("GCD=" + gcd.get(i-1));
                int lcm = a * b / gcd.get(i-1);
                System.out.println("LCM=" + lcm);
                break;
            }   
            i++;        
        }   
    }   
}

感想

最大公約数と最小公倍数を求める問題。アルゴリズムはユーグリッドの互除法です。これですね

ユーグリッドの互除法：ユークリッドの互除法 - Wikipedia

まぁこれ自体は複雑なアルゴリズムなわけではないのですが、なんでこの計算方法で最大公約数が出せるのか・・・誰か説明してくれ。ぶっちゃけよくわからんでした。数学って難しいな。

==

0006: Reverse Sequence

問題

Write a program which reverses a given string str.

回答

import java.io.*;
import java.util.*;

class ReverseSequence {
    public static void main (String args[]) throws java.io.IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String input= in.readLine();
        ArrayList<Character> output = new ArrayList<Character>();
        for(int i=input.length()-1;i>=0;i--) {
            output.add(input.charAt(i));
        }   
        System.out.println(output);
    }   
}

感想

また配列を逆から回してる。なんかいいやり方ありそうな気がするけど。っていうか今思うとこれ出力おかしいよね・・・。

なんかもう少しあるのでわけて書きます
その2はこちら
http://d.hatena.ne.jp/gong023/20111225/1324825134