Python splitの使い方まとめ

split

Pythonの文字列は、メソッドsplitを用いることでlistに分割することができます。
まずは実際にコードを見てみましょう。下記のような半角スペース区切りで単語が結合されている文字列を考えます。

1
2
3
>>> fruits = 'orange lemon apple banana grape'
>>> fruits.split()
['orange', 'lemon', 'apple', 'banana', 'grape']

区切り文字(ここでは半角スペース)は連続して複数入っている場合は一つの区切り文字として扱われます。また、文字列の先頭や末尾に入っている区切り文字は無視されます。

1
2
>>> fruits2 = ' orange   lemon apple banana grape '
['orange', 'lemon', 'apple', 'banana', 'grape']

改行コードも区切り文字として分割されます。

1
2
>>> fruits3 = ' orange\nlemon apple\rbanana grape '
['orange', 'lemon', 'apple', 'banana', 'grape']

区切り文字の指定

また、区切り文字を自分で指定することもできます。

1
2
3
4
>>> fruits.split(' ')
['orange', 'lemon', 'apple', 'banana', 'grape']
>>> fruits.split('a')
['or', 'nge lemon ', 'pple b', 'n', 'n', ' gr', 'pe']

ただし、区切り文字の指定を行なった場合は、先述のルール

1
区切り文字(ここでは半角スペース)は連続して複数入っている場合は一つの区切り文字として扱われます。また、文字列の先頭や末尾に入っている区切り文字は無視されます。

は適用されません。すなわち

1
2
3
fruits2 = ' orange   lemon apple banana grape '
fruits2.split(' ')
['', 'orange', '', '', 'lemon', 'apple', 'banana', 'grape', '']

のような挙動となるので中板必要です。

maxsplitの指定

最大で何分割をするか指定することもできます。

1
2
3
4
5
6
7
8
fruits.split(' ',1)
['orange', 'lemon apple banana grape']
```
あまりメリットがあるように思えませんが、取り出したい要素が何番目か決まっている場合は、
無駄な分割をせずに済みます。
```python
fruits.split(' ',1)[0]
'orange'

また、rsplitを用いると、文字列の末尾から分割をすることができるため、
取り出したい要素が後ろの方にある場合は下記のような無駄なく要素を取り出せます

1
2
3
4
>>> fruits.rsplit(' ',1)
['orange lemon apple banana', 'grape']
>>> fruits.rsplit(' ',1)[-1]
'grape'

正規表現を用いたい場合

区切り文字をリストなどで複数指定することはできません。

1
fruits.split(['1','2']) #  エラー。リストを指定することはできない

そう言った場合は正規表現を使うと良いでしょう。

1
2
3
4
>>> import re
>>> fruits4 = 'orange1lemon2banana21grape'
>>> print(re.split('\d+', fruits4))
['orange', 'lemon', 'banana', 'grape']

splitlines

文字列を改行コードで分割したい場合はsplitlinesを利用すると良い。この場合、半角スペースは区切り文字として扱われない。

1
2
3
4
fruits3 = ' orange\nlemon apple\rbanana grape '
lines
fruits3.splitlines()
[' orange', 'lemon apple', 'banana grape ']

Python listの使い方まとめ(全メソッド)

listの基本

リスト(list)はシーケンス型(順番を保持した、要素の集まり)の一つです。

1
2
A = [2, 3, 4]
B = ['apple', 'orange']

メソッド

全メソッドを紹介していきます。

append

計算量 O(1)

要素の追加を行う。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.append('x')
>>> ls
['a', 'b', 'a', 'c', 'x']

extend

計算量 O(k)

(kは追加するlistの大きさ)

listにlistを結合する。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.extend(['x', 'y'])
>>> ls
['a', 'b', 'a', 'c', 'x', 'y']

insert

計算量 O(n)

(nはlistの大きさ)

位置を指定して要素の追加を行う。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.insert(0, 'x')
>>> ls
['x', 'a', 'b', 'a', 'c']

以下のようにするとappendと等価。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.insert(len(ls), 'x')
>>> ls
['a', 'b', 'a', 'c', 'x']

remove

計算量 O(n)

(nはlistの大きさ)

指定した値の要素を削除する。ただし、削除されるのは指定した値を持つ、リストで最初に現れる要素である。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.remove('a')
>>> ls
['b', 'a', 'c']

pop

位置を指定して要素の追加を行う。削除した値を返却する。

1
2
3
4
5
6
>>> ls = ['a', 'b', 'a', 'c']
>>> p = ls.pop(0)
>>> ls
['b', 'a', 'c']
>>> p
'a'

-1を指定することで、末尾から削除することも可能。

1
2
3
4
>>> ls = ['a', 'b', 'a']
>>> ls.pop(-1)
>>> ls
['a', 'b']

clear

listの中身を空にする。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.clear()
>>> ls
[]

index

指定した値を持つ要素の位置を取得する。

1
2
3
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.index('b')
1

ただし指定した値を持つ、リストで最初に現れる要素の位置が返却される。

1
2
3
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.index('a')
0

count

指定した値を持つ要素を数える。

1
2
3
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.count('a')
2

sort

昇順ソートを行う。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.sort()
>>> ls
['a', 'a', 'b', 'c']

降順ソートを行う。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.sort(reverse=True)
>>> ls
['c', 'b', 'a', 'a']

reverse

順序を逆にする。

1
2
3
4
>>> ls = ['a', 'b', 'a', 'c']
>>> ls.reverse()
>>> ls
['c', 'a', 'b', 'a']

copy

ディープコピーを生成する。

1
2
3
4
5
>>> ls = ['a', 'b', 'a', 'c']
>>> ls_c = ls.copy()
>>> ls.clear()
>>> ls_c
['a', 'b', 'a', 'c']

計算量については、下記のリンクを参考にすると良いでしょう。
https://wiki.python.org/moin/TimeComplexity

記事情報

  • 投稿日:2020年2月6日
  • 最終更新日:2020年4月3日

Pythonにおけるリスト(list)と配列(array)の違い

はじめに

リスト(list)と配列(array)を厳密に使い分けていない情報が散見されます。本記事では、両者の違いをまとめようと思います。

listの基本

リスト(list)はシーケンス型(順番を保持した、要素の集まり)の一つです。

1
2
A = [2, 3, 4]
B = ['apple', 'orange']

arrayの基本

標準ライブラリarrayは、実はlistとほとんど同じです。大きな違いは、arrayでは格納するオブジェクトの型が全て同じである必要がある点です。この制約をメリットと感じられない場合はlistを使えば問題ないでしょう。実際、標準ライブラリのarrayはほとんど使われることはありません。

では、listだけ覚えればよいのでしょうか。 いえ、Pythonで配列としてよく利用されるクラスnumpy.ndarrayについても理解をしておくと良いでしょう。

numpy.ndarrayの基本

NumPyPythonの数値計算ライブラリで、標準ライブラリではないものの非常に多くのユーザに利用されています。そんなNumPyndarrayは次のように利用します。

1
2
import numpy as np
C = np.array([2,3,4])

listとnumpy.ndarrayの比較

実行速度

timeitを用いて速度を計測する
まずは、要素数が1000のlistndarrayを準備する。

1
2
ones = [1] * 1000
np_ones = np.array(ones)
  • sum ndarrayの方が高速

    1
    2
    3
    4
    >>> %timeit sum(ones)
    8.06 µs ± 274 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
    >>> %timeit np_ones.sum()
    2.58 µs ± 31 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  • max ndarrayの方が高速

    1
    2
    3
    4
    >>> %timeit max(ones)
    16.3 µs ± 779 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
    >>> %timeit np_ones.max()
    3.11 µs ± 68.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  • for文 listの方が高速

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> %%timeit
    >>> for i in ones:
    >>> pass
    9.3 µs ± 680 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

    >>> %%timeit
    >>> for i in np_ones:
    >>> pass
    45.8 µs ± 2.83 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  • 演算 ndarrayの方が高速

まとめて演算した際の実行速度を考える。listでは以下のようにしても要素ごとの演算は行われずエラーとなる。

1
>>> ones / 2

そのため、リスト内包表記を用いる必要がある。

1
2
3
4
5
6
7
8
>>> %timeit [one+1 for one in ones]
46.7 µs ± 3.91 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit np_ones + 1
1.33 µs ± 61.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> %timeit [a+b for a,b in zip(ones,ones)]
54.5 µs ± 3.89 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit np_ones + np_ones
1.11 µs ± 69.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

相互変換

1
2
ls = arr.tolist()
arr = np.array(ls)

まとめ

  • arrayを使うケースはあまりない
  • listnumpy.ndarrayを使い分ける
    • 数値計算を伴う場合はnumpy.ndarrayが適している場合が多く、そうでなければlistで十分

記事情報

  • 投稿日:2020年2月5日
  • 最終更新日:2020年5月3日

Pythonでlistの要素を「飛ばし」で取得する

飛ばし

Pythonのlistでは、「飛ばし」で要素を取得することができます。
例えば、0~9のリストから偶数のリストを作成できます。

1
2
3
4
5
>>> L = list(range(10))
>>> L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> L[::2]
[0, 2, 4, 6, 8]

コロン区切りで3つ目に与える値によって、何個飛ばしかが決まります。
この値のことを、stepstrieと呼びます。

1
2
>>> L[::3]
[0, 3, 6, 9]

返却されるリストの要素数は元の要素数/stepを切り上げた値となります。

start, stopとの組み合わせ

よく見るstart,stopのスライスと組み合わせることもできます。

  • 2以上6未満

    1
    2
    >>> L[2:6]
    [2, 3, 4, 5]
  • 2以上6未満を3個飛ばし

    1
    2
    >>> L[2:6:3]
    [2, 5]

返却されるリストの要素数は指定された区間の要素数/stepを切り上げた値となります。

1
>>> L[2:6:3]

1
>>> L[2:6][::3]

と等価ということになります。(ただし、stepが正の場合)

逆順

-1を指定することで、リストを逆順に呼べます。

1
2
>>> L[::-1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

start,stopと組み合わせる場合は次のように記述します。

1
2
>>> L[9:1:-1]
[9, 8, 7, 6, 5, 4, 3, 2]

start>stopとする必要があることに注意してください。

応用

では、逆向きに一個飛ばしとなるようなリストを取得したい場合はどうすれば良いでしょうか。

1
2
>>> L[::-1][::2]
[9, 7, 5, 3, 1]

としても良いですが、

1
2
>>> L[::-2]
[9, 7, 5, 3, 1]

このようにも書けます。

最後に

これだとどうなるでしょうか。これが分かれば完璧です。

1
>>> L[7:1:-2]

参考

https://docs.python.org/2.3/whatsnew/section-slices.html

おわりに

MENTAというサービスでプログラミング学習のサポートをしています。競技プログラミングについてもサポートできるので、ご興味がある方はぜひMENTAのDMでご連絡いただければと思います。

記事情報

  • 投稿日:2020年2月5日
  • 最終更新日:2022年1月8日

ARC002A うるう年

問題

https://atcoder.jp/contests/arc002/tasks/arc002_1

方針

ベン図を考える

ポイント

うるう年は「100の倍数ではない4の倍数」「400の倍数」の二つの集合に分けることができる。

コード

1
2
3
4
5
y = int(input())
if ((y%4==0 and y%100!=0) or y%400==0):
print ("YES")
else:
print ("NO")

その他の解法

公式の解説にあった解法。より厳しい条件から順に判定をしていくこともできる。

1
2
3
4
5
6
7
8
9
y = int(input())
if (y%400==0):
print ("YES")
elif (y%100==0):
print ("NO")
elif (y%4==0):
print ("YES")
else:
print ("NO")

機械学習のコードを動かしてみよう(scikit-learn)

概要

昨今、ブームとなっているAI・機械学習の技術は、ハードルが高くて敬遠されている方も多いのではないでしょうか。
たしかに、実際にエンジニアとして開発や研究を行うためには、相応のスキルが必要です。
しかしながら、ソースコードを少し実行するくらいであれば、たった10行のコードで機械学習を体験することができます。

コード

先ずは、今回動かすコードを見てみましょう。このコードを1行ずつ紹介していきます。

1
2
3
4
5
6
7
8
9
10
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neural_network import MLPClassifier
iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)
clf = MLPClassifier()
clf.fit(X_train, y_train)
print (clf.score(X_test, y_test))

1行目

1
from sklearn.datasets import load_iris

scikit-learnはPythonの機械学習ライブラリです。
Deep Learningなどの最先端のアルゴリズムはほとんど実装されていませんですが、
クラシカルで実用的なアルゴリズムやそれらを扱うためのツールが数多く実装されています。

scikit-learnにはサンプルとして、いくつかのデータセットをダウンロードすることができます。その一つがフィッシャーのアヤメと呼ばれるデータで、1行目ではアヤメのデータをダウンロードするための関数load_irisをインポートしています。
データの詳細はこちらを参照いただきたい

2行目

1
from sklearn.model_selection import train_test_split

データ(サンプルの集合)を学習用データとテストデータに分割する関数train_test_splitをインポートしています。データを分割する理由については、やや本題からずれますので記事の最後に補足します。

3行目

1
from sklearn.neural_network import MLPClassifier

クラスMLPClassifierは多層パーセプトロン[1]を用いた分類[2]モデルのクラスです。

[1]多層パーセプトロン・・・ 多層パーセプトロンニューラルネットワーク(Deep Learning)の最もプレーンなネットワーク

[2]分類・・・機械学習のタスクには「回帰」や「分類」といったタスクがあります。分類タスクとは文字通りデータを分類するタスクのことで、例えば、画像に写っている動物が猫か犬かを判定する問題などが考えられます。

4行目

1
iris = load_iris()

先ほど説明したアヤメのデータを変数irisに代入する。

5行目

1
X = iris.data

オブジェクトirisは属性dataを持っており、その中にはアヤメの「がくの長さ」「がくの幅」「花弁の長さ」「花弁の幅」が保持されています。こういった予測に用いるための情報を説明変数特徴量と呼びます。 9行目から説明変数を使って、アヤメの分類を行うことになります。

1
2
>>> X.shape
(150, 4)

データの数(サンプル数)が150で説明変数の種類(次元)が4であることが確認できます。
さて、試しに1つ目のサンプルを確認してみましょう。

1
2
>>> X[0]
array([5.1, 3.5, 1.4, 0.2])

小数で4つの説明変数が格納されていることが確認できます。
ちなみに説明変数の名前はは属性feature_namesで確認できます。

1
2
3
4
5
>>> iris.feature_names
['sepal length (cm)',
'sepal width (cm)',
'petal length (cm)',
'petal width (cm)']

6行目

1
y = iris.target

オブジェクトirisは属性targetを持っており、その中には「アヤメの種類」が保持されています。こういった予測対象となる情報を目的変数ラベルと呼びます。説明変数を使って、目的変数を出来るだけ高い精度で予測することが機械学習の目的の一つです。

1
2
>>> y.shape
(150, )

yについてもデータの数(サンプル数)が150であり、Xの場合とサンプル数が一致していることが確認できます。
さて、試しに1つ目のサンプルを確認してみましょう。

1
2
>>> y[0]
0

今回のtargetは0,1,2のいずれかの数字が保持されています。これらの数字はそれぞれsetona, versicolor, virginicaという種類に対応しています。これは属性target_namesで確認できます。

1
2
>>> list(data.target_names)
['setosa', 'versicolor', 'virginica']

7行目

1
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

train_test_splitを使ってデータを学習用データとテストデータに分割しています。それぞれに目的変数と説明変数があるため、返却されるオブジェクトは4つとなります。test_sizeは分割の比率を決めるパラメータで、ここでは30%をテストデータに、残りの70%を学習用データとしています。データの形状を確認してみましょう。

1
2
3
4
5
6
7
8
>>> X_train.shape
(105, 4)
>>> X_test.shape
(45, 4)
>>> y_train.shape
(105,)
>>> y_test.shape
(45,)

random_stateはデータを分割する際に利用する乱数を、プログラムの実行ごとに固定するための値です。

8行目

1
clf = MLPClassifier()

多層パーセプトロンを用いた分類モデルのクラスであるMLPClassifierからインスタンスclfを作成しています。

9行目

1
clf.fit(X_train, y_train)

clfの学習を行います。引数として、学習用のデータの説明変数X_trainと目的変数y_trainを渡します。

10行目

1
print (clf.score(X_test, y_test))

ここではメソッドscoreで、clfX_testを入力し予測値を計算したのち、答えであるy_testと比較を行い、平均正解率を求めています。もちろん正解率まで求めず、予測だけを行うこともできます。その際にはメソッドpredictを使用します。

1
2
3
4
clf.predict(X_test)
array([0, 2, 1, 1, 1, 2, 1, 1, 2, 0, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1, 2, 0,
0, 2, 1, 0, 2, 2, 2, 0, 0, 2, 0, 2, 1, 0, 1, 2, 2, 0, 2, 0, 2, 1,
2])

MLPClassifierで用いる乱数の関係で、ここに記載した結果と異なる結果が出る可能性があります)

先ほど平均正解率を求めましたが、目視でも答えy_testと比較してみましょう。

1
2
3
4
y_test
array([0, 2, 1, 1, 1, 2, 1, 1, 2, 0, 2, 2, 0, 0, 0, 0, 2, 1, 1, 1, 2, 0,
0, 1, 1, 0, 2, 2, 2, 0, 0, 2, 0, 2, 1, 0, 1, 2, 2, 0, 1, 0, 2, 1,
2])

概ね一致しているのではないでしょうか。

まとめ

解説自体は少々長くなりましたが、コード自体はたった10行と非常に短く、機械学習のハードルは思ったより低く感じられた方もいらっしゃるのではないでしょうか。

より詳しくscikit-learnの勉強をしたい方は

連載「scikit-learnで学ぶ機械学習」を始めます

csvデータの学習方法を知りたい方は

CSVファイルをpandasで読み込み、scikit-learnで学習させる

機械学習の入門〜NumPyによるロジスティック回帰の実装を勉強したい方は

連載「ゼロから始める機械学習」

データ分析と機械学習の関係については以下の記事でまとめています。

データ分析とは何か?機械学習との関係について

補足:train_test_splitでデータを分割する理由

以下の2行の値を比較してみて下さい。おそらく、1行目の方が値が高いのではないでしょうか。

1
2
>>> clf.score(X_train, y_train)
>>> clf.score(X_test y_test)

これは、機械学習モデルに学習してほしいと期待しているアヤメのがく・花弁と種類の関係だけではなく、本質的ではない丸暗記のようなものを学習してしまっているためです。これを過学習と呼びます。私たちが機械学習に期待しているのは学習データの丸暗記ではなく、機械学習モデルにとって未知のデータ(ここではテストデータ)に対する高い正解率での予測です。そのため、機械学習モデルを評価する際は、学習用データに対する正解率ではなくテストデータに対する正解率を優先的に見るべきです。(ただし、前者も使い道はあります。)

人間の試験と一緒

人間が受ける入学試験や資格試験では、本番ではすでに公開されている問題(過去問や模試)と全く同じ問題は基本的には出ませんよね。なぜなら、同じ問題を出してしまうとなると暗記をしてしまえばよい、となるからです。逆にいえば、公開されている問題と同じ問題を出してしまうと、その試験では受験者を適切に評価することができなくなってしまいます。

記事情報

  • 投稿日:2020年2月3日
  • 最終更新日:2020年3月31日

ARC097A K-th Substring

問題

https://atcoder.jp/contests/arc097/tasks/arc097_a

方針

  • 解になりうる全ての文字列をリスト化する
    • 重複してカウントしないように、集合を計算した後、リスト化する
  • 辞書順にソートする
    • Pythonでは文字列のリストに対して、ソートを行うと辞書順にソートが行われる
  • 先頭からK番目の要素を取得する

    ポイント

  • 解の文字数は最大でKであることを利用して計算量を削減する
    • なぜ、最大でKであることが保証できるかというと、例えば、文字数が4文字の文字列hogeよりも、その接頭辞h, ho, hogは辞書順で必ず前にくる。そのためhogeが辞書順で4未満となることはありえない。つまり、辞書順でK番目に小さいものとして、文字数がK文字より大きい文字列を考慮する必要はない。

      コード

      1
      2
      3
      4
      5
      6
      7
      8
      s = input()
      K = int(input())
      st = set() # 集合
      for i in range(K):
      for j in range(len(s)-i):
      st.add(s[j:j+i+1]) # 文字数がi+1となるように文字列をスライスし、集合に追加する
      ls = list(st) # 集合のリスト化
      print (sorted(ls)[K-1]) # ソートしてK番目の要素を取得

ARC046A ゾロ目数

問題

https://atcoder.jp/contests/arc046/tasks/arc046_a

方針

まず、ゾロ目数を列挙してどのような法則に従っているかを考察する

1
2
# N=20までのゾロ目数
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222]

どうやら、ゾロ目数に使われる数字は1~9までの9文字で周期が9であることがわかる

1
2
# ゾロ目数に使われる数字
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

この数列Bをどの様に作るか考えてみる。周期が9であるので9による剰余が関わってきそうだ。

1
2
3
>>> C = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
>>> [ c%9 for c in C ]
[1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2]

これだけではBを作ることはできない。周期は9となっているが、使われている数字が19ではなく08となってしまっている。つまりこの数列に1を足せば良い。

1
2
>>> [ c%9+1 for c in C ]
[2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3]

今度は数列の始めがすれてしまった。これを修正するのは簡単で、9の剰余を取る前に1を引けば良い(数列全体が右にシフトするイメージ)

1
2
>>> [ (c-1)%9+1 for c in C ]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

これで所望の数列Bが完成した。

あとは、数列Aの各項の桁数を表現できれば良い

1
2
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3]

これまた、周期が9であるので9による剰余が関わってきそうだ。

1
2
>>> [ c//9 for c in C ]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

1を足す。

1
2
>>> [ (c)//9+1 for c in C ]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]]

シフトする。

1
2
>>> [ (c-1)//9+1 for c in C ]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3]

これで数列Aの各項の桁数を表現できた。

Pythonは文字列に整数をかけることで、与えられた文字列を繰り返す文字列を生成できる。

1
2
>>> 'A' * 3
'AAA'

つまり、ここまでで数列の各要素に使われている数と桁数を求めることができたので、これらを以下の様に組み合わせることで、所望の数列が得られる

1
2
>>> [ str((c-1)%9+1) * ((c-1)//9+1) for c in C ]
['1', '2', '3', '4', '5', '6', '7', '8', '9', '11', '22', '33', '44', '55', '66', '77', '88', '99', '111', '222']

問題では数列を求める必要はなく、与えられたNに対する要素だけを求めれば良い

コード

1
2
N = int(input())
print (str((N-1) % 9 + 1) * ((N-1) // 9 + 1))

その他の解法

1から数を1ずつ増やしていき、ゾロ目数かどうかを確認していくだけでも解ける。Nが最大で50なので計算時間的にも問題はない。

Pythonでstackとqueueを使う

stack

listを使えば良い。

1
2
3
4
stack = []
stack.append(1) # push O(1)
stack.append(2) # push O(1)
stack.pop() # pop O(1)

listは末尾への挿入・削除はO(1)で処理できるが、任意の位置に対する挿入・削除はO(n)であることに注意が必要。つまり、stackとしてリストが与えられていた場合、順番を逆順にする等してstackの底をリストの先頭にすると良いだろう。

queue

dequeは両端キューとして実装されているが、これをqueueとして使えば良い。

1
2
3
4
5
from collections import deque
queue = deque()
queue.append(1) # enqueue O(1)
queue.append(2) # enqueue O(1)
queue.popleft() # dequeue O(1)

余談

dequeue自体はもちろんstackとしても利用可能である。ちなみにPythonのdequeは双方向連結リストで実装されているため、ランダムアクセス(端以外の要素へのアクセス)はO(n)となってしまう。純粋なstackとしての用途であれば、listとdequeどちらを用いても良いが、それらの特性を理解しておくと良いと思う。

参考

https://docs.python.org/3.7/library/collections.html#collections.deque

defaultdictの紹介

標準の辞書を利用していると、辞書の中に存在しないキーで参照しようとした際に、エラーとなってしまう。そのため、下記のようにチェックをする必要がある。

1
2
3
4
try:
your_process(d[key])
except KeyError:
pass
1
2
if key in d:
your_process(d[key])

そんな時はdefaultdictを使うと便利。

1
2
3
>>> import collections
>>> dd = collections.defaultdict(lambda: "hoge")
>>> dd['A'] = '1'

Bをキーとして参照すると’hoge’が返却される

1
2
3
4
5
>>> dd['A']
'1'

>>> dd['B']
'hoge'