💻 競技プログラミングの魅力と AtCoder ABC272 の問題解説
突然ですが、競技プログラミング（通称：競プロ）をご存じでしょうか？
競技プログラミングとは、与えられた問題を制限時間内に解くプログラミング競技です。
単なる「テスト」や「作業」ではなく、頭脳ゲーム × コーディング × 論理パズルのような、とても刺激的な世界です。
私自身も AtCoder を中心に参加しており、
理解力・論理力のトレーニングとして最適だと感じています。
AtCoder Beginner Contest（ABC）は、ほぼ毎週土曜21:00〜開催。
初心者から上級者まで楽しめるため、まだ触れたことがない方にもおすすめです◎
今回は、AtCoder Beginner Contest 272（ABC272） の一部問題を、
チップス（解法のコツ）とともに解説していきます。
競プロでは、ちょっとした知識・書き方の差がスピードや正確性に大きく影響します。
今回の解説に必要なチップスは次の 3 つです。
- 二次元配列（行列）の簡単な初期化
- itertools.combinations の使い方（組み合わせ生成）
- 配列を「大きい順」にソートする方法
① 二次元配列の作成
Python では、以下のように 1 行で 2 次元リストを作成できます。
ll = [[0 for _ in range(n)] for _ in range(n)]
これはリスト内包表記と呼ばれる書き方で、競プロでは非常によく使います。
今回は n×n の全要素が 0 の行列を作っています。
② itertools.combinations：組み合わせを簡単に取り出せる
あるリストから「2 個選ぶ組み合わせ」を取り出したい場合に便利です。
import itertools
a = [1, 2, 3]
for v in itertools.combinations(a, 2):
print(v)
# (1, 2)
# (1, 3)
# (2, 3)
使い方は直感的で、順序を無視した全ペアを取得できます。
今回の B 問ではこれが非常に重要な役割を果たします。
③ 配列の「大きい順」ソート
通常の sort() は「小さい順」になります。
大きい順にしたいときは reverse=True をつけます。
a = [1, 2, 3]
a.sort(reverse=True)
print(a)
# [3, 2, 1]これら 3 つを押さえるだけで、今回の問題がスムーズに解けます。
ここからは、ABC272 の以下 3 問を解説していきます。
- A: Integer Sum（整数の合計）
- B: Everyone is Friends（友達判定）
- C: Max Even（最大の偶数を作る）
—
A Integer Sum
問題文
N 個の整数 \(A_1,A_2,…,A_N\) が与えられます。
その合計値を求めてください。
解答例
def LI(): return list(map(int, input().split()))
n = int(input())
a = LI()
print(sum(a))
解法は非常にシンプルで、sum(a) を使うだけ。
ウォーミングアップとして最適な問題です。
—
B Everyone is Friends
問題文
N 人がいて、M 回の舞踏会が行われる。
各舞踏会に参加した人たちの情報が与えられるので、
どの 2 人も少なくとも 1 回は同じ舞踏会に参加しているか判定せよ。
解答例
import itertools
def LI(): return list(map(int, input().split()))
n, m = LI()
# ペアごとの「共通参加回数」を記録する行列
ll = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
temp = LI()
temp.pop(0) # 先頭の k_i は使わない
# 全てのペアについて共通参加を記録
for v in itertools.combinations(temp, 2):
ll[v[0]-1][v[1]-1] += 1
ll[v[1]-1][v[0]-1] += 1
# 1 回も会っていないペアがあれば No
for i in range(n):
for j in range(n):
if i == j:
continue
if ll[i][j] 1:
print("No")
exit()
print("Yes")処理のポイントは以下２点：
- ✔
itertools.combinationsで全ペアを自動生成 - ✔ 一度も共通参加がないペアを見つけたら即終了（
exit()）
この問題はデータ数が大きくなると計算量が重くなるため、
「見つけたらすぐ返す」方針が効率的です。
—
C Max Even
問題文
長さ N の整数列 A が与えられる。
「異なる 2 要素の和」として作れる値の中から、
偶数の最大値を求めよ（存在しない場合は -1）。
解答例
def LI(): return list(map(int, input().split()))
n = int(input())
a = LI()
ki = [] # 奇数
gu = [] # 偶数
# 奇数・偶数に分類
for x in a:
if x % 2 == 0:
gu.append(x)
else:
ki.append(x)
# 大きい順に並べる
ki.sort(reverse=True)
gu.sort(reverse=True)
# 偶数が作れないケース
if len(ki) = 1 and len(gu) = 1:
print(-1)
else:
# 候補は「奇数+奇数」or「偶数+偶数」
candidates = []
if len(ki) >= 2:
candidates.append(ki[0] + ki[1])
if len(gu) >= 2:
candidates.append(gu[0] + gu[1])
print(max(candidates))
全組み合わせを計算すると O(N²) になり、
N=2×10⁵ の制約では間に合いません。
そこで、
- 偶数＋偶数＝偶数
- 奇数＋奇数＝偶数
という性質を使い、偶数と奇数のリストを分けて上位 2 個の和だけを見ることで
高速に最大値を求めています。
ABC272 の C 問題では、
「全探索では間に合わない → 問題の性質を利用して最適化する」
という競プロでは非常に重要な考え方が登場しました。
競技プログラミングは、
論理的に考える力・効率的に実装する力・丁寧に検証する力
が自然と身につく最高のトレーニングです。
これからも問題解説を続けていきますので、
ぜひ一緒に楽しみながら実力を伸ばしていきましょう！