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})$ と遷移していきます。これにより、…

D - ABS $N=1$ のときは $X$ さんが $1$ 枚取るしかないため答えは $|a_1 - W|$ です。 $2 \le N$ のときは、$X$ さんが最初の操作で全てのカードを取るとスコア $|a_N - W|$ を達成できます。また、最初の操作で $N-1$ 枚のカードを取る、つまり $1$ 枚だけ…

A - Capitalized? 問題文の通りに判定します。大文字かどうか、小文字かどうかはそれぞれisupper、islowerなどで判定できます。 S = input() print("Yes" if S[0].isupper() and all(i.islower() for i in S[1:]) else "No") #include <bits/stdc++.h> using namespace std;</bits/stdc++.h>…

C - Lining Up 2 解法1 人 $i$ に対してその後ろにいる人 $B_i$ を求める方法です。$B$ を求める時に $A_i=-1$ となる $i$ に対しては列の先頭なのでそれを持つ必要もあります。 N = int(input()) A = list(map(int, input().split())) B = [-1] * N now = 0…

B - Extended ABC 解法1 隣接する部分だけ見る方法 $S$ の隣接する2文字を見ます。これがAA,AB,AC,BB,BC,CCのいずれかならば$S$は拡張ABC文字列です。逆に言うと、BA,CA,CBのいずれかが含まれていると$S$は拡張ABC文字列ではありません。 S = input() for i …

A - Scoreboard 2チームのN試合分の野球の点数が与えられて、合計得点が高いチーム、または引き分けかを判定する問題です。N回ループを回して、合計得点を求め、あとはifで比較をするだけです。 N = int(input()) sx = 0 sy = 0 for _ in range(N): X, Y = m…

E - Traveler 各色ごとに回収する順番を考えます。色 $i$ に対して、最も座標が小さいものを $Min_i$ 、最も座標が大きいものを $Max_i$ とすると、簡単に言えば $Max_i$ までまっすぐ行ってから $Min_i$ に行く、または $Min_i$ までまっすぐ行ってから $Ma…

A - Addition 全ての和が偶数なら、奇数は偶数個あるので、奇数を2つずつ組にすると全て偶数になり、これは明らかにすべて合成できます。 そうでないなら、奇数は奇数個あるので、奇数をどのように合成しても必ず奇数が1つだけ残り、残りは全て偶数になるの…

A - JOI 紋章 (JOI Emblem) まず最初に、全体での答えを求めておき、次に1箇所だけ変えた時に答えがどれだけ変わるかを計算すると解けます。計算量は $O(MN)$ です。 #include <bits/stdc++.h> using namespace std; int main() { int M, N; cin >> M >> N; vector<string> S(M); fo</string></bits/stdc++.h>…

E - Simple String Queries Fenwick Treeを使います。Point AddとRange Sumを高速にできます。 Fenwick Treeを $26$ 本持つと $1$ 文字を変更したり、各文字について、区間にその文字が現れる個数を高速に求めることができたりします。 type1のクエリについ…

D - Cutting Woods データ構造ゲーです。要素が小さい順に並んでいて、データの挿入と探索が高速にできるデータ構造としては、PythonではSortedList、C++ではsetなどがあります。 from sortedcontainers import SortedList L, Q = map(int, input().split())…

D - Flipping and Bonus DPをします。$dp[$(0-indexedで)$i$回目のコイントスで$][j$回連続で表が出ているとき$]$のこれまでもらったお金の最大値 というDPができます。遷移は、$i$連続の連続ボーナスを$Bonus[i]$(なければ$0$)とすると、 $dp[i][0]=max(dp[…

B - Find snuke $H \times W$ のグリッドからsnukeを探す問題です。 解法1 向きに対して全部書く方法です。 H, W = map(int, input().split()) S = [input() for _ in range(H)] for i in range(H): for j in range(W - 4): if S[i][j] == 's' and S[i][j + …

E - Small d and k 各頂点の次数は $3$ 以下、そして各クエリで $k_i$ は $3$ 以下という制約があります。すると、各クエリで見る必要がある頂点は $40$ 頂点に抑えることができるので、BFSをすることで解けます。ただし、訪問の判定に、毎回全ての頂点に対…

B - 増減管理 forの中にif文を書くだけです。 N = int(input()) A = [int(input()) for _ in range(N)] for i in range(N - 1): if A[i] == A[i + 1]: print("stay") elif A[i] < A[i + 1]: print("up", A[i + 1] - A[i]) else: print("down", A[i] - A[i + …

A - 2倍チェック 3桁の整数が与えられて2倍する問題ですが、入力に英小文字が紛れ込むことがあるので、その場合はerrorを出力します。1文字ずつ見ていって、英小文字が出たかどうかを管理すれば解くことができます。 文字列を数値に変換するのには、Pythonで…