競技プログラミングに役立つテクニック　初級編12問

#競技プログラミングに役立つテクニック　初級編12問

###はじめに
データ構造やアルゴリズムなど、競技プログラミングには必須となる基礎知識がたくさんあります。
しかし、それらについては、すでに分かりやすくまとめられた優秀な記事や書籍が多数あります。

今回の記事では、それらの内容ではなく、初歩的な課題を簡潔なコードで記述するテクニックを書いてみます。
筆者が得意な言語がPythonなので、この記事はすべてPythonで書きます。
シンプルに記述することで、早く書くことができますし、実行時間も短くなることが多いです。
可読性については、読みやすいこともあれば、一見しただけでは理解しにくいものもあるかもしれません。
ある程度の知識がある人にとっては常識的な内容だと思いますが、自分の勉強も兼ねて記事にまとめます。

題材は、競技を行うサイトではありませんが、[Codewars](https://www.codewars.com/dashboard)の8級から6級の問題を使います。
問題を解いた後に他の人が書いた高評価の回答を見ることができ、いろいろな工夫を学べます。

問題数は全部で12問です。比較のためそれぞれの問題につき、2種類のコードを記述します。
★記事の性質上、自分で問題を解くときのネタバレになってしまうので、注意してください。

###8級の問題1

[Even or Odd](https://www.codewars.com/kata/even-or-odd/train/python)
課題: 与えられた整数が偶数(Even)か奇数(Odd)かを答える関数を書きなさい。
入出力例: `even_or_odd(2)` -> `"Even"`

```python:解答例1
def even_or_odd(number):
    if number % 2 == 0:
        return "Even"
    else:
        return "Odd"
```

このような単純な`if/else文`は、以下のように1行で記述する方がシンプルです。

```python:解答例2
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](https://www.codewars.com/kata/return-negative/train/python)
課題: 与えられた数字を負の数字にして答える関数を書きなさい。
入出力例: `make_negative(42)` -> `-42`

```python:解答例1
def make_negative(number):
    return -number if number > 0 else number
```

先ほどの工夫を活かして`if/else文`を1行で記述していますが、もっとシンプルにできます。

```python:解答例2
def make_negative(number):
    return -abs(number)
```

関数をうまく使って、不必要な記述を避けるようにしましょう。

###8級の問題3

[Grasshopper](https://www.codewars.com/kata/grasshopper-summation/train/python)
課題: 1から与えられた正の整数までの整数の総和を答える関数を書きなさい。
入出力例: `summation(8)` -> `36` (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)

```python:解答例1
def summation(num):
    return sum(range(num+1))
```

十分にシンプルな記述ですが、以下の方が`num`の値が大きいときには計算量が少なくて済みます。

```python:解答例2
def summation(num):
    return num * (num+1) // 2
```

ここで、以下の数学的知識を利用しています。

```math
\sum_{k=1}^{n} k = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}
```

###8級の問題4

[Count of positives / sum of negatives](https://www.codewars.com/kata/count-of-positives-slash-sum-of-negatives/train/python)
課題: 与えられたリストのうち正の要素の個数と、負の要素の総和を答える関数を書きなさい。
入出力例: `count_positives_sum_negatives[1, 2, 3, 4, -5, -6, -7]` -> `[4, -18]`
制約: 要素数が0のリストが与えられたときは`[]`を返してください。

```python:解答例1
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行で記述できます。

```python:解答例2
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](https://www.codewars.com/kata/complementary-dna/train/python)
課題: 与えられたDNAの塩基配列に対して、相補的な塩基配列を求める関数を書きなさい。
入出力例: `DNA_strand ("ATTGC")` -> `"TAACG"`

```python:解答例1
def DNA_strand(dna):
    dic = {"A":"T", "T":"A", "G":"C", "C":"G"}
    return "".join([dic[x] for x in dna])
```

`for`文で一つずつ要素を選び、辞書を使って相補的な塩基対を計算しています。
内包表記を使って記述し、得られたリストを`join`でつなげて1つの文字列にしています。
十分にまとまっているように見えますが、もっとシンプルに記述できます。

```python:解答例2
def DNA_strand(dna):
    return dna.translate(str.maketrans("ATCG","TAGC"))
```

文字列に対する`translate()`メソッドを使っています。
`str.maketrans()`関数には、辞書を指定するか、以下のように引数として文字列を指定することができます。
このとき第一引数と第二引数の文字列の長さは一致している必要があります。

- 第一引数: 置換元文字を連結した文字列
- 第二引数: 置換先文字を連結した文字列
- 第三引数: 削除する置換元文字列を連結した文字列

###7級の問題2

[Disemvowel Trolls](https://www.codewars.com/kata/disemvowel-trolls/train/python)
課題: 与えられた文字列から母音だけを除いた文字列を返す関数を書きなさい。
入出力例: `disemvowel("This website is for losers LOL!")` -> `"Ths wbst s fr lsrs LL!"`

```python:解答例1
def disemvowel(string):
    return string.translate(str.maketrans({"a":"", "e":"", "i":"", "o":"", "u":"", "A":"", "E":"", "I":"", "O":"", "U":""}))
```

さっそく`translate()`メソッドを使ってみました。
`str.maketrans()`関数に辞書ではなく文字列で指定することで、シンプルにできないでしょうか。
第一引数に`"aeiouAEIOU"`を指定した場合に、第二引数に空白`""`を指定することはできません。
第一引数と第二引数の文字列の長さは一致している必要があるからです。
このような場合は、前述の第三引数を使います。

```python:解答例2
def disemvowel(string):
    return string.translate(str.maketrans('','','aeiouAEIOU'))
```

###7級の問題3

[You're a square!](https://www.codewars.com/kata/youre-a-square/train/python)
課題: 与えられた整数が平方数かどうかを`True`または`False`で判定する関数を書きなさい。
入出力例: `is_square(-1)` -> `False`

```python:解答例1
def is_square(n):
    if n < 0:
        return False
    elif n ** 0.5 == int(n ** 0.5):
        return True
    else:
        return False
```

負の整数が入力されることもあるので、その場合はまず`False`を返して処理を修了します。
入力された数の平方根が整数になるかどうかで、その数が平方数であることを判定しています。
シンプルに1行にまとめましょう。

```python:解答例2
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](https://www.codewars.com/kata/code-golf-add-2-values-for-each/train/python)
課題: 与えられたリストのそれぞれ隣り合った要素の和からなるリストを作る関数を60字以内で書きなさい。
入出力例: `make_new_list([1, 10, 100, 1])` -> `[11, 110, 101]` (1+10, 10+100, 100+1)

```python:解答例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でまとめると以下のようになります。(オブジェクトの中身を表示させるために*でアンパックしています。)

```python:
> print(*zip(x,x[1:]))
(1, 10) (10, 100) (100, 1)
```

`x`の方が`x[1:]`より要素数が多いですが、余った要素数は無視されます。
それぞれの組に対して`map`関数で和を計算します。

```python:
print(*map(sum,zip(x,x[1:])))
11 110 101
```

あとは`list`でリストに変換すれば答えになります。
今回の問題では、コードの字数が60字以内であることを指定されており、もっと短くしてみましょう。

```python:解答例2
make_new_list=lambda x:[*map(sum,zip(x,x[1:]))]
```

なるべく短く書きたい場合は関数自体を`lambda`式で書けます。
また、最後のリストにまとめる処理は、`map`関数で得られたオブジェクトをアンパックして`[]`で囲めばよいです。

###8級の問題5

[Beginner - Reduce but Grow](https://www.codewars.com/kata/beginner-reduce-but-grow/train/python)
課題: 整数の要素からなるリストが与えられます。すべての要素を掛け合わせた値を返す関数を書いてください。
入出力例: `grow([1, 2, 3, 4])` -> `24` (1 * 2 * 3 * 4)

```python:解答例0
import numpy as np
def grow(arr):
    # 注意！今回の問題ではこれは正解になりません！
    return np.prod(arr)
```

`NumPy`には総積を求める`prod`関数があるので、そのままで良いように思われます。
しかし、実はこの問題では正解になりません！
計算結果が大きくなりすぎると`prod`関数は桁あふれして、計算結果が`0`など変な値になってしまうのです。

```python:解答例1
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](https://www.codewars.com/kata/find-the-odd-int/train/python)
課題: 整数からなるリストが与えられます。リストに奇数個しか含まれない要素がただ一つあります。それを求めなさい。
入出力例: `find_it([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5])` -> `5` (5以外の要素はどれも偶数個含まれている)

```python:解答例1
def find_it(seq):
    for i in seq:
        if seq.count(i) % 2:
            return i
```

リストの各要素に対して出現回数を`count`で数えて、偶数回でなければその要素を返しています。
もっとシンプルに記述できるでしょうか？
直前の8級の問題5で書いた`reduce(mul, arr)`を参考にしてみましょう。

```python:解答例2
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](https://www.codewars.com/kata/persistent-bugger/train/python)
課題: 与えられた自然数に対して各桁の値をすべて掛け合わせて新たな数を作る操作を最低何回行えば一桁になりますか。
入出力例: `persistence(39)` -> `3` (3 * 9 = 27, 2 * 7 = 14, 1 * 4 = 4で最低3回の操作を行うと一桁になる)

```python:解答例1
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`という変数に取得しています。
もう少しシンプルに書けないでしょうか。

```python:解答例2
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](https://www.codewars.com/kata/sum-of-digits-slash-digital-root/train/python)
課題: 与えられた自然数に対して各桁の値を合計して新たな数を作る操作を繰り返し、一桁になったときの値を求めなさい。
入出力例: `digital_root(132189)` -> `6` (1 + 3 + 2 + 1 + 8 + 9 = 24, 2 + 4 = 6)

```python:解答例1
def digital_root(n):
    return n if n < 10 else digital_root(sum(map(int, str(n))))
```

前問とまったく同じ方法で、再帰関数により簡単に記述できました。
今回は各桁の総和なので、`reduce`や`mul`などの関数を`import`する必要はなく、`sum`関数を使えば問題ないです。
これはさらにシンプルにできるでしょうか？

```python:解答例2
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`を返すことで答えになります。

###まとめ

今回の初級編は以上になります。
競技プログラミングを始めたばかりのレベルの人にとって、役に立つ記事になると嬉しいです。

上級者の方は、良くないコードがあればぜひ指摘いただけると助かります。
長文を読んでいただき、ありがとうございました。