競技プログラミングに役立つテクニック 初級編12問
はじめに
データ構造やアルゴリズムなど、競技プログラミングには必須となる基礎知識がたくさんあります。
しかし、それらについては、すでに分かりやすくまとめられた優秀な記事や書籍が多数あります。
今回の記事では、それらの内容ではなく、初歩的な課題を簡潔なコードで記述するテクニックを書いてみます。
筆者が得意な言語がPythonなので、この記事はすべてPythonで書きます。
シンプルに記述することで、早く書くことができますし、実行時間も短くなることが多いです。
可読性については、読みやすいこともあれば、一見しただけでは理解しにくいものもあるかもしれません。
ある程度の知識がある人にとっては常識的な内容だと思いますが、自分の勉強も兼ねて記事にまとめます。
題材は、競技を行うサイトではありませんが、Codewarsの8級から6級の問題を使います。
問題を解いた後に他の人が書いた高評価の回答を見ることができ、いろいろな工夫を学べます。
問題数は全部で12問です。比較のためそれぞれの問題につき、2種類のコードを記述します。
★記事の性質上、自分で問題を解くときのネタバレになってしまうので、注意してください。
8級の問題1
Even or Odd
課題: 与えられた整数が偶数(Even)か奇数(Odd)かを答える関数を書きなさい。
入出力例: even_or_odd(2) -> "Even"
def even_or_odd(number):
if number % 2 == 0:
return "Even"
else:
return "Odd"
このような単純なif/else文は、以下のように1行で記述する方がシンプルです。
def even_or_odd(number):
return 'Odd' if number % 2 else 'Even'
公式ドキュメントにあるように、if/while文の真偽判定において以下のようなオブジェクトは偽として判定されます。
-
None,False - 値が
0に等しい数値 - 文字列、リスト、辞書などの要素数(
len)が0
その他のオブジェクトは基本的に真として判定されます。
- 値が
0以外の数値 - 文字列、リスト、辞書などの要素数(
len)が1以上
8級の問題2
Return Negative
課題: 与えられた数字を負の数字にして答える関数を書きなさい。
入出力例: make_negative(42) -> -42
def make_negative(number):
return -number if number > 0 else number
先ほどの工夫を活かしてif/else文を1行で記述していますが、もっとシンプルにできます。
def make_negative(number):
return -abs(number)
関数をうまく使って、不必要な記述を避けるようにしましょう。
8級の問題3
Grasshopper
課題: 1から与えられた正の整数までの整数の総和を答える関数を書きなさい。
入出力例: summation(8) -> 36 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)
def summation(num):
return sum(range(num+1))
十分にシンプルな記述ですが、以下の方がnumの値が大きいときには計算量が少なくて済みます。
def summation(num):
return num * (num+1) // 2
ここで、以下の数学的知識を利用しています。
\sum_{k=1}^{n} k = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}
8級の問題4
Count of positives / sum of negatives
課題: 与えられたリストのうち正の要素の個数と、負の要素の総和を答える関数を書きなさい。
入出力例: count_positives_sum_negatives[1, 2, 3, 4, -5, -6, -7] -> [4, -18]
制約: 要素数が0のリストが与えられたときは[]を返してください。
def count_positives_sum_negatives(arr):
if arr == []:
return []
pos = 0
neg = 0
for i in arr:
if i > 0:
pos += 1
else:
neg += i
return [pos, neg]
きれいにまとまっているように見えますが、これも1行で記述できます。
def count_positives_sum_negatives(arr):
return [sum(x > 0 for x in arr), sum(x for x in arr if x < 0)] if arr else []
return A if X else Bの書式になっています。arrが空のときはif文は偽となり[]を返します。
解答例1のposとnegをそれぞれ以下のように内包表記で計算し、リストにまとめて返しています。
-
pos:arrの要素が0より大きいかをそれぞれTrue(1)とFalse(0)で判定した総和を求めています。 -
neg:arrの要素が0より小さいものをそれぞれ集めた総和を求めています。
内包表記の総和をsumで求める書き方では、posやnegの初期値を0にする処理が不要になります。
7級の問題1
Complementary DNA
課題: 与えられたDNAの塩基配列に対して、相補的な塩基配列を求める関数を書きなさい。
入出力例: DNA_strand ("ATTGC") -> "TAACG"
def DNA_strand(dna):
dic = {"A":"T", "T":"A", "G":"C", "C":"G"}
return "".join([dic[x] for x in dna])
for文で一つずつ要素を選び、辞書を使って相補的な塩基対を計算しています。
内包表記を使って記述し、得られたリストをjoinでつなげて1つの文字列にしています。
十分にまとまっているように見えますが、もっとシンプルに記述できます。
def DNA_strand(dna):
return dna.translate(str.maketrans("ATCG","TAGC"))
文字列に対するtranslate()メソッドを使っています。
str.maketrans()関数には、辞書を指定するか、以下のように引数として文字列を指定することができます。
このとき第一引数と第二引数の文字列の長さは一致している必要があります。
- 第一引数: 置換元文字を連結した文字列
- 第二引数: 置換先文字を連結した文字列
- 第三引数: 削除する置換元文字列を連結した文字列
7級の問題2
Disemvowel Trolls
課題: 与えられた文字列から母音だけを除いた文字列を返す関数を書きなさい。
入出力例: disemvowel("This website is for losers LOL!") -> "Ths wbst s fr lsrs LL!"
def disemvowel(string):
return string.translate(str.maketrans({"a":"", "e":"", "i":"", "o":"", "u":"", "A":"", "E":"", "I":"", "O":"", "U":""}))
さっそくtranslate()メソッドを使ってみました。
str.maketrans()関数に辞書ではなく文字列で指定することで、シンプルにできないでしょうか。
第一引数に"aeiouAEIOU"を指定した場合に、第二引数に空白""を指定することはできません。
第一引数と第二引数の文字列の長さは一致している必要があるからです。
このような場合は、前述の第三引数を使います。
def disemvowel(string):
return string.translate(str.maketrans('','','aeiouAEIOU'))
7級の問題3
You're a square!
課題: 与えられた整数が平方数かどうかをTrueまたはFalseで判定する関数を書きなさい。
入出力例: is_square(-1) -> False
def is_square(n):
if n < 0:
return False
elif n ** 0.5 == int(n ** 0.5):
return True
else:
return False
負の整数が入力されることもあるので、その場合はまずFalseを返して処理を修了します。
入力された数の平方根が整数になるかどうかで、その数が平方数であることを判定しています。
シンプルに1行にまとめましょう。
def is_square(n):
return n >= 0 and n ** 0.5 % 1 == 0
if A and Bの条件式はAがFalseであればBの判定を行わずにFalseを返します。
条件式Bの真偽値がTrueならTrueを返す、という処理はif B return True else return Falseは冗長です。
Bの真偽値をそのまま返せばよいのでreturn Bで良いです。
7級の問題4
Add 2 values for each
課題: 与えられたリストのそれぞれ隣り合った要素の和からなるリストを作る関数を60字以内で書きなさい。
入出力例: make_new_list([1, 10, 100, 1]) -> [11, 110, 101] (1+10, 10+100, 100+1)
def make_new_list(x):
return list(map(sum,zip(x,x[1:])))
与えられたリストと、1つ要素の順番がずれたリストを作ります。
その二つのリストをzipでまとめて、得られた組に対してmap関数でそれぞれのsumを計算しています。
最後にリストに変換して返しています。
挙動を分かりやすくするために例で説明します。
xが[1, 10, 100, 1]のときx[1:]は[10, 100, 1]です。
これをzipでまとめると以下のようになります。(オブジェクトの中身を表示させるために*でアンパックしています。)
> print(*zip(x,x[1:]))
(1, 10) (10, 100) (100, 1)
xの方がx[1:]より要素数が多いですが、余った要素数は無視されます。
それぞれの組に対してmap関数で和を計算します。
print(*map(sum,zip(x,x[1:])))
11 110 101
あとはlistでリストに変換すれば答えになります。
今回の問題では、コードの字数が60字以内であることを指定されており、もっと短くしてみましょう。
make_new_list=lambda x:[*map(sum,zip(x,x[1:]))]
なるべく短く書きたい場合は関数自体をlambda式で書けます。
また、最後のリストにまとめる処理は、map関数で得られたオブジェクトをアンパックして[]で囲めばよいです。
8級の問題5
Beginner - Reduce but Grow
課題: 整数の要素からなるリストが与えられます。すべての要素を掛け合わせた値を返す関数を書いてください。
入出力例: grow([1, 2, 3, 4]) -> 24 (1 * 2 * 3 * 4)
import numpy as np
def grow(arr):
# 注意！今回の問題ではこれは正解になりません！
return np.prod(arr)
NumPyには総積を求めるprod関数があるので、そのままで良いように思われます。
しかし、実はこの問題では正解になりません！
計算結果が大きくなりすぎるとprod関数は桁あふれして、計算結果が0など変な値になってしまうのです。
from operator import mul
from functools import reduce
def grow(arr):
return reduce(mul, arr)
問題文のタイトルにも書いてあるreduce関数を使います。
書式はreduce(function, iterable)です。
指定されたiterableの要素に対して左から右に累積的に関数を適用し、最終的な計算結果を返します。
関数として乗算を指定したいので、operatorモジュールからmulをimportしています。
6級の問題1
Find the odd int
課題: 整数からなるリストが与えられます。リストに奇数個しか含まれない要素がただ一つあります。それを求めなさい。
入出力例: find_it([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5]) -> 5 (5以外の要素はどれも偶数個含まれている)
def find_it(seq):
for i in seq:
if seq.count(i) % 2:
return i
リストの各要素に対して出現回数をcountで数えて、偶数回でなければその要素を返しています。
もっとシンプルに記述できるでしょうか？
直前の8級の問題5で書いたreduce(mul, arr)を参考にしてみましょう。
from operator import xor
from functools import reduce
def find_it(seq):
return reduce(xor, seq)
Pythonではaとbのビット単位排他的論理和をa ^ bとして計算することができます。
以下の性質を持ちます。
-
a ^ bはb ^ aと等しい -
(a ^ b) ^ cはa ^ (b ^ c)と等しい -
a ^ b ^ bはaと等しい
与えられたリストの要素に対して左から右に累積的にビット単位排他的論理和を計算していくと、どうなるでしょう。
偶数回だけ含まれる要素は0になって消えてしまい、奇数回だけ含まれる要素の値が残ります。
関数としてビット単位排他的論理和を使いたいので、operatorモジュールのxorをimportしています。
6級の問題2
Persistent Bugger
課題: 与えられた自然数に対して各桁の値をすべて掛け合わせて新たな数を作る操作を最低何回行えば一桁になりますか。
入出力例: persistence(39) -> 3 (3 * 9 = 27, 2 * 7 = 14, 1 * 4 = 4で最低3回の操作を行うと一桁になる)
from operator import mul
from functools import reduce
def persistence(n):
def rec(lst, cnt):
if len(lst) == 1:
return cnt
return rec(list(map(int, str(reduce(mul, lst)))), cnt + 1)
return rec(list(map(int, str(n))), 0)
各桁を掛け合わせる処理は8級の問題5のままです。
リストにして要素が1になるまで再帰関数で操作を繰り返し、必要な操作の回数をcntという変数に取得しています。
もう少しシンプルに書けないでしょうか。
from operator import mul
from functools import reduce
def persistence(n):
return 0 if n < 10 else persistence(reduce(mul, map(int, str(n)))) + 1
必要な操作の回数を求める処理を、cntという変数を使わずに1行ですっきりと書くことができました。
6級の問題3
Sum of Digits / Digital Root
課題: 与えられた自然数に対して各桁の値を合計して新たな数を作る操作を繰り返し、一桁になったときの値を求めなさい。
入出力例: digital_root(132189) -> 6 (1 + 3 + 2 + 1 + 8 + 9 = 24, 2 + 4 = 6)
def digital_root(n):
return n if n < 10 else digital_root(sum(map(int, str(n))))
前問とまったく同じ方法で、再帰関数により簡単に記述できました。
今回は各桁の総和なので、reduceやmulなどの関数をimportする必要はなく、sum関数を使えば問題ないです。
これはさらにシンプルにできるでしょうか？
def digital_root(n):
return n % 9 or n and 9
数学的に考えてみると、この操作を行ったときに9で割った余りは変化しません。
nを9で割った余りが1～8の値になるなら、この操作を繰り返して1桁になったときの値はその値です。
9で割った余りが0になるとき、nが0なら0を返し、nが0でなければ9を返すことで答えになります。
まとめ
今回の初級編は以上になります。
競技プログラミングを始めたばかりのレベルの人にとって、役に立つ記事になると嬉しいです。
上級者の方は、良くないコードがあればぜひ指摘いただけると助かります。
長文を読んでいただき、ありがとうございました。