AtCoder 入黄しました！
hiro1729さんのAtCoder Beginner Contest 367での成績：85位
パフォーマンス：2400相当
レーティング：1951→2005 (+54) :)
Highestを更新し、初段になりました！
ということで、ABC367で、ついに黄コーダーになることができました！この記事では、入黄するまでにしたことを話します。
精進
ABCの青〜黄diffをメインに精進しました。ARC前はWriter対策をしていました。そのおかげで、ABCではコンテスト中に青下位diff以下をほぼ安定して通すことができ、得意な分野の問題では橙diffまで解けました。画像は直近10回のABCの結果です。
コンテスト中
ABCでは、ほとんどの回で前から順番に解きました。また、早解きが得意なので崖回(Fが水〜青diffで、Gが橙以上diff)ではかなり安定して黄上位〜橙perfを取ることができました。
知識
コンテスト中に通したABC366-Gは、得意分野線形代数の力で解けました。1つでも知っている高度典型があるとABCで勝つ回が増えると思います。
ライブラリ
主にPythonとC++でコンテストに参加していますが、ライブラリをちゃんとつくったことはほとんどありません。これから作る予定です。しかし、考察速度とタイピング速度が早ければ、ライブラリなしでも崖回でも安定して勝てるのでライブラリの必要性を感じることはなかったです。
これからの目標
AJLで、とある黄コーダーさんに爆勝ちされてしまい追いつくのが大変になったので、個人3位を維持して学校4位を奪い返したいです。また、ARC精進をしっかりして安定して勝つために、苦手なwriterをなくすことを目標に頑張ります。また、こどふぉの問題がARCに近いと聞いたので、主に紫〜橙下位diffを埋めることにします。そして、9月以降はJOIの季節です。今年はJOIでは春合宿進出を目標に頑張ります。
ABC364 A〜D 解説
A - Glutton Takahashi
解説
最後の $2$ 連続が甘い料理のときは全ての料理を食べることができますが、それ以外で甘い料理が $2$ 連続して現れる時は全ての料理を食べることができません。したがって、$1 \le i \le N-2$ に対して $S_i=S_{i+1}=$ sweet が成り立つ $i$ が存在するとき No 、そうでないとき Yes を出力すればよいです。
実装
C++
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<string> S(N); for (int i = 0; i < N; i++) { cin >> S[i]; } for (int i = 0; i < N - 2; i++) { if (S[i] == "sweet" && S[i + 1] == "sweet") { cout << "No\n"; return 0; } } cout << "Yes\n"; }
Python
N = int(input()) S = [input() for _ in range(N)] for i in range(N - 2): if S[i] == S[i + 1] == "sweet": print("No") exit() print("Yes")
B - Grid Walk
解説
問題文に書いてある通りに行動します。移動できるかどうかの判定に注意してください。
実装
C++
#include <bits/stdc++.h> using namespace std; int main() { int H, W, Si, Sj; cin >> H >> W >> Si >> Sj; Si--; Sj--; vector<string> C(H); for (int i = 0; i < H; i++) { cin >> C[i]; } string X; cin >> X; for (char dir: X) { if (dir == 'U') { if (Si > 0 && C[Si - 1][Sj] == '.') { Si--; } } if (dir == 'D') { if (Si < H - 1 && C[Si + 1][Sj] == '.') { Si++; } } if (dir == 'L') { if (Sj > 0 && C[Si][Sj - 1] == '.') { Sj--; } } if (dir == 'R') { if (Sj < W - 1 && C[Si][Sj + 1] == '.') { Sj++; } } } cout << Si + 1 << ' ' << Sj + 1 << '\n'; }
Python
H, W = map(int, input().split()) Si, Sj = map(int, input().split()) Si -= 1 Sj -= 1 C = [input() for _ in range(H)] X = input() for d in X: if d == 'U': if Si > 0 and C[Si - 1][Sj] == '.': Si -= 1 if d == 'D': if Si < H - 1 and C[Si + 1][Sj] == '.': Si += 1 if d == 'L': if Sj > 0 and C[Si][Sj - 1] == '.': Sj -= 1 if d == 'R': if Sj < W - 1 and C[Si][Sj + 1] == '.': Sj += 1 print(Si + 1, Sj + 1)
C - Minimum Glutton
解説
$A_i$ が大きい順に料理を並べて食べた時の甘さの合計が $X$ を超えるまでに食べた料理の個数( $X$ を超えないならば $N$ )を $c_A$ 、$B_i$ が大きい順に料理を並べて食べた時のしょっぱさの合計が $Y$ を超えるまでに食べた料理の個数( $Y$ を超えないならば $N$ )を $c_B$ とすると、答えは $min(c_A, c_B)$ です。これを証明します。$(1, 2, \ldots, N)$ を $A_i$ が大きい順に並び替えたものを $C_i$ 、$B_i$ が大きい順に並び替えたものを $D_i$ とします。このとき、$\sum_{i=1}^{c_A} A_{C_i} \le X$ 、$c_A < N$ ならば $\sum_{i=1}^{c_A+1} A_{C_i} > X$ が成り立ちます。また、$\sum _{i=1}^{c_B} A_{D_i} \le Y$ 、$c_B < N$ ならば $\sum_{i=1}^{c_B+1} B_{D_i} > Y$ も成り立ちます。また、$i$ 番目に食べた料理を $P_i (1 \le i \le N)$ とすると $\sum_{i=1}^j A_{P_j} \le \sum_{i=1}^j A_{C_j}$ 、 $\sum_{i=1}^j B_{P_j} \le \sum_{i=1}^{j} B_{C_j}$ が成り立ちます。したがって、この順に料理を並べて食べた時の甘さの合計が $X$ を超えるまでに食べた料理の個数( $X$ を超えないならば $N$ )を $c'_A$ 、この順に料理を並べて食べた時のしょっぱさの合計が $Y$ を超えるまでに食べた料理の個数( $Y$ を超えないならば $N$ )を $c'_B$ とすると、$c'_A \ge c_A$ 、$c'_B \ge c_B$ が成り立つので、$min(c'_A, c'_B) \ge min(c_A, c_B)$ となり、答えが $min(c_A, c_B)$ であることが示されます。
実装
C++
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int N; ll X, Y; cin >> N >> X >> Y; vector<int> A(N), B(N); for (int i = 0; i < N; i++) { cin >> A[i]; } for (int i = 0; i < N; i++) { cin >> B[i]; } sort(A.rbegin(), A.rend()); sort(B.rbegin(), B.rend()); ll sA = 0, sB = 0; int cA = 0, cB = 0; for (int a: A) { sA += a; cA++; if (sA > X) { break; } } for (int b: B) { sB += b; cB++; if (sB > Y) { break; } } cout << min(cA, cB) << '\n'; }
Python
N, X, Y = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort(reverse = True) B.sort(reverse = True) sA = 0 sB = 0 cA = 0 cB = 0 for a in A: sA += a cA += 1 if sA > X: break for b in B: sB += b cB += 1 if sB > Y: break print(min(cA, cB))
D - K-th Nearest
解説
方針1
点 $X$ からの距離を二分探索します。点 $A_1, A_2, \ldots, A_N$ のうち、点 $B_j$ からの距離が $mid$ 以内である点の個数は $A$ を昇順に並び替えたものを二分探索するとよいです。
方針2
長さ $K$ の区間(の左端)を二分探索します。判定は、$B_j - A_{mid}$ と $A_{mid+K-1} - B_j$ の大小を比較すれば良いです。
実装
方針1
C++
#include <bits/stdc++.h> using namespace std; int main() { int N, Q; cin >> N >> Q; vector<int> a(N); for (int i = 0; i < N; i++) cin >> a[i]; sort(a.begin(), a.end()); while (Q--) { int b, k; cin >> b >> k; int le = -1, ri = 200000000; while (le + 1 < ri) { int mi = (le + ri) / 2; if (lower_bound(a.begin(), a.end(), b + mi + 1) - lower_bound(a.begin(), a.end(), b - mi) >= k) { ri = mi; } else { le = mi; } } cout << ri << '\n'; } }
Python
from bisect import bisect_left N, Q = map(int, input().split()) a = list(map(int, input().split())) a.sort() for _ in range(Q): b, k = map(int, input().split()) le, ri = -1, 200000000 while le + 1 < ri: mi = (le + ri) // 2 if bisect_left(a, b + mi + 1) - bisect_left(a, b - mi) >= k: ri = mi else: le = mi print(ri)
方針2
C++
#include <bits/stdc++.h> using namespace std; int main() { int N, Q; cin >> N >> Q; vector<int> a(N); for (int i = 0; i < N; i++) cin >> a[i]; sort(a.begin(), a.end()); while (Q--) { int b, k; cin >> b >> k; int le = -1, ri = N - k + 1; while (le + 1 < ri) { int mi = (le + ri) / 2; if (b - a[mi] >= a[mi + k - 1] - b) { le = mi; } else { ri = mi; } } int ans = 1e9; if (le >= 0) { ans = min(ans, b - a[le]); } if (ri <= N - k) { ans = min(ans, a[ri + k - 1] - b); } cout << ans << '\n'; } }
Python
N, Q = map(int, input().split()) a = list(map(int, input().split())) a.sort() for _ in range(Q): b, k = map(int, input().split()) le, ri = -1, N - k + 1 while le + 1 < ri: mi = (le + ri) // 2 if b - a[mi] >= a[mi + k - 1] - b: le = mi else: ri = mi ans = 10 ** 9 if le >= 0: ans = min(ans, b - a[le]) if ri <= N - k: ans = min(ans, a[ri + k - 1] - b) print(ans)
ABC359 A〜D 解説
A - Count Takahashi
解説
問題文に書いてある通りに、$S_i=$Takahashi である $i$ の個数を数えます。
実装
for文で数える方法
C++
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<string> S(N); for (int i = 0; i < N; i++) { cin >> S[i]; } int ans = 0; for (int i = 0; i < N; i++) { if (S[i] == "Takahashi") { ans++; } } cout << ans << '\n'; }
Python
N = int(input()) ans = 0 for i in range(N): S = input() if S == "Takahashi": ans += 1 print(ans)
count関数を使う方法
C++
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<string> S(N); for (int i = 0; i < N; i++) { cin >> S[i]; } cout << count(S.begin(), S.end(), "Takahashi") << '\n'; }
Python
N = int(input()) S = [input() for _ in range(N)] print(S.count("Takahashi"))
B - Couples
解説
色 $i$ を着た $2$ 人のインデックスを管理する配列を作ります。その $2$ 人のインデックスの差が $2$ なら、その間に人がちょうど一人いるので、その個数を数えればいいです。
実装
C++
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> A(2 * N); for (int i = 0; i < 2 * N; i++) { cin >> A[i]; A[i]--; } vector<int> first(N, -1), second(N, -1); for (int i = 0; i < 2 * N; i++) { if (first[A[i]] == -1) { first[A[i]] = i; } else { second[A[i]] = i; } } int ans = 0; for (int i = 0; i < N; i++) { if (second[i] - first[i] == 2) { ans++; } } cout << ans << '\n'; }
Python
N = int(input()) A = list(map(int, input().split())) first = [-1] * N second = [-1] * N for i in range(2 * N): A[i] -= 1 if first[A[i]] == -1: first[A[i]] = i else: second[A[i]] = i ans = 0 for i in range(N): if second[i] - first[i] == 2: ans += 1 print(ans)
C - Tile Distance 2
問題文では $(S_x+0.5, S_y+0.5)$ から $(T_x+0.5, T_y+0.5)$ までとなっていますが、解説ではタイルを左に $0.5$ 、下に $0.5$ ずらし $(S_x, S_y)$ から $(T_x, T_y)$ までに通る必要があるタイルの境界の最小個数を求める問題とします。
解説
$S_x+S_y$ が偶数ならタイルの左側、奇数ならタイルの右側にあることは簡単に示せます。ここで、簡単のため $(S_x, S_y)$ がタイルの右側にあるときは、$S_x$ を $1$ 減らし、$(S_x, S_y)$ がタイルの左側にあるようにします。 解説で、上下のタイルの境界を横境界、左右のタイルの境界を縦境界と呼ぶことにします。
方針1
$y$ 座標が $S_y$ から $T_y$ に移動するまでには、必ず横境界を $|T_y - S_y|$ 個通る必要があります。このとき、縦境界を通らずに移動できる点のうち最も左にあるものを $(le, T_y)$ 、最も右にあるものを $(ri, T_y)$ とします。このとき、$le=S_x - |T_y - S_y|$ 、$ri=S_x + |T_y - S_y| + 1$ となります。横境界をちょうど $|T_y - S_y|$ 個通ったとき最適で、このとき通る必要がある縦境界の個数は $T_x < le$ のとき $\lceil \frac{le-T_x}2 \rceil$ 個、$le \le T_x \le ri$ のとき $0$ 個、$ri < T_x$ のとき $\lceil \frac{T_x-ri}2 \rceil$ 個になります。
方針2 (と方針1の証明)
上の図のタイルを下の図の丸に変換すると赤い軸が合うようになり、タイルの境界は丸の間の辺で表せます。(これはJOI2014 予選 C - 超都観光と同じ形のグラフです)
このとき、上の図のもとの座標が $(x, y)$ だったとき、(これがタイルの左右どちらにあるかにかかわらず)下の図の新しい座標は $(\lfloor \frac{x + y}2 \rfloor, y)$ になります。また、上のようなグラフで $(0,0)$ から $(x,y)$ まで移動する最短距離は $xy \ge 0$ のとき $\max(|x|,|y|)$ 、$xy<0$ のとき $|x|+|y|$ なので、これらを使うことで方針1の証明ができ、また答えを求めることができます。
実装
方針1
C++
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll Sx, Sy, Tx, Ty; cin >> Sx >> Sy >> Tx >> Ty; if (Sx % 2 != Sy % 2) { Sx--; } ll le = Sx - abs(Sy - Ty), ri = Sx + abs(Sy - Ty) + 1; ll ans = abs(Sy - Ty); if (Tx < le) { ans += (le - Tx + 1) / 2; } if (ri < Tx) { ans += (Tx - ri + 1) / 2; } cout << ans << '\n'; }
Python
Sx, Sy = map(int, input().split()) Tx, Ty = map(int, input().split()) if Sx % 2 != Sy % 2: Sx -= 1 le = Sx - abs(Sy - Ty) ri = Sx + abs(Sy - Ty) + 1 ans = abs(Sy - Ty) if Tx < le: ans += (le - Tx + 1) // 2 if ri < Tx: ans += (Tx - ri + 1) // 2 print(ans)
方針2
C++
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll Sx, Sy, Tx, Ty; cin >> Sx >> Sy >> Tx >> Ty; ll sx = (Sx + Sy) / 2, sy = Sy, tx = (Tx + Ty) / 2, ty = Ty; ll dx = tx - sx, dy = ty - sy; cout << ((dx >= 0 && dy >= 0) || (dx <= 0 && dy <= 0) ? max(abs(dx), abs(dy)) : abs(dx) + abs(dy)) << '\n'; }
Python
Sx, Sy = map(int, input().split()) Tx, Ty = map(int, input().split()) sx, sy = (Sx + Sy) // 2, Sy tx, ty = (Tx + Ty) // 2, Ty dx = tx - sx dy = ty - sy print(max(abs(dx), abs(dy)) if dx * dy >= 0 else abs(dx) + abs(dy))
D - Avoid K Palindrome
解説
この問題は、前 $K$ 文字をインデックスとして回文にならないように遷移するbit DPで解くことができます。具体的には、$dp[i][j]$ ( $j$ は文字列)を、$S$ の前 $i$ 文字の?をAまたはBに置き換えた文字列の $max(1,i-K+1)$ 文字目から $i$ 文字目が $j$ でかつ、条件を満たすものの個数とします。計算量は $O(N 2^{K})$ です。
実装
実装する際には、DPの添え字に文字列を使う代わりに文字列を $2$ 進数で表したものを使っています。
C++
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using mint = atcoder::modint998244353; int main() { int N, K; string S; cin >> N >> K >> S; vector<bool> is_palindrome(1 << K); for (int i = 0; i < (1 << K); i++) { bool ok = true; for (int j = 0; j < K / 2; j++) { if (((i >> j) & 1) != ((i >> (K - 1 - j)) & 1)) { ok = false; } } if (ok) { is_palindrome[i] = true; } } int all_bit = (1 << K) - 1; vector<vector<mint>> dp(N + 1, vector<mint>(1 << K)); dp[0][0] = 1; for (int i = 0; i < N; i++) { if (S[i] != 'B') { for (int j = 0; j < (1 << K); j++) { dp[i + 1][(j << 1) & all_bit] += dp[i][j]; } } if (S[i] != 'A') { for (int j = 0; j < (1 << K); j++) { dp[i + 1][((j << 1) & all_bit) | 1] += dp[i][j]; } } if (i >= K - 1) { for (int j = 0; j < (1 << K); j++) { if (is_palindrome[j]) { dp[i + 1][j] = 0; } } } } mint ans = 0; for (mint i: dp[N]) { ans += i; } cout << ans.val() << '\n'; }
Python
mod = 998244353 N, K = map(int, input().split()) S = input() is_palindrome = [False] * (1 << K) for i in range(1 << K): i_bit = bin(i)[2:].zfill(K) if i_bit == i_bit[::-1]: is_palindrome[i] = True all_bit = (1 << K) - 1 dp = [[0] * (1 << K) for _ in range(N + 1)] dp[0][0] = 1 for i in range(N): if S[i] != 'B': for j in range(1 << K): dp[i + 1][(j << 1) & all_bit] += dp[i][j] if S[i] != 'A': for j in range(1 << K): dp[i + 1][((j << 1) & all_bit) | 1] += dp[i][j] if i >= K - 1: for j in range(1 << K): if is_palindrome[j]: dp[i + 1][j] = 0 else: dp[i + 1][j] %= mod print(sum(dp[N]) % mod)
ABC338-E 解説
E - Chords
円周上に $2N$ 点が等間隔に、$1$ 〜 $2N$ の順に番号づけられて並んでいます。$A_i$ と $B_i$ を結ぶ弦で、交わるものはあるかどうか判定してください。
解法では、$A_i < B_i$ になるようにswapした後の説明をします。
解法1 - stackを使う解法
$0 \le i < 2N$ の順番に以下の操作を繰り返します。
- $A_k = i$ となる $0 \le k < N$ が存在するならstackに $k$ をpushする
- $B_k = i$ となる $0 \le k < N$ が存在するならstackからpopしてその値を $l$ とおく
- $k=l$ なら $A_i$ と $B_i$ の間で弦は交わっていない
- $k \ne l$ なら $A_i$ と $B_i$ で挟まれる部分の内部と外部に跨る弦があるので、交わっている弦がある なので
Yesを出力してexitする
全て終わったら、Noを出力します。$O(N)$ です。
from collections import deque N = int(input()) P = [0] * (2 * N) for i in range(N): A, B = map(int, input().split()) A -= 1 B -= 1 if A > B: A, B = B, A P[A] = i P[B] = N + i st = deque([]) for i in P: if i < N: st.append(i) else: if st.pop() != i - N: print("Yes") exit() print("No")
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> P(2 * N); for (int i = 0; i < N; i++) { int A, B; cin >> A >> B; A--; B--; if (A > B) { swap(A, B); } P[A] = i; P[B] = N + i; } stack<int> s; for (int i: P) { if (i < N) { s.push(i); } else { if (s.top() != i - N) { cout << "Yes\n"; return 0; } s.pop(); } } cout << "No\n"; }
import strutils, sequtils let N = stdin.readLine.parseInt var P = newSeq[int](2 * N) for i in 0..<N: let a_b = stdin.readLine.split().map(parseInt) var A = a_b[0] - 1 B = a_b[1] - 1 if A > B: swap(A, B) P[A] = i P[B] = N + i var st = newSeq[int]() for i in P: if i < N: st.add(i) else: if st.pop() != i - N: echo "Yes" quit() echo "No"
解法2 - Fenwick Treeを使う解法
はじめに $(A_i, B_i)$ の組でsortしておきます。
$A_i < A_j$ のときに弦 $i$ と $j$ が交わっていないかどうかは、$A_i<A_j<B_i<B_j$ かどうかで判定できます。$i$ に対してこれを満たす個数は、$A_j<A_i$ を満たす $j$ が存在しなければ $A_i<A_j<B_i$ を満たす $j$ の個数から $A_i<B_j<B_i$ を満たす $j$ の個数を引くことで求めることができます。これは、Fenwick Treeで $A_i, B_i$ の区間和を効率的に求めたり各操作の終わりに $A_i, B_i$ で $1$ を引いたりすることができるので $O(N \log(N))$ です。
from atcoder.fenwicktree import FenwickTree N = int(input()) P = [[0, 0] for _ in range(N)] fwA = FenwickTree(2 * N) fwB = FenwickTree(2 * N) for i in range(N): P[i] = list(map(int, input().split())) P[i][0] -= 1 P[i][1] -= 1 if P[i][0] > P[i][1]: P[i][0], P[i][1] = P[i][1], P[i][0] fwA.add(P[i][0], 1) fwB.add(P[i][1], 1) P.sort() for A, B in P: if fwB.sum(A + 1, B) < fwA.sum(A + 1, B): print("Yes") exit() fwA.add(A, -1) fwB.add(B, -1) print("No")
#include <bits/stdc++.h> #include <atcoder/fenwicktree> using namespace std; using namespace atcoder; int main() { int N; cin >> N; vector<pair<int, int>> P(N); fenwick_tree<int> fwA(2 * N), fwB(2 * N); for (int i = 0; i < N; i++) { cin >> P[i].first >> P[i].second; P[i].first--; P[i].second--; if (P[i].first > P[i].second) { swap(P[i].first, P[i].second); } fwA.add(P[i].first, 1); fwB.add(P[i].second, 1); } for (auto [A, B]: P) { if (fwB.sum(A + 1, B) < fwA.sum(A + 1, B)) { cout << "Yes\n"; return 0; } fwA.add(A, -1); fwB.add(B, -1); } cout << "No\n"; }
import strutils, sequtils, algorithm type BIT = object n: int a: seq[int] proc initBIT(n: int): BIT = return BIT(n: n, a: newSeq[int](n)) proc add(bit: var BIT, p: int, x: int) = var t = p + 1 while t <= bit.n: bit.a[t - 1] += x t += t and -t proc sum0(bit: var BIT, r: int): int = var s = 0 x = r while x > 0: s += bit.a[x - 1] x -= x and -x return s proc sum(bit: var BIT, l, r: int): int = return bit.sum0(r) - bit.sum0(l) let N = stdin.readLine.parseInt var P = newSeq[tuple[f: int, s: int]](N) fwA = initBIT(2 * N) fwB = initBIT(2 * N) for i in 0..<N: let a_b = stdin.readLine.split().map(parseInt) P[i].f = a_b[0] - 1 P[i].s = a_b[1] - 1 if P[i].f > P[i].s: swap(P[i].f, P[i].s) fwA.add(P[i].f, 1) fwB.add(P[i].s, 1) sort(P) for (A, B) in P: if fwB.sum(A + 1, B) < fwA.sum(A + 1, B): echo "Yes" quit() fwA.add(A, -1) fwB.add(B, -1) echo "No"
ABC251-D 解説
D - At Most 3 (Contestant ver.)
$10^6$ 未満の正の整数を $100$ 進法で $3$ 桁であらわすことができる。つまり、 $100$ 進法で $100^0$ の位、$100^1$ の位、$100^2$ の位がそれぞれ $0$ 〜 $99$ であるおもりを全て持つと個数は $297$ 個であり、$10^6$ 未満の正の整数を全て良い整数となります。これに $10^6$ のおもりを追加すると個数が $298$ 個かつ $10^6$ 以下の全ての整数が良い整数となるため、条件を満たします。
A = list(range(1, 100)) + list(range(100, 10000, 100)) + list(range(10000, 1010000, 10000)) print(len(A)) print(*A)
#include <bits/stdc++.h> using namespace std; int main() { vector<int> A; for (int i = 1; i < 100; i++) { A.push_back(i); A.push_back(i * 100); A.push_back(i * 10000); } A.push_back(1000000); cout << A.size() << '\n'; for (int i = 0; i < A.size(); i++) { cout << A[i] << ' '; } }
ABC271-E 解説
E - Subsequence Path
DPできます。
長さ$N$のDP配列(これは頂点 $1$ からの最短距離を表します)を $dp[1]=0,dp[i]=inf(i > 1)$ で初期化します。そして、各 $E_i$ に対して、$chmin(dp[A_{E_i}], dp[B_{E_i}] + C_{E_i})$ と遷移していきます。これにより、最短経路が更新されていきます。
inf = 1 << 60 N, M, K = map(int, input().split()) A = [0] * M B = [0] * M C = [0] * M for i in range(M): A[i], B[i], C[i] = map(int, input().split()) A[i] -= 1 B[i] -= 1 dp = [inf] * N dp[0] = 0 for E in list(map(int, input().split())): E -= 1 dp[B[E]] = min(dp[B[E]], dp[A[E]] + C[E]) print(dp[N - 1] if dp[N - 1] < inf else -1)
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1LL<<60; int main() { int N, M, K, E; cin >> N >> M >> K; vector<int> A(M), B(M), C(M); for (int i = 0; i < M; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; } vector<ll> dp(N, inf); dp[0] = 0; while (K--) { cin >> E; E--; dp[B[E]] = min(dp[B[E]], dp[A[E]] + C[E]); } ll ans = dp[N - 1]; cout << (ans < inf ? ans : -1) << '\n'; }
ABC078-D 解説
D - ABS
$N=1$ のときは $X$ さんが $1$ 枚取るしかないため答えは $|a_1 - W|$ です。
$2 \le N$ のときは、$X$ さんが最初の操作で全てのカードを取るとスコア $|a_N - W|$ を達成できます。また、最初の操作で $N-1$ 枚のカードを取る、つまり $1$ 枚だけ残すとスコア $|a_{N-1} - a_N|$ を達成できます。$X$ さんが $2$ 枚以上残したとき、$Y$ さんが残り $1$ 枚になるまでカードを取るとスコアは $|a_{N-1} - a_N|$ となります。よって、$X$ さんがカードを $2$ 枚以上残した時、$Y$ さんがスコアを最小化するので、スコアは $|a_{N-1} - a_N|$ 以下になります。$X$ さんはスコアを最大化するので、$2$ 枚以上残す意味はなくなります。よって、答えは $max(|a_N - W|, |a_{N-1} - a_N|)$ です。
N, Z, W = map(int, input().split()) a = list(map(int, input().split())) if N == 1: print(abs(W - a[0])) else: print(max(abs(a[N - 1] - W), abs(a[N - 2] - a[N - 1])))
#include <bits/stdc++.h> using namespace std; int main() { int N, Z, W; cin >> N >> Z >> W; vector<int> a(N); for (int i = 0; i < N; i++) { cin >> a[i]; } if (N == 1) { cout << abs(W - a[0]) << '\n'; } else { cout << max(abs(a[N - 1] - W), abs(a[N - 2] - a[N - 1])) << '\n'; } }
