突然ですが、競技プログラミングという言葉を聞いたことはありますか？簡単に言うと問題が出題されて時間内に答えを出力するプログラムを提出するといったものです。
筆者も参加者の一人で、自身の理解力を深めるためにも今回からブログを投稿していこうと思います。ちなみに競技プログラミングはほぼ毎週土曜日の21から開催されているので気になる方はぜひ参加してみてください。
今回は競プロを開催しているAtCoderのAtCoder Beginner Contest 272の問題を解いていきます。
今回から始める企画なので今後変わるかもしれないですが、だいたいの流れをご紹介します。
まず最初に問題を解くために最低限知っておくべきチップス（アルゴリズムやライブラリ）のを説明します。
そのあと実際に解答例をご紹介してまとめで締めくくりたいと思います。
今回の問題を解くためには以下の３つのことを知っておいた方が良いです。
- 二次元配列の準備
- itertoolsのcombinationsの使い方
- 配列の大きい順ソート
まず１つ目の二次元配列の準備についてです。
実は以下のように１行で書けちゃいます。
ll = [[0 for i in range(n)] for j in range(n)]リスト内包表記というやり方をしていて、ここでは全て０で初期化されています。
次に２つ目のitertoolsのcombinationsの使い方についてです。
これは組み合わせを計算したい時に役立ちます。
例えば以下のような書き方をすると配列aの中から２つ取り出してこれます。
import itertools
a = [1, 2, 3]
for v in itertools.combinations(a, 2):
print(v)
#(1, 2)
#(1, 3)
#(2, 3)最後に３つ目の配列の大きい順にソートする方法です。
これはa.sort()という風に書くのですがこのままでは小さい順にソートされます。
そこで以下のように書かないといけません。
a = [1, 2, 3]
a.sort(reverse=True)
print(a)
#[3, 2, 1]今回のチップスはこれでおわりです。
さて、実際にこれらを使って問題を解いていきましょう！
問題は全てAtCoder Beginner Contest 272に準拠しています。
今回は以下の３問をご紹介します。
- A Integer Sum
- B Everyone is Friends
- C Max Even
A Integer Sum
問題文
N個の整数\(A_1\),\(A_2\),…\(A_N\)が与えられます。
N個の整数を合計した値を求めてください。
制約
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 ・・・ A_N解答例
def LI(): return list(map(int, input().split()))
n = int(input())
a = LI()
print(sum(a))この問題はN個の要素の合計を出力すればよいので、aというリストに値を格納した後にaをsum関数に渡してあげれば答えを求めることができます。
B Everyone is Friends
問題文
1,2,…Nの番号が付いたN人の人がいます。
M回の舞踏会が行われました。i(目の舞踏会には\(k_i\)人が参加し、参加した人は人\(x_{i,1}\),\(x_{i,2}\),…,\(x_{i,k_i}\)でした。
どの二人も少なくとも1回同じ舞踏会に参加したか判定してください。
制約
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
k1 x1_1 x1_2 … x1_k1
.
.
.
kM xM_1 xM_2 … xM_kM出力
どの二人も少なくとも回同じ舞踏会に参加した場合Yesを、そうでない場合Noを出力せよ。
解答例
import itertools
def LI(): return list(map(int, input().split()))
n,m = LI()
ll = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
temp = LI()
temp.pop(0)
for v in itertools.combinations(temp,2):
ll[v[0]-1][v[1]-1]+=1
ll[v[1]-1][v[0]-1]+=1
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という組み合わせを出力する関数を使っています。
ちなみに計算量を少なくするために１回も同じ舞踏会に参加していないペアがいた場合にNoを出力した後にすぐexit()と書くことでプログラムを終了しています。
C Max Even
問題文
長さの非負整数列\(A\) = \(A_1\),\(A_2\),…,\(A_N\)が与えられます。
\(A\)の異なる 要素の和として表せる値の中に偶数が存在するか判定し、存在する場合その最大値を求めてください。
制約
- の要素は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 … A_N出力
の異なる要素の和として表せる値の中に偶数が存在しない場合、-1を出力せよ。
偶数が存在する場合、その最大値を出力せよ。
解答例
def LI(): return list(map(int, input().split()))
n = int(input())
a = LI()
ki = []
gu = []
for i in a:
if i%2==0:
gu.append(i)
else:
ki.append(i)
ki.sort(reverse=True)
gu.sort(reverse=True)
if len(ki)<=1 and len(gu)<=1:
print(-1)
else:
if len(ki) <= 1:
print(gu[0]+gu[1])
elif len(gu) <= 1:
print(ki[0]+ki[1])
else:
print(max(ki[0]+ki[1],gu[0]+gu[1]))この問題は先ほどのように全ての組み合わせについて計算していると計算量がオーバーしてしまいます。そこで、偶数と奇数のリストに分けて大きい順にソートした後に１つ目と２つ目の和をとることで偶数の最大値を得ることができます。
ちなみに最後の条件文の意味はもし奇数と偶数の数が１つ以下だった場合に足して偶数になるものは無いので－１を出力して、それ以外は奇数もしくは偶数の数が１以下だった場合に反対のリストの２和が答えになり、他は奇数と偶数それぞれの２和をmaxに渡すことで最大値を得ることができます。
今回のC問題は全ての組み合わせを計算する前に問題の本質を考えて効率のいいコードを書く必要がありました。