A - ABC Preparation
$\min\{A_1,A_2,A_3,A_4\}$ を計算すれば OK. こういうときに
int ans = Math.min(Math.min(Math.min(A[0], A[1]), A[2]), A[3]);
みたいに書くのは面倒なので, 複数の値の $\min$ を取る関数を準備しておくと楽.
B - Smartphone Addiction
$\pm 1$ が必要かどうかを考えるのが少し面倒. 迷ったら最終的な残り容量を出力してサンプルと辻褄が合っているかを確認するのが確実そう ?
解法としては, 現時刻とその時に残っている容量を持ちながら for ループを回せばよくて, 途中で残容量が 0 以下になったら No を出力して早期リターンしてしまうのが楽.
int n = sc.nextInt(); int max = n; int m = sc.nextInt(); int t = sc.nextInt(); int cur = 0; for (int i = 0; i < m; i++) { int a = sc.nextInt(); int b = sc.nextInt(); n -= a - cur; if (n <= 0) { pw.println("No"); return; } n += b - a; n = Math.min(n, max); cur = b; } n -= t - cur; if (n <= 0) { pw.println("No"); } else { pw.println("Yes"); }
C - Duodecim Ferra
写像 12 相. 二項係数 $C(L - 1,11)$ が答えとなるが, 途中のオーバフローが怖いので Java であれば BigInteger を使ってしまうのが手っ取り早い.
int l = sc.nextInt(); BigInteger ans = BigInteger.ONE; for (int i = 1; i <= 11; i++) { ans = ans.multiply(BigInteger.valueOf(l - i)); } for (int i = 1; i <= 11; i++) { ans = ans.divide(BigInteger.valueOf(i)); } pw.println(ans);
D - Stamp
白マスが 1 つ以上連続する区間のうち, 最も短い区間の区間長を $k$ とするのが明らかに最適. $k$ が決まれば, 白マスが 1 つ以上連続する区間 (この区間長を $w$ とする) のそれぞれに対して $\left\lceil \dfrac{w}{k} \right\rceil$ 回スタンプを押せばよい. 実装方針として, $0$ 番目のマスと $N+1$ 番目のマスを追加すると楽になる.
int n = sc.nextInt(); int m = sc.nextInt(); int[] x = new int[m + 2]; x[0] = 0; x[m + 1] = n + 1; int[] a = sc.ints(m); System.arraycopy(a, 0, x, 1, m); Arrays.sort(x); int k = n; for (int i = 1; i < m + 2; i++) { if (x[i] - x[i - 1] > 1) { k = Math.min(k, x[i] - x[i - 1] - 1); } } long ans = 0; for (int i = 1; i < m + 2; i++) { int w = x[i] - x[i - 1] - 1; ans += (w + k - 1) / k; } pw.println(ans);
E - Sequence Matching
典型的な DP. ここでは $A_i$, $B_j$ は 1-indexed のまま考える. DP テーブルを
\[
dp[i][j]:=\text{$A_i$, $B_j$ まで見たときのコストの最小値}
\]
で定義すると, 以下の式に従ってテーブルを埋めることが出来る.
\[
dp[i][j]=
\begin{cases}
0 & \text{if $i=0$, $j=0$} \\
dp[i-1][j]+1 & \text{if $i=0$, $j>0$}\\
dp[i][j-1]+1 & \text{if $i>0$, $j=0$}\\
\min \{dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] \} & \text{if $i>0$, $j>0$, $a[i-1]=b[i-1]$} \\
\min \{dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1 \} & \text{if $i>0$, $j>0$, $a[i-1]\neq b[i-1]$}
\end{cases}
\]
答えは $dp[N][M]$.
int n = sc.nextInt(); int m = sc.nextInt(); int[] a = sc.ints(n); int[] b = sc.ints(m); int[][] dp = new int[n + 1][m + 1]; for (int[] r : dp) { Arrays.fill(r, Integer.MAX_VALUE >> 3); } dp[0][0] = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i == 0 && j == 0) continue; if (i == 0) { dp[i][j] = dp[i][j - 1] + 1; } else if (j == 0) { dp[i][j] = dp[i - 1][j] + 1; } else { int v0 = dp[i - 1][j] + 1; int v1 = dp[i][j - 1] + 1; int diff = a[i - 1] == b[j - 1] ? 0 : 1; int v2 = dp[i - 1][j - 1] + diff; dp[i][j] = Math.min(Math.min(v0, v1), v2); } } } pw.println(dp[n][m]);
F - Range Xor Query
ビット毎の排他的論理和は Segment Tree に載せることが出来るので, ライブラリがあれば貼るだけ.
int n = sc.nextInt(); int q = sc.nextInt(); int[] a = sc.ints(n); // Segment Tree のライブラリ (要準備) IntSegmentTree t = new IntSegmentTree( a, // 初期化に用いるデータ (u, v) -> u ^ v, // 二項演算 0 // ここでは単位元を要求している ); while (q --> 0) { int type = sc.nextInt(); if (type == 1) { int i = sc.nextInt() - 1; int v = sc.nextInt(); // t[i] ^= v t.set(i, t.get(i) ^ v); } else { int l = sc.nextInt() - 1; int r = sc.nextInt(); // t[l] ^ t[l+1] ^ ... ^ t[r-1] (半開区間) pw.println(t.prod(l, r)); } }
これだけだと味気ないので補足. Segment Tree に載る条件は半群であることで, $n$ bit 整数全体の集合 $G$ とビット毎の排他的論理和を取る二項演算 $\oplus$ に関して, $(G, \oplus)$ は確かに半群となっている (ビット毎に見れば $\bmod 2$ 上の通常の加算であることを考えれば, 半群の要件である結合則は明らか). また, 結合則に加えて以下の性質が成り立つので, 結局 $(G, \oplus)$ は可換群 (アーベル群) である.
- 単位元の存在: $e=0\in G$
- 逆元の存在: $\forall x\in G$ に対して, $x\oplus x=0$ より, $x$ の逆元は $x$ 自身.
- 可換則: ビット毎に見れば $\bmod 2$ 上の通常の加算であることから明らか.
従って, Segment Tree に限らず, 可換群であることを要求するデータ構造にも載せることができる.
