既存投稿一覧ページへのリンク
Before
Next
C問題
入力例03
頂点に 1 から 10 の番号がついた 10 個の頂点、10 本の辺からなる単純無向グラフがあります。 各辺は次の通りに2つの頂点を結んでいます。
- 7 と 9 を結ぶ
- 4 と 6 を結ぶ
- 6 と 10 を結ぶ
- 2 と 5 を結ぶ
- 5 と 6 を結ぶ
- 5 と 9 を結ぶ
- 6 と 8 を結ぶ
- 4 と 8 を結ぶ
- 1 と 5 を結ぶ
- 1 と 4 を結ぶ
このグラフを「森」（どの連結成分も閉路を持たない＝全ての成分が木）にするために、少なくとも何本の辺を削除する必要がありますか？
input
10 10
7 9
4 6
6 10
2 5
5 6
5 9
6 8
4 8
1 5
1 4
input_python
input.py
def io_func():
# n と m を入力から取得
n, m = map(int, input().split())
# u, v のペア情報を格納
edges = []
for _ in range(m):
u, v = map(int, input().split())
edges.append((u, v))
# n, m, edges の3つを戻り値とする
return n, m, edges
output
2
D問題
入力例01
テストケース1
問題設定
- 3組のカップル（1, 2, 3）が一列に座っています。
- 現在の並び順：1 2 3 3 1 2 （合計6人の並び）
- 各番号は、そのカップルの人を表します（例えば「1」が2人、「2」が2人、「3」が2人ずつ居ます）。
求める内容
- 1～3のうち異なる番号の組 $(a, b)$（$1 \leq a < b \leq 3$）で、下記条件をすべて満たすものの個数を求めてください。
- 最初、a同士もb同士も隣り合っていない。
- 次の操作を1回以上繰り返すことで、「a同士もb同士もそれぞれ隣同士」になることが可能となる。
- それぞれのa, bの位置(i, j)（1 ≤ i, j ≤ 6）を一つ選び、A_iとA_jを入れ替える（例：1番目と4番目を交換、など）。
テストケース2
問題設定
- 4組のカップル（1, 2, 3, 4）が一列に座っています。
- 現在の並び順：1 1 2 2 3 3 4 4（合計8人の並び）
- それぞれの番号が2回ずつ現れます。
求める内容
- 1～4のうち異なる番号の組 $(a, b)$（$1 \leq a < b \leq 4$）で、下記条件をすべて満たすものの個数を求めてください。
- 最初、a同士もb同士も隣り合っていない。
- どちらのカップルも操作によって隣り合うように席を入れ替えられる（操作内容はテストケース1と同じ）。
テストケース3
問題設定
- 5組のカップル（1, 2, 3, 4, 5）が一列に座っています。
- 現在の並び順：1 2 3 4 5 1 2 3 4 5（合計10人の並び）
- それぞれの番号が2回ずつ現れます。
求める内容
- 1～5のうち異なる番号の組 $(a, b)$（$1 \leq a < b \leq 5$）で、下記条件をすべて満たすものの個数を求めてください。
- 最初、a同士もb同士も隣り合っていない。
- どちらのカップルも操作によって隣り合うように席を入れ替えられる（操作内容は上記同様）。
解法シナリオ
-
カップルごとの隣接状態の判定リストを初期化する
- 各カップル番号 $1$ から $N$ について、同じ番号が隣り合って登場したら、そのカップルは条件対象外とするフラグリストを作成する。
-
全ての隣接ペア $(A_i, A_{i+1})$ を列挙し、それぞれのペアに対して操作判定・記録を行う
- 隣接している二人が同じカップルであれば対象外フラグを立てる。
- 異なるカップルならば、(小さい番号, 大きい番号)のペアを記録する。
- そのペアが既に登場済みならば、再び隣接した場合はスキップする。まだペアごとに対象になれるか ($\mathtt{flag[a]}$, $\mathtt{flag[b]}$) を判定し、両方条件を満たしていればカウントする。
-
カウントした結果を出力する
- 条件を満たすペア数（ans）をそのまま出力する。
input
3
3
1 2 3 3 1 2
4
1 1 2 2 3 3 4 4
5
1 2 3 4 5 1 2 3 4 5
input_python
input.py
def io_func():
# テストケース数を入力
t = int(input())
# 各テストケースの情報を格納するリスト
testcases = []
for _ in range(t):
# 各テストケースのNを入力
n = int(input())
# 配列Aを入力し、整数リストに変換
a = list(map(int, input().split()))
# テストケースごとにタプルで格納
testcases.append((n, a))
# テストケース数tと各テストケースのリストを戻り値として返す
return t, testcases # t: int, testcases: List[(n, a)]
output
1
0
4
E問題
入力例01
長さ 6 の英小文字からなる文字列 S と T が与えられます。
S = afbfda
T = bkckbb
以下の操作を0回以上繰り返して、SをTと一致させることができるか判定してください。
可能な場合は、そのために必要な操作回数の最小値も求めてください。
操作内容
- 英小文字 x , y を好きに選び、S に含まれる すべての x を y に置き換える。
input
6
afbfda
bkckbb
input_python
input.py
def io_func():
n = int(input()) # 1行目から整数Nを取得
s = input().strip() # 2行目から文字列Sを取得し、前後の空白を除去
t = input().strip() # 3行目から文字列Tを取得し、前後の空白を除去
return n, s, t # 取得したN,S,Tを戻り値として返す
output
4
F問題
入力例01
正整数 N=3、K=2 および長さ 3 の整数列 A=(3, 1, 2) が与えられます。
次の式の値を 998244353 で割った余りを求めてください：
$$\sum_{1 \leq l \leq r \leq 3} \left( \sum_{l \leq i \leq r} A_i \right)^2$$
愚直(計算量O(N^3)版)
def interval_sum_square(A):
n = len(A)
total = 0
# 1 <= l <= r <= n
for l in range(1, n + 1):
for r in range(l, n + 1):
s = sum(A[l-1:r])
total += s ** 2
return total
つまり、全ての区間 $(l, r)$（$1 \leq l \leq r \leq 3$）について、その区間の要素和を2乗し、その合計を求めてください。
具体的な計算対象
- （$l=1, r=1$）：区間 = ⇒ 和 = 3 ⇒ 3² = 9
- （$l=1, r=2$）：区間 = ⇒ 和 = 4 ⇒ 4² = 16
- （$l=1, r=3$）：区間 = ⇒ 和 = 6 ⇒ 6² = 36
- （$l=2, r=2$）：区間 = ⇒ 和 = 1 ⇒ 1² = 1
- （$l=2, r=3$）：区間 = ⇒ 和 = 3 ⇒ 3² = 9
- （$l=3, r=3$）：区間 = ⇒ 和 = 2 ⇒ 2² = 4
これらを全て合計した値（9+16+36+1+9+4 = 75）を 998244353 で割った余りが答えとなります。
input
3 2
3 1 2
input_python
input.py
def io_func():
# 1行目：n, k を取得し、それぞれ int型に変換して格納
n, k = map(int, input().split())
# 2行目：A を取得し、各要素を int型に変換してリストに格納
a = [int(x) for x in input().split()]
# n, k, a の3変数をタプルとして返す
return n, k, a
output
75