長さ N の 0 埋め・値埋め、2 次元配列、可変リスト。
IntArray(5) → [0, 0, 0, 0, 0] fill(-1) → [-1,-1,-1,-1,-1] 2D h×w → [[0,0,0], [0,0,0]]
vector<int> a(n); // 0 埋め vector<int> b(n, -1); // -1 埋め vector<vector<int>> g(h, vector<int>(w)); // 2次元 // vector<int> list; list.push_back(x);
値だけ / 添字だけ / 添字と値の両方を回す 3 パターン。
[10,20,30] → i=0:10 i=1:20 i=2:30
for (int x : a) { } // 値
for (int i = 0; i < (int)a.size(); i++){ } // 添字
末尾の add/pop は O(1)。先頭の挿入/削除は配列だと O(N)、多用するなら Deque。
[1,2] +3(末尾) → [1,2,3] pop → 3, 残 [1,2] [1,2] 先頭0 → [0,1,2] shift → 0, 残 [1,2]
vector<int> a = {1, 2};
a.push_back(3); // 末尾追加
int last = a.back(); a.pop_back(); // 末尾取り出し
a.insert(a.begin(), 0); // 先頭挿入 (O(N))
a.erase(a.begin()); // 先頭削除 (O(N)) → deque 推奨
2 つの列をつなぐ。両方ソート済みなら merge で O(N) に整列したまま結合。
[1,2] ++ [3,4] → [1,2,3,4] ソート済 [1,3] と [2,4] を merge → [1,2,3,4]
vector<int> c = a; c.insert(c.end(), b.begin(), b.end()); // 連結 vector<int> m; merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(m)); // ソート済マージ
順序を保つ重複除去と、ソートして潰す方法。
[1,1,2,3,3] → [1,2,3]
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end()); // unique は隣接重複を後ろへ寄せる
存在判定と添字。配列の contains は O(N)(多用なら Set 化で O(1))。
[5,3,9] 3を含む? → true 9の位置 → 2
bool has = find(a.begin(), a.end(), 3) != a.end();
int idx = find(a.begin(), a.end(), 9) - a.begin(); // 無いと size()
合計はオーバーフローに注意(Long で受ける)。空配列の max/min は例外。
[3,1,2] → sum=6 max=3 min=1
ll s = accumulate(a.begin(), a.end(), 0LL); // 0LL で long long
int mx = *max_element(a.begin(), a.end());
int mn = *min_element(a.begin(), a.end());
条件を満たす個数を数える / 満たす要素だけ取り出す。
[1,2,3,4] → even を抽出 → [2,4] cnt=2
int cnt = count_if(a.begin(), a.end(), [](int x){ return x%2==0; });
vector<int> evens; for (int x : a) if (x%2==0) evens.push_back(x);
各要素に同じ加工をして新しい列を作る。
[1,2,3] → ×2 → [2,4,6]
vector<int> b(a.size()); for (size_t i = 0; i < a.size(); i++) b[i] = a[i] * 2;
破壊的か非破壊か、降順、キー指定(複数キー)を押さえる。
[3,1,2] → 昇順 [1,2,3] / 降順 [3,2,1]
sort(a.begin(), a.end()); // 昇順 sort(a.rbegin(), a.rend()); // 降順 sort(v.begin(), v.end(), [](auto&x, auto&y){ return x.second < y.second; });
反転、部分列の切り出し(半開区間 [l, r))、左 k 回転。
[1,2,3,4] → 反転 [4,3,2,1] / [1,3) = [2,3]
reverse(a.begin(), a.end()); // 破壊的反転 vector<int> sub(a.begin()+1, a.begin()+3); // [1,3) rotate(a.begin(), a.begin()+k, a.end()); // 左 k 回転
「最大値そのもの」でなく「最大の添字」が欲しいとき。
[3,9,1] → maxIdx = 1 (値 9)
int idx = max_element(a.begin(), a.end()) - a.begin();
前計算 O(N)、以後どの区間和も O(1)。pre は長さ N+1、半開区間で引く。
a=[1,2,3] → pre=[0,1,3,6] sum[l,r) = pre[r] - pre[l]
vector<ll> pre(n + 1);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
ll s = pre[r] - pre[l]; // [l, r)
h×w を w×h に。grid[i][j] → t[j][i]。
[[1,2,3],
[4,5,6]] → [[1,4],
[2,5],
[3,6]]vector<vector<int>> t(w, vector<int>(h)); for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) t[j][i] = g[i][j];
Dijkstra・貪欲で頻出。「常に最小(or 最大)を取り出す」袋。
push 3,1,2 → poll → 1,2,3 (最小ヒープ) add/poll は O(log N)
priority_queue<int> mx; // 最大ヒープ (既定) priority_queue<int, vector<int>, greater<>> mn; // 最小ヒープ mx.push(3); int t = mx.top(); mx.pop();
両端から出し入れできる。Queue は BFS、Stack は DFS に使う。
BFS=Queue(先入れ先出し) / DFS=Stack(後入れ先出し) front [ . . . ] back
deque<int> dq;
dq.push_back(1); dq.push_front(0);
int f = dq.front(); dq.pop_front();
// queue<int> / stack<int> も同様
重複を消す / 含まれるかを高速判定。順序つきが要るなら Tree/std::set。
[1,1,2,3] → {1,2,3} (3 in set? → true)set<int> s(a.begin(), a.end()); // 重複排除 + 昇順 if (s.count(3)) { } // unordered_set は平均 O(1)
出現回数の数え上げが定番。無いキーの既定 0 の扱いが言語差。
[a,b,a] → {a:2, b:1}map<int, int> cnt; for (int x : a) cnt[x]++; // 既定 0 から +1 int c = cnt[x]; // 注意: 参照で要素が増える
ソート済み配列で「x 以上が始まる位置」。x の個数 = upper - lower。
sorted=[1,3,5,7] x=5 lower=2 (5以上の先頭) / upper=3 (5より大の先頭)
int lo = lower_bound(a.begin(), a.end(), x) - a.begin(); // x 以上の先頭 int hi = upper_bound(a.begin(), a.end(), x) - a.begin(); // x より大
空白区切りで分解、配列を連結、文字単位の配列化。
"a b c" → split → [a, b, c]
[a, b, c] → join(" ") → "a b c"stringstream ss(s); string w; // split は stringstream while (ss >> w) parts.push_back(w); // join: 自前ループで " " を挟む