メモリ使用量の見積もり

プログラムが使用するメモリ容量を概算する方法：

1 MB = 1024 × 1024 バイト
int 型は 4 バイト
→ 必要メモリ (MB) = (int の要素数 × 4) / (1024 × 1024)

他のデータ型も同様に、各要素のバイト数を掛け合わせて計算する。

実行時間の計測（C++）

CPU時間を用いてコードの実行時間を計測する例：

#include <ctime>
#include <iostream>
using namespace std;

int main() {
    clock_t start = clock();

    // 実行したい処理

    clock_t end = clock();
    double elapsed = static_cast<double>(end - start) / CLOCKS_PER_SEC;
    cout << "実行時間: " << elapsed << " 秒" << endl;
    return 0;
}

Javaでの高速入出力

標準入出力を高速化するためのテンプレート：

import java.io.*;

public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer tokenizer = new StreamTokenizer(reader);
    static PrintWriter writer = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        writer.println("sample");
        double[] arr = new double[10];
        for (int i = 0; i < 4; i++) {
            arr[i] = nextDouble();
        }
        for (int i = 0; i < 4; i++) {
            writer.println(arr[i]);
        }
        writer.flush(); // 必須
    }

    static double nextDouble() throws IOException {
        tokenizer.nextToken();
        return tokenizer.nval;
    }
}

整数分割問題（動的計画法）

整数 n を、各要素が m 以下となるように分割する方法の総数を求める。同じ数を複数回使ってもよい。

再帰関係式は以下の通り：

• もし n == 1 または m == 1 なら、分割方法は 1 通り（すべて 1）。
• もし n < m なら、m は意味を持たないため、dp[n][m] = dp[n][n]。
• もし n == m なら、n 自体を一つの分割として加え、残りは m-1 以下の分割：
  dp[n][m] = dp[n][m-1] + 1。
• もし n > m なら、二つのケースに分かれる：
  • 少なくとも一つ m を含む場合 → 残り n - m を m 以下で分割：dp[n - m][m]
  • m を一切使わない場合 → 全て m - 1 以下で分割：dp[n][m - 1]
  よって：dp[n][m] = dp[n - m][m] + dp[n][m - 1]

この漸化式に基づいて動的計画法により解を構築できる。