E - Chords 円周上に $2N$ 点が等間隔に、$1$ 〜 $2N$ の順に番号づけられて並んでいます。$A_i$ と $B_i$ を結ぶ弦で、交わるものはあるかどうか判定してください。 解法では、$A_i < B_i$ になるようにswapした後の説明をします。 解法1 - stackを使う解法…

D - At Most 3 (Contestant ver.) $10^6$ 未満の正の整数を $100$ 進法で $3$ 桁であらわすことができる。つまり、 $100$ 進法で $100^0$ の位、$100^1$ の位、$100^2$ の位がそれぞれ $0$ 〜 $99$ であるおもりを全て持つと個数は $297$ 個であり、$10^6$ …

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で…

B - Christmas Trees $L \le A+kM \le R$ を満たす整数 $k$ の個数を求める問題です。制約が大きいため、全探索では求められません。 これは $L-A \le kM \le R-A$ と言い換えられるので、$L-A$ 以上 $R-A$ 以下の $ M $ の倍数です。$L-A$ と $R-A$ の正負…

A - Christmas Present $B$ と $G$ が異なるので、$B$ が大きい時はBat、$G$ が大きい時はGloveを出力すればいいです。 Python B, G = map(int, input().split()) if B > G: print("Bat") else: print("Glove") C++ #include <bits/stdc++.h> using namespace std; int main</bits/stdc++.h>…

B - 11/11 月と日の組み合わせを全探索します。月と日の組み合わせが正しい条件は、月と日の全ての数字が等しいことなので、setに突っ込みます。 Python N = int(input()) D = list(map(int, input().split())) cnt = 0 for i in range(N): for j in range(1…

A - Not Too Hard やるだけです。forで回してもいいし、Pythonではsumの内部で条件を判定することで簡単に書くことができます。 Python [(iを使った何か) for i in (リスト) if (iの条件)] と書くことでリストから条件を満たす値を抽出できます。 N, X = map…

C - Number Place ナンプレが正しいかどうかの判定です。 縦、横、ブロックごとにsetに突っ込んで全ての長さが $9$ であるかを判定すればいいです。 Python s = [list(map(int, input().split())) for _ in range(9)] a = [set() for _ in range(9)] b = [se…

B - A^A $A^{A} = B \le 10^{18} < 16^{16}$ なので、$A$ として $15$ 以下を全て調べればいいです。 Pythonでは $0^{0}=1$ なので、そのケースを含まないように注意しましょう。 Python b = int(input()) for a in range(1, 19): if a ** a == b: exit(prin…

A - ab 「aとbが隣接する」は「abまたはbaが含まれる」と言い換えられるので、そのまま書きます。 Python N = int(input()) S = input() print("Yes" if "ab" in S or "ba" in S else "No") C++ #include <iostream> using namespace std; int main() { int N; string </iostream>…