補講：基本情報処理技術者試験 科目Bのアルゴリズム問題集

整数型: a ← 5
整数型: b ← 3
整数型: ans ← a × b + a
ans を出力

public class Main {
    public static void main(String[] args) {
        int a = 5;
        int b = 3;
        int ans = a * b + a;
        System.out.println(ans);
    }
}

整数型: score ← 75
文字列型: result ← "不合格"

if (score ≥ 80)
  result ← "優"
elseif (score ≥ 60)
  result ← "良"
else
  result ← "不可"
endif

result を出力

public class Main {
    public static void main(String[] args) {
        int score = 75;
        String result = "不合格";

        if (score >= 80) {
            result = "優";
        } else if (score >= 60) {
            result = "良";
        } else {
            result = "不可";
        }
        System.out.println(result);
    }
}

整数型: i ← 1
整数型: count ← 0

while (i ≤ 10)
  count ← count + i
  i ← i + 3
endwhile

count を出力

public class Main {
    public static void main(String[] args) {
        int i = 1;
        int count = 0;

        while (i <= 10) {
            count = count + i;
            i = i + 3;
        }
        System.out.println(count);
    }
}

整数型の配列: nums ← {10, 20, 30, 40, 50}
整数型: total ← 0
整数型: k

for (k を 1 から 3 まで 1 ずつ増やす)
  total ← total + nums[k]
endfor

total を出力

public class Main {
    public static void main(String[] args) {
        int[] nums = {10, 20, 30, 40, 50};
        int total = 0;

        // Javaの配列は0番目から始まるため、
        // 擬似言語の「1から3まで」は「0から2まで」に対応します。
        for (int k = 0; k < 3; k++) { 
            total = total + nums[k];
        }
        System.out.println(total);
    }
}

○文字列型: checkValue(整数型: n)
  if ((n mod 3 = 0) and (n mod 5 = 0))
    return "A"
  elseif (n mod 3 = 0)
    return "B"
  else
    return "C"
  endif

public class Main {
    public static void main(String[] args) {
        System.out.println(checkValue(15));
    }

    public static String checkValue(int n) {
        // Javaでは「mod」の代わりに「%」、「and」の代わりに「&&」を使います
        if ((n % 3 == 0) && (n % 5 == 0)) {
            return "A";
        } else if (n % 3 == 0) {
            return "B";
        } else {
            return "C";
        }
    }
}

整数型の配列: mat ← {{1, 2, 3}, 
                     {4, 5, 6}, 
                     {7, 8, 9}}
整数型: sum ← 0
整数型: i

for (i を 1 から 3 まで 1 ずつ増やす)
  sum ← sum + mat[i][i]
endfor

sum を出力

public class Main {
    public static void main(String[] args) {
        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int sum = 0;
        // Javaは0始まりなので、mat[i][i]でアクセスするために0から2まで回す
        for (int i = 0; i < 3; i++) {
            sum = sum + mat[i][i];
        }
        System.out.println(sum);
    }
}

整数型の配列: scores ← {10, 50, 30, 20, 40}
整数型: maxVal ← scores[1]
整数型: i

for (i を 2 から scoresの要素数 まで 1 ずつ増やす)
  if (scores[i] > maxVal)
    maxVal ← scores[i]
  endif
endfor

maxVal を出力

public class Main {
    public static void main(String[] args) {
        int[] scores = {10, 50, 30, 20, 40};
        int maxVal = scores[0]; // Javaは0番目が先頭

        // 2番目の要素(index 1)から最後まで比較
        for (int i = 1; i < scores.length; i++) {
            if (scores[i] > maxVal) {
                maxVal = scores[i];
            }
        }
        System.out.println(maxVal);
    }
}

○整数型: sigma(整数型: n)
  if (n = 0)
    return 0
  endif
  return n + sigma(n - 1)

public class Main {
    public static void main(String[] args) {
        System.out.println(sigma(3));
    }

    public static int sigma(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sigma(n - 1);
    }
}

整数型: count ← 0
整数型: i, j

for (i を 1 から 3 まで 1 ずつ増やす)
  for (j を 1 から i まで 1 ずつ増やす)
    count ← count + 1
  endfor
endfor

count を出力

public class Main {
    public static void main(String[] args) {
        int count = 0;
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= i; j++) {
                count = count + 1;
            }
        }
        System.out.println(count);
    }
}

整数型の配列: data ← {1, 2, 3, 4, 5}
整数型: n ← dataの要素数
整数型: i, temp

for (i を 1 から (n ÷ 2) の商 まで 1 ずつ増やす)
  /* 値の入れ替え */
  temp ← data[i]
  data[i] ← data[n - i + 1]
  data[n - i + 1] ← temp
endfor

data の全要素を出力

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5};
        int n = data.length;
        int temp;

        // Javaの添字は0〜(n-1)。
        // 擬似言語の「iを1から n/2」は、Javaでは「iを0から n/2 - 1」まで等の調整が必要ですが、
        // ここではロジックを分かりやすくJava風に書き直します。
        // 左端(i)と右端(n-1-i)を交換します。
        for (int i = 0; i < n / 2; i++) {
            temp = data[i];
            data[i] = data[n - 1 - i];
            data[n - 1 - i] = temp;
        }
        System.out.println(Arrays.toString(data));
    }
}

○整数型: binarySearch(整数型の配列: data, 整数型: target)
  整数型: low ← 1
  整数型: high ← dataの要素数
  整数型: middle

  while (low ≤ high)
    middle ← (low + high) ÷ 2
    if (data[middle] = target)
      return middle
    elseif (data[middle] < target)
      low ← middle + 1
    else
      high ← middle - 1
    endif
  endwhile
  return -1

public class Main {
    public static void main(String[] args) {
        int[] data = {10, 20, 30, 40, 50, 60, 70};
        System.out.println(binarySearch(data, 20));
    }

    public static int binarySearch(int[] data, int target) {
        int low = 0; // Javaは0始まり
        int high = data.length - 1;
        int middle;

        while (low <= high) {
            middle = (low + high) / 2;
            System.out.println("middle: " + middle); // 変化を確認

            if (data[middle] == target) {
                return middle;
            } else if (data[middle] < target) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }
}

文字列型: s ← "AAABCCCC"
文字列型: res ← ""
整数型: count ← 1
整数型: i

for (i を 1 から sの文字数 - 1 まで 1 ずつ増やす)
  if (s の i 文字目 = s の (i + 1) 文字目)
    count ← count + 1
  else
    res ← res + s の i 文字目 + countを文字列にしたもの
    count ← 1
  endif
endfor
res ← res + s の 末尾の文字 + countを文字列にしたもの

res を出力

public class Main {
    public static void main(String[] args) {
        String s = "AAABCCCC";
        String res = "";
        int count = 1;

        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                count++;
            } else {
                res = res + s.charAt(i) + count;
                count = 1;
            }
        }
        // 最後の部分を追加
        res = res + s.charAt(s.length() - 1) + count;
        System.out.println(res);
    }
}

○整数型: calc(整数型: a, 整数型: b)
  if (b = 0)
    return a
  endif
  return calc(b, a mod b)

public class Main {
    public static void main(String[] args) {
        System.out.println(calc(24, 9));
    }

    public static int calc(int a, int b) {
        if (b == 0) {
            return a;
        }
        return calc(b, a % b);
    }
}

整数型の配列: arr ← {1, 2, 3, 4, 5}
整数型: temp
整数型: i

temp ← arr[1]
for (i を 1 から arrの要素数 - 1 まで 1 ずつ増やす)
  arr[i] ← arr[i + 1]
endfor
arr[arrの要素数] ← temp

arr を出力

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int temp = arr[0]; // 先頭を退避

        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
        }
        arr[arr.length - 1] = temp; // 末尾に代入

        System.out.println(Arrays.toString(arr));
    }
}

整数型の配列: stack ← {}
push(stack, 10)
push(stack, 20)
整数型: a ← pop(stack)
push(stack, 30)
push(stack, 40)
整数型: b ← pop(stack)
整数型: c ← pop(stack)

(a + b - c) を出力

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> stack = new ArrayList<>();
        
        stack.add(10); // push
        stack.add(20); // push
        
        int a = stack.remove(stack.size() - 1); // pop
        
        stack.add(30); // push
        stack.add(40); // push
        
        int b = stack.remove(stack.size() - 1); // pop
        int c = stack.remove(stack.size() - 1); // pop
        
        System.out.println(a + b - c);
    }
}

クラス ListElement
  メンバ変数 val: 文字列型
  メンバ変数 next: ListElement型
  
○手続名: deleteSecond(ListElement: head)
  ListElement: p1
  ListElement: p2
  
  /* p1は1番目の要素(A)を指す */
  p1 ← head.next
  
  /* p2は2番目の要素(B)を指す */
  p2 ← p1.next
  
  /* リンクのつなぎ替え */
  p1.next ← p2.next

class ListElement {
    String val;
    ListElement next;
    ListElement(String val) { this.val = val; }
}

public class Main {
    public static void main(String[] args) {
        // リストの構築: Head -> A -> B -> C
        ListElement head = new ListElement("Head");
        ListElement a = new ListElement("A");
        ListElement b = new ListElement("B");
        ListElement c = new ListElement("C");
        
        head.next = a;
        a.next = b;
        b.next = c;
        
        // 削除処理
        ListElement p1 = head.next; // A
        ListElement p2 = p1.next;   // B
        p1.next = p2.next;          // A -> C
        
        // 結果確認
        System.out.println(head.next.val + " -> " + head.next.next.val);
    }
}

    1
   / \
  2   3
 /
4

クラス Node
  メンバ変数 val: 整数型
  メンバ変数 left: Node型
  メンバ変数 right: Node型

○手続名: traverse(Node: n)
  if (n = nil)
    return
  endif
  traverse(n.left)
  n.val を出力
  traverse(n.right)

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

public class Main {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        
        n1.left = n2; n1.right = n3;
        n2.left = n4;
        
        traverse(n1);
    }

    static void traverse(Node n) {
        if (n == null) return;
        traverse(n.left);
        System.out.println(n.val);
        traverse(n.right);
    }
}

○整数型: getBit(整数型: val, 整数型: n)
  整数型: mask ← 1
  /* 1 を (n-1) ビット左にシフトする */
  mask ← mask << (n - 1)
  
  if ((val and mask) ≠ 0)
    return 1
  else
    return 0
  endif

public class Main {
    public static void main(String[] args) {
        System.out.println(getBit(20, 3));
    }

    static int getBit(int val, int n) {
        int mask = 1;
        mask = mask << (n - 1);
        
        if ((val & mask) != 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

クラス Counter
  メンバ変数 count: 整数型
  
  ○Counter()  /* コンストラクタ */
    count ← 0
    
  ○add(整数型: n)
    count ← count + n
    
  ○clear()
    count ← 0

/* メイン処理 */
Counter: c1 ← Counter()
Counter: c2 ← Counter()

c1.add(5)
c2.add(10)
c1.add(3)
c2.clear()
c2.add(2)

(c1.count + c2.count) を出力

class Counter {
    int count;
    Counter() { count = 0; }
    void add(int n) { count += n; }
    void clear() { count = 0; }
}

public class Main {
    public static void main(String[] args) {
        Counter c1 = new Counter();
        Counter c2 = new Counter();
        
        c1.add(5);
        c2.add(10);
        c1.add(3);
        c2.clear();
        c2.add(2);
        
        System.out.println(c1.count + c2.count);
    }
}

整数型の配列: data ← {4, 3, 1, 5, 2}
整数型: i, j, minIndex, temp

for (i を 1 から dataの要素数 - 1 まで 1 ずつ増やす)
  minIndex ← i
  
  /* 未ソート部分から最小値の位置を探す */
  for (j を i + 1 から dataの要素数 まで 1 ずつ増やす)
    if ( [　空欄　] )
      minIndex ← j
    endif
  endfor
  
  /* 値の交換 */
  temp ← data[i]
  data[i] ← data[minIndex]
  data[minIndex] ← temp
endfor

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] data = {4, 3, 1, 5, 2};
        int minIndex, temp;
        
        for (int i = 0; i < data.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                // Javaは0始まりですがロジックは同じ
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }
            // 交換
            temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }
        System.out.println(Arrays.toString(data));
    }
}

整数型の配列: table ← {-1, -1, -1, ...} （要素数10）
整数型の配列: data ← {15, 25, 35}
整数型: i, pos

for (i を 1 から 3 まで 1 ずつ増やす)
    pos ← data[i] mod 10
    /* 空きが見つかるまで位置をずらす */
    while (table[pos] ≠ -1)
        pos ← (pos + 1) mod 10
    endwhile
    table[pos] ← data[i]
endfor
35 が格納された pos を出力

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] table = new int[10];
        Arrays.fill(table, -1);
        int[] data = {15, 25, 35};
        int finalPos = -1;

        for (int x : data) {
            int pos = x % 10;
            while (table[pos] != -1) {
                pos = (pos + 1) % 10;
            }
            table[pos] = x;
            if (x == 35) finalPos = pos;
        }
        System.out.println(finalPos);
    }
}

整数型の配列: arrA ← {2, 5, 9}
整数型の配列: arrB ← {1, 6, 8}
整数型の配列: arrC ← {} （要素数6の空配列）
整数型: a ← 1, b ← 1, c ← 1

while (a ≤ 3 and b ≤ 3)
    if (arrA[a] < arrB[b])
        arrC[c] ← arrA[a]
        a ← a + 1
    else
        arrC[c] ← arrB[b]
        b ← b + 1
    endif
    c ← c + 1
endwhile
/* 残りの要素をコピーする処理は省略 */
arrC[4] を出力

public class Main {
    public static void main(String[] args) {
        int[] arrA = {2, 5, 9};
        int[] arrB = {1, 6, 8};
        int[] arrC = new int[6];
        int a = 0, b = 0, c = 0;

        // 擬似言語の1始まりを0始まりに読み替え
        while (a < arrA.length && b < arrB.length) {
            if (arrA[a] < arrB[b]) {
                arrC[c++] = arrA[a++];
            } else {
                arrC[c++] = arrB[b++];
            }
        }
        // Java配列は0から始まるため、4番目はインデックス3
        System.out.println(arrC[3]); 
    }
}

整数型: a ← 10
整数型: b ← 6
整数型: temp

/* 値の交換（XORスワップアルゴリズムの一部） */
temp ← a xor b
a ← temp
temp ← a xor b
/* ここでの temp の値を出力 */
temp を出力

public class Main {
    public static void main(String[] args) {
        int a = 10; // 1010
        int b = 6;  // 0110
        
        int temp = a ^ b; // 1100 (12)
        a = temp;
        
        temp = a ^ b; // 1100 ^ 0110 = 1010 (10)
        
        System.out.println(temp);
    }
}

整数型の配列: adj ← {
  {0, 1, 1}, 
  {1, 0, 1}, 
  {1, 1, 0} 
}
整数型: count ← 0
整数型: i

/* ノード2（配列の2行目）の接続数をカウント */
for (i を 1 から 3 まで 1 ずつ増やす)
    if (adj[2][i] = 1)
        count ← count + 1
    endif
endfor
count を出力

public class Main {
    public static void main(String[] args) {
        int[][] adj = {
            {0, 1, 1},
            {1, 0, 1},
            {1, 1, 0}
        };
        int count = 0;
        // ノード2に対応するのはインデックス1
        for (int i = 0; i < 3; i++) {
            if (adj[1][i] == 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}

/* インデックス:    1   2   3  */
/* 値(data):      10, 20, 30 */
整数型の配列: next ← {2,  3, -1}
整数型の配列: prev ← {-1, 1,  2}

整数型: deleteIdx ← 2  /* 削除する要素(20)の添字 */
整数型: p ← prev[deleteIdx] /* 1 (10の場所) */
整数型: n ← next[deleteIdx] /* 3 (30の場所) */

/* 削除処理：ポインタの付け替え */
if (p ≠ -1)
    next[p] ← n
endif
if (n ≠ -1)
    prev[n] ← p
endif

next[1] を出力

public class Main {
    public static void main(String[] args) {
        // インデックス0は使わず、1,2,3を使用すると仮定
        int[] next = {0, 2, 3, -1};
        int[] prev = {0, -1, 1, 2};
        
        int deleteIdx = 2;
        int p = prev[deleteIdx]; // 1
        int n = next[deleteIdx]; // 3
        
        if (p != -1) next[p] = n;
        if (n != -1) prev[n] = p;
        
        System.out.println(next[1]);
    }
}

整数型の配列: nums ← {4, 2, 5, 1, 3}
整数型: i, j, temp
/* 末尾から先頭に向かって順に比較・交換を行う */
for (i を 1 から numsの要素数 - 1 まで 1 ずつ増やす)
    for (j を numsの要素数 から i + 1 まで 1 ずつ減らす)
        if (nums[j] < nums[j - 1])
            /* 交換処理 */
            temp ← nums[j]
            nums[j] ← nums[j - 1]
            nums[j - 1] ← temp
        endif
    endfor
endfor
nums を出力

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {4, 2, 5, 1, 3};
        // 外側のループ1回分 (i=0に対応)
        for (int j = nums.length - 1; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}

整数型の配列: cards ← {10, 5, 8, 3, 6}
整数型: i, j, temp

/* 2番目の要素から順に、適切な位置に挿入していく */
for (i を 2 から cardsの要素数 まで 1 ずつ増やす)
    temp ← cards[i]
    j ← i - 1
    while (j ≥ 1 and cards[j] > temp)
        cards[j + 1] ← cards[j]
        j ← j - 1
    endwhile
    cards[j + 1] ← temp
endfor

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] cards = {10, 5, 8, 3, 6};
        // Javaでは i=1 が擬似言語の i=2 に相当
        for (int i = 1; i <= 2; i++) { // i=2(3番目の要素)まで実行
            int temp = cards[i];
            int j = i - 1;
            while (j >= 0 && cards[j] > temp) {
                cards[j + 1] = cards[j];
                j--;
            }
            cards[j + 1] = temp;
        }
        System.out.println(Arrays.toString(cards));
    }
}

/* data は整数の配列として各ビットを表す {1, 0, 1, 1, 0, 0, 1} */
整数型の配列: data ← {1, 0, 1, 1, 0, 0, 1}
整数型: sum ← 0
整数型: k, parity

for (k を 1 から 7 まで 1 ずつ増やす)
    sum ← sum + data[k]
endfor

if (sum mod 2 = 0)
    parity ← 0
else
    parity ← 1
endif

parity を出力

public class Main {
    public static void main(String[] args) {
        int[] data = {1, 0, 1, 1, 0, 0, 1};
        int sum = 0;
        for (int bit : data) {
            sum += bit;
        }
        int parity;
        if (sum % 2 == 0) {
            parity = 0;
        } else {
            parity = 1;
        }
        System.out.println(parity);
    }
}

配列の配列: adj ← {
    {},        /* index 0: 未使用 */
    {2, 3},    /* index 1: 1から2と3へ */
    {4},       /* index 2: 2から4へ */
    {},        /* index 3: 行き先なし */
    {}         /* index 4: 行き先なし */
}

○visit(整数型: n)
    n を出力
    整数型: i
    for (i を 1 から adj[n]の要素数 まで 1 ずつ増やす)
        visit(adj[n][i])
    endfor

public class Main {
    static int[][] adj = {
        {},
        {2, 3},
        {4},
        {},
        {}
    };

    public static void main(String[] args) {
        visit(1);
    }

    public static void visit(int n) {
        System.out.println(n);
        for (int neighbor : adj[n]) {
            visit(neighbor);
        }
    }
}

/* 状態遷移表: transition[state][input] */
整数型の配列: transition ← {
  {0, 1},  /* state 0 のとき: 入力0なら0, 入力1なら1へ */
  {2, 1},  /* state 1 のとき: 入力0なら2, 入力1なら1へ */
  {0, 2}   /* state 2 のとき: 入力0なら0, 入力1なら2へ */
}
整数型の配列: inputs ← {1, 0, 1, 1}
整数型: state ← 0
整数型: k

for (k を 1 から inputsの要素数 まで 1 ずつ増やす)
    state ← transition[state][inputs[k] + 1] 
    /* ※擬似言語の配列添字は1始まりのため、input(0/1)に+1して列を指定 */
endfor
state を出力

public class Main {
    public static void main(String[] args) {
        // Javaは0始まりなのでそのまま使用
        int[][] transition = {
            {0, 1}, // state 0
            {2, 1}, // state 1
            {0, 2}  // state 2
        };
        int[] inputs = {1, 0, 1, 1};
        int state = 0;

        for (int input : inputs) {
            state = transition[state][input];
        }
        System.out.println(state);
    }
}

整数型の配列: data ← {2, 6, 1, 7, 4}
整数型: pivot ← data[dataの要素数]  /* ピボットは最後の 4 */
整数型: i ← 0  /* 小さい要素の境界線 */
整数型: j, temp

/* 1番目から (要素数-1) 番目まで走査 */
for (j を 1 から dataの要素数 - 1 まで 1 ずつ増やす)
    if (data[j] < pivot)
        i ← i + 1
        /* data[i] と data[j] を交換 */
        temp ← data[i]
        data[i] ← data[j]
        data[j] ← temp
    endif
endfor

/* 最後にピボットを境界線の隣に移動 */
temp ← data[i + 1]
data[i + 1] ← data[dataの要素数]
data[dataの要素数] ← temp

data を出力

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] data = {2, 6, 1, 7, 4};
        int pivot = data[data.length - 1]; // pivot = 4
        int i = -1; // Javaは0始まりなので、擬似言語の0に対応するのは-1

        for (int j = 0; j < data.length - 1; j++) {
            if (data[j] < pivot) {
                i++;
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        // ピボットの移動
        int temp = data[i + 1];
        data[i + 1] = data[data.length - 1];
        data[data.length - 1] = temp;

        System.out.println(Arrays.toString(data));
    }
}

/* 木構造のデータ（葉のスコア）を配列で表現 */
/* index 0 は根。1,2 はその子。3,4,5,6 は葉 */
整数型の配列: scores ← {0, 0, 0, 5, 3, 8, 1}

○整数型: minimax(整数型: node, ブール型: isMax)
    /* 葉ノード（これ以上子がない）なら値を返す */
    if (node ≥ 3)
        return scores[node]
    endif

    if (isMax = true)
        /* 自分: 子ノード(左:2*node+1, 右:2*node+2)のうち大きい方を選ぶ */
        return max(minimax(2 * node + 1, false), minimax(2 * node + 2, false))
    else
        /* 相手: 小さい方を選ぶ */
        return min(minimax(2 * node + 1, true), minimax(2 * node + 2, true))
    endif

public class Main {
    static int[] scores = {0, 0, 0, 5, 3, 8, 1}; // index 0~6

    public static void main(String[] args) {
        System.out.println(minimax(0, true));
    }

    public static int minimax(int node, boolean isMax) {
        // 簡易的な判定：配列外なら終了とみなす等の処理が必要だが
        // ここでは問題文の通りnode>=3で葉とする
        if (node >= 3) {
            return scores[node];
        }

        if (isMax) {
            int left = minimax(2 * node + 1, false);
            int right = minimax(2 * node + 2, false);
            return Math.max(left, right);
        } else {
            int left = minimax(2 * node + 1, true);
            int right = minimax(2 * node + 2, true);
            return Math.min(left, right);
        }
    }
}

整数型の配列: weights ← {2, 3}  /* 荷物の重さ */
整数型の配列: values  ← {3, 4}  /* 荷物の価値 */
整数型の配列: dp ← {0, 0, 0, 0, 0, 0} /* 重さ0〜5に対応 */
整数型: capacity ← 5
整数型: i, w

/* 荷物の種類ごとにDPテーブルを更新 */
for (i を 1 から 2 まで 1 ずつ増やす)
    /* 重い方から更新することで、同じ荷物の重複利用を防ぐ（0/1ナップサック） */
    for (w を capacity から weights[i] まで 1 ずつ減らす)
        if (dp[w] < dp[w - weights[i]] + values[i])
            dp[w] ← dp[w - weights[i]] + values[i]
        endif
    endfor
endfor
dp[5] を出力

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] weights = {2, 3};
        int[] values = {3, 4};
        int capacity = 5;
        int[] dp = new int[capacity + 1]; // 0~5

        for (int i = 0; i < weights.length; i++) {
            int weight = weights[i];
            int value = values[i];
            // 重複なし(0/1)のため、後ろからループ
            for (int w = capacity; w >= weight; w--) {
                if (dp[w] < dp[w - weight] + value) {
                    dp[w] = dp[w - weight] + value;
                }
            }
        }
        System.out.println(dp[5]);
    }
}

整数型の配列: coef ← {3, 2, 1, 5} /* 係数: 3x^3 + 2x^2 + 1x + 5 */
整数型: x ← 2
整数型: result ← coef[1] /* 最上位の係数(3)で初期化 */
整数型: i

for (i を 2 から 4 まで 1 ずつ増やす)
    result ← result × x + coef[i]
endfor
result を出力

public class Main {
    public static void main(String[] args) {
        int[] coef = {3, 2, 1, 5};
        int x = 2;
        int result = coef[0]; // 最上位の係数
        
        for (int i = 1; i < coef.length; i++) {
            result = result * x + coef[i];
        }
        System.out.println(result);
    }
}

整数型: base ← 2
整数型: exp ← 10   /* 2進数で 1010 */
整数型: mod ← 1000
整数型: ans ← 1

while (exp > 0)
    /* 指数の最下位ビットが 1 なら現在の base を掛ける */
    if (exp mod 2 = 1)
        ans ← (ans × base) mod mod
    endif
    
    /* base を二乗して、指数を右にシフト */
    base ← (base × base) mod mod
    exp ← exp div 2
endwhile
ans を出力

【解答】

public class Main {
    public static void main(String[] args) {
        long base = 2;
        long exp = 10;
        long mod = 1000;
        long ans = 1;

        while (exp > 0) {
            if (exp % 2 == 1) {
                ans = (ans * base) % mod;
            }
            base = (base * base) % mod;
            exp = exp / 2;
        }
        System.out.println(ans);
    }
}

整数型: p ← 13  /* 素数 */
整数型: g ← 6   /* 生成元 */
整数型: secretA ← 3
整数型: secretB ← 2
整数型: publicA, publicB, keyA, keyB

/* 公開鍵の生成と交換 */
publicA ← modPow(g, secretA, p)
publicB ← modPow(g, secretB, p)

/* 相手の公開鍵と自分の秘密値から共通鍵を生成 */
keyA ← modPow(publicB, secretA, p)
keyB ← modPow(publicA, secretB, p)

keyA を出力

public class Main {
    public static void main(String[] args) {
        long p = 13;
        long g = 6;
        long secretA = 3;
        long secretB = 2;
        
        long publicA = modPow(g, secretA, p); // 8
        long publicB = modPow(g, secretB, p); // 10
        
        long keyA = modPow(publicB, secretA, p); // 10^3 % 13 = 12
        
        System.out.println(keyA);
    }

    public static long modPow(long base, long exp, long mod) {
        long res = 1;
        for (int i = 0; i < exp; i++) {
            res = (res * base) % mod;
        }
        return res;
    }
}

整数型の配列: heap ← {}
整数型: size ← 0

○pushHeap(整数型: val)
    size ← size + 1
    整数型: k ← size
    heap[k] ← val
    
    /* 親と比較して、親より大きければ交換（アップヒープ） */
    while (k > 1 and heap[k] > heap[k ÷ 2])
        整数型: parent ← k ÷ 2
        整数型: temp ← heap[k]
        heap[k] ← heap[parent]
        heap[parent] ← temp
        k ← parent
    endwhile

import java.util.ArrayList;
import java.util.List;

public class Main {
    // 1始まりのインデックスを模倣するためにダミー要素を入れる
    static List<Integer> heap = new ArrayList<>();
    
    public static void main(String[] args) {
        heap.add(0); // index 0 (dummy)
        int[] data = {10, 30, 20, 5, 40};
        for (int val : data) {
            pushHeap(val);
        }
        System.out.println(heap.get(1)); // 根を出力
    }

    public static void pushHeap(int val) {
        heap.add(val);
        int k = heap.size() - 1;
        while (k > 1 && heap.get(k) > heap.get(k / 2)) {
            int parent = k / 2;
            int temp = heap.get(k);
            heap.set(k, heap.get(parent));
            heap.set(parent, temp);
            k = parent;
        }
    }
}

文字列型の配列: tokens ← {"3", "4", "+", "2", "*"}
整数型のスタック: stack ← {}
整数型: a, b, i

for (i を 1 から tokensの要素数 まで 1 ずつ増やす)
    if (tokens[i] が数値である)
        push(stack, tokens[i]を整数に変換)
    else
        b ← pop(stack)
        a ← pop(stack)
        if (tokens[i] = "+") push(stack, a + b)
        elseif (tokens[i] = "*") push(stack, a * b)
        endif
    endif
endfor
pop(stack) を出力

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String[] tokens = {"3", "4", "+", "2", "*"};
        Stack<Integer> stack = new Stack<>();
        
        for (String token : tokens) {
            if (token.matches("\\d+")) {
                stack.push(Integer.parseInt(token));
            } else {
                int b = stack.pop();
                int a = stack.pop();
                if (token.equals("+")) stack.push(a + b);
                else if (token.equals("*")) stack.push(a * b);
            }
        }
        System.out.println(stack.pop());
    }
}

配列の配列: adj ← {
    {},        /* 0: 未使用 */
    {2, 3},    /* 1: 1から2, 3へ */
    {4, 5},    /* 2: 2から4, 5へ */
    {6},       /* 3: 3から6へ */
    {}, {}, {} /* 4, 5, 6: 行き先なし */
}
整数型のキュー: queue ← {}

enqueue(queue, 1) /* 開始ノード */

while (queue が空でない)
    整数型: n ← dequeue(queue)
    n を出力
    
    整数型: i
    for (i を 1 から adj[n]の要素数 まで 1 ずつ増やす)
        enqueue(queue, adj[n][i])
    endfor
endwhile

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int[][] adj = {
            {},
            {2, 3},
            {4, 5},
            {6},
            {}, {}, {}
        };
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        
        while (!queue.isEmpty()) {
            int n = queue.poll();
            System.out.println(n);
            for (int neighbor : adj[n]) {
                queue.add(neighbor);
            }
        }
    }
}

文字列型: text ← "BABABABC"
文字列型: pattern ← "ABC"
整数型: i, j
ブール型: match ← false

for (i を 1 から (textの文字数 - patternの文字数 + 1) まで 1 ずつ増やす)
    match ← true
    for (j を 1 から patternの文字数 まで 1 ずつ増やす)
        if (text[i + j - 1] ≠ pattern[j])
            match ← false
            break /* 内側のループを抜ける */
        endif
    endfor
    
    if (match = true)
        break /* 外側のループを抜ける */
    endif
endfor
i を出力

public class Main {
    public static void main(String[] args) {
        String text = "BABABABC";
        String pattern = "ABC";
        int n = text.length();
        int m = pattern.length();
        boolean match = false;
        int foundIndex = -1;

        for (int i = 0; i <= n - m; i++) {
            match = true;
            for (int j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                foundIndex = i + 1; // 1始まりに合わせる
                break;
            }
        }
        System.out.println(foundIndex);
    }
}