PythonでABCのCくらいまでをしばき倒す part1

#注意
この記事は[AtCoder](https://atcoder.jp/?lang=ja)及びAtCoder Beginner Contestのための記事です。
AtCoderって何？って方は[こちらへ](https://qiita.com/drken/items/fd4e5e3630d0f5859067)
**初めての記事なのでどうか温かい目でよろしくお願いします。**
**多分正しくない記述がいっぱいです。**
**小技紹介なので厳密な説明をしません、説明がめんどくさい部分は省きます。**
**ミスってたらごめんなさい。**
ターゲットとしてはB問題やC問題で苦戦しがち、時間がかかりがちな人あたりです。
~~正直あまり教育によろしい記事ではないと思います~~


#はじめに
競プロを始めて丁度1年くらいの緑Coder、くろま(Chroma7p)です。後輩に競プロ文化を広めるべく精進しております。
後輩たちの健闘を見ていると、ライブラリや言語の機能を使いこなしきれずC問題くらいで力尽きるパターンをよく見るので、そういった要素をある程度あらかじめ知っておくことで、灰～茶Diff前半くらいを反射でしばいてD問題以降に挑戦できるようになってほしいというのが狙いです。あとは初心者に教えたいことの備忘録的な物だったり初めての記事書く練習だったりします。
行き当たりばったりで書いているので順番等めちゃくちゃになるかもしれません。気づいたら加筆修正等はしていくつもりです。


今回は基本的な部分と、リスト、文字列の扱い、辞書型をまとめます。
便利な機能等を挙げていますが、行が少ないと速いというわけではなく当然それなりの処理があります。特にC問題では愚直に操作を行ったり、全探索をしてしまうと間に合わないケースが多いので気を付けたほうがいいと思います。そういった時のテクなどもいずれ紹介するつもりです。
なるべく色々なパターンを紹介しようとしていますがカバーしきれていないケースもあるので疑問に思った場合はその関数名で調べるなり自分で試すなりしていただければ理解が深まると思います。(関数や型の機能は調べてもらった方が早いし情報が多いです)
あくまで紹介という体でよろしくお願いします。
なお、ここにあるコードは全てAtCoderの環境での動作を確認しているつもりです。

#目次
|項目|内容|
|----|----|
|基本|基本的な入出力やちょっとした演算|
|インデックスとスライス|文字列やリストを扱ううえで便利な機能|
|辞書型|文字列などで管理できる便利な配列|
|便利な関数|ABCで使える便利な関数|
|応用編|紹介した機能を用いてABCで使える小技を紹介|
#基本
入力を

~~~
Hello world!
~~~
として考えます。


~~~python
s=input()
print(s)
#Hello world!
~~~
行を空白含めて文字列として読み取ります。(例:”Hello world!")

~~~python
s=input().split()
print(s)
#["Hello","world!"]
~~~
行を空白区切りのリストで取得します。
input()の返り値は上と同様"Hello world!"ですが、それをsplit()という関数で空白区切りで分割しています。

~~~python
s,t=input().split()
print(s,t)
#Hello world!
~~~
入力の空白区切りの要素数と左辺の要素数が同じであれば直接代入もできます。
print()はスペース区切りで1行で出力してくれます。

~~~python
s="Hello world!"

for c in s:#sの文字列から1文字ずつcとして参照
  print(c,end=" ")
print()#ただの改行
#H e l l o   w o r l d ! 
~~~
print()でendを指定してやると末尾に入る文字列を設定してやることが出来ます。デフォルトで改行が入っていますが、変更すれば改行をなくしたり、1文字ずつ間に挟んだりできます。

~~~python
s="Hello"
t="world"

u=s+" "+t+"!"*5
print(u)
#Hello world!!!!!

v=(s+" "+t+"!")*5
print(v)
#Hello world!Hello world!Hello world!Hello world!Hello world!
~~~
文字列同士の`+`は結合、`*`でその分繰り返すことが出来ます。記号の優先度は数字と同様*のほうが高いです。
また、数字と文字列でやろうとするともちろんエラーを吐きます。

~~~Python
print("ABC" in "ABCDE")#True
print("AC"  in "ABCDE")#False

print("ABC" in ["ABC","ARC","AGC"])#True
print("AB" in ["ABC","ARC","AGC"])#False
~~~
文字列A in 文字列B で文字列Bに文字列Aが含まれているかを判定します。判定するのは連続する部分文字列だけであり上の例で言うような飛び飛びの部分文字列は判定できません。
また、リスト内の検索にも使えますが、要素と完全に一致しないと判定できません。

~~~Python
a,b=3,4
print(a,b)#3 4
a,b=b,a
print(a,b)#4,3
~~~
代入にこのような記法ができるので、変数の入れかえも一発でできます。

##リストの基本

リストも、文字列同様リスト同士足したり定数を掛けたりできます。
また、リスト内包表記と呼ばれるfor文でリストを生成する方法もあります。

~~~Python
a=[7,6,5]
b=[3,4,6]
print(a+b)#[7, 6, 5, 3, 4, 6]
print(b+a)#[3, 4, 6, 7, 6, 5]
a.extend(b)
print(a)#[7, 6, 5, 3, 4, 6]

zeros=[0]*10
print(zeros)#[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
nums=[3,6,4]*3
print(nums)#[3, 6, 4, 3, 6, 4, 3, 6, 4]

print([i for i in range(10)])#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#↑ほとんど
#↓同じ
lis=[]
for i in range(10):
  lis.append(i)
print(lis)#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
~~~


#インデックスとスライス
文字列において、リストと同じようにn番目の文字を参照できます.


##インデックス
~~~python
print("Python"[0])#P
print("Python"[1])#y
print("Python"[5000])#エラー
print("Python"[-1])#n
print("Python"[-100])#エラー

print([6,5,4,3,2,1][-4])#4
~~~



n文字の時それぞれの文字を0からn-1で参照します。
範囲外を選択するとエラーを吐きます
また、一番最後の文字を-1番目としたマイナスの記法も存在します。(下参照)
実際マイナスで尻からたどれることと-1で最後尾が参照できることが分かれば大丈夫だと思います。

~~~
 0  1  2  3  4  5
 P  y  t  h  o  n
-6 -5 -4 -3 -2 -1
~~~

##スライス
スライスは文字列やリストで指定した範囲を取り出すことが出来る機能です。説明するより見たほうが早いです。

~~~Python
print("Python"[1:])#ython
print("Python"[:2])#Py
print("Python"[2:4])#th
print("Python"[::2])#Pto
print("Python"[::-1])#nohtyP

print([10,9,8,7,6,5,4,3,2,1][-3:-8:-2])#[3,5,7]
~~~
[start:stop:step]のようにコロンで区切って指定することで、自由に一定間隔の文字、要素を取り出すことが出来ます。
stepは省略可能で通常1になっています。また、start,stopの数字を省略すると端まで勝手にやってくれます。
そしてstepに負の値を入れると逆向きで行ってくれます

~~~Python
print("Python"[33:4:264])#空文字列
~~~
スライスでは無茶な指定をしてもエラーを吐かずに空文字列を返してくれます。

基本的に、forとかでよく使うrange()と同じ文法のはずです。

#辞書型
Pythonには辞書型(dict)という型があります。リストはインデックスで要素を参照しますが、辞書型ではkeyと呼ばれるもので参照します。(例:{key:要素}) 
keyは数字でも文字列でも割と何でも行けます(リストとかはダメ)。要素はリスト同様リストやら文字列やらもっと何でも行けます。

~~~Python
dic={"pen":1,"pineapple":2,"apple":"No",33:4}
print(dic["pen"])#1
print(dic["pineapple"])#2
print(dic["apple"])#No
print(dic[33])#4
print(dic[4])#エラー
~~~
また、リスト同様辞書内の要素に直接アクセスして変更を加えることや、inでkeyの存在をチェックすることも可能です。
また新たなkeyと要素を追加したい場合dict[key]=xxで代入することで追加することが出来ます。
dict.keys()でdict内のkeyを列挙することが出来ます。

~~~Python
inp=["bass","bass","kick","kick","bass","kick","kick"]
dic={}
for s in inp:
  if s in dic:#sというkeyが存在するかを判定
    dic[s]+=1
  else:#ない場合新しいkeyを作る
    dic[s]=1
for key in dic.keys():#.keys()でkeyを参照
  print(key+":"+str(dic[key]))

#bass:3
#kick:4
~~~
文字列で与えられた要素などをカウントする際に使えます。


#便利な関数
##map()
~~実はリスト内包表記で事足りる~~
イテラブルなもの(リストやタプルなど)のすべての要素に対して関数を適用します。細かい説明は省くので詳しくは"Python map"とかで調べてください。ここではリストの全ての要素に関数を適用する例を挙げます。
第一引数に関数を、第二引数にイテラブルなもの(ここではリスト)を入れます。第一引数の関数が引数を2つ、3つと要求する場合mapの第三、第四引数に同様にリストを入れておけばそれらがその関数の第二、第三引数として機能します。
map()の返り値はmap型のオブジェクトなのでそのまま出力する際はlist()に入れて変換してやる必要があります。
自作関数でも可能なのでリスト全体に対して一定の操作をしたい場合などに使えます。

~~~Python
lis=[1,-2,3,-4,5]
print(map(abs,lis))#<map object at なんとかかんとか>
print(list(map(abs,lis)))#[1, 2, 3, 4, 5]
print([abs(i) for i in lis])#[1, 2, 3, 4, 5](やっていることは同じ) 
~~~

また、map()を用いて複数個の数字の入力もできます。
input().split()で文字列のリストを取得してintに変換しています。
前者の場合入力の要素数と左辺の変数の数が合わないとエラーになるので気を付けてください。


~~~Python
a,b=map(int,input().split())
lis=list(map(int,input().split()))
~~~



##count()
その名の通り文字列内の文字やリスト内の要素をカウントしてくれる関数です。

~~~python
print("aaa".count("a"))#3
print("aaa".count("aa"))#1
~~~
複数文字を指定する場合は重ならないように選ぶので後者は1となります。

~~~python
print([1,1,1,4,4,5].count(1))#3
print(["ABC","ARC","AGC"].count("AHC"))#0
~~~
リストでも同様のことが出来ます。(完全一致)
また、該当する要素が無い場合0を返します。

##replace()
文字列のうち特定の部分文字列を置き換えます。
先頭から置き換えられるので重なっていてそれが置き換えられた場合重なっていた後ろの方は放置されます。
置き換えですが第二引数に空文字列を指定すれば削除できたり、二つの引数が同じ長さである必要はありません。

~~~Python
print("aaa".replace("a","x"))#xxx
print("aaa".replace("aa","x"))#xa
~~~


##upper(),lower(),capitalize()
それぞれ、文字列をupper(大文字)、lower(小文字)にする、先頭を大文字にする関数です

~~~python
print("AbCdEfG".upper())#ABCDEFG
print("AbCdEfG".lower())#abcdefg
print("AbCdEfG".capitalize())#Abcdefg
print("なんだしなんだしagc".upper())#なんだしなんだしAGC
print("ＺＥＮＫＡＫＵ".lower())#ｚｅｎｋａｋｕ
~~~
大文字小文字の区別があるものなら変換可能です。また変換可能でなくてもエラーを吐くことはなく変換可能な物だけを変換してくれます。

##isupper(),islower()
文字列が、**大文字小文字の区別があるものが完全に**upper(大文字)、lower(小文字)であるかを判別する関数です。
ただし、文字列のすべてが大文字小文字の区別が無いものである場合には**Falseになります**。

~~~python
print("ABC".isupper())#True
print("ABC".islower())#False
print("abc".isupper())#False
print("abc".islower())#True
print("aBc".isupper())#False
print("aBc".isupper())#False
print("なんだしなんだしAGC".isupper())#True
print("なんだし".isupper())#False
print("".isupper())#False
~~~

#join(),split()
それぞれ、リストから文字列を、文字列からリストを作る関数です。

~~~python
l=["霧","霧","奇","譚"]

print("".join(l))#霧霧奇譚

s1=" ".join(l)
print(s1)#霧 霧 奇 譚

s2="・".join(l)
print(s2)#霧・霧・奇・譚

#s1をスペース区切りでリスト化
print(s1.split())#['霧', '霧', '奇', '譚']

#s2をスペース区切りでリスト化(スペースが無いのでそのまま文字列として入る)
print(s2.split())#['霧・霧・奇・譚']

#s2を点で区切ってリスト化
print(s2.split("・"))#['霧', '霧', '奇', '譚']

#文字列をそのまま1文字ずつリスト化
print(list(s2))#['霧', '・', '霧', '・', '奇', '・', '譚']

~~~
"任意の文字列(空文字列でも可)".join(list)で、listの要素の間に任意の文字列を挟んで文字列にすることが出来ます。
また、文字列.split(任意の文字列(空の場合空白))で、文字列を任意の文字列で区切ってリスト化できます。
この辺は文字列系の問題で役立つことがあります。

ただし、数字のリストの場合文字列に変換してやらないと怒られるのでmapで変換してやってからjoinします。
これは[特定の条件を満たす数列を出力しなさいみたいな問題](https://atcoder.jp/contests/arc117/tasks/arc117_a)で使えます。

~~~Python
lis=[1,2,3,4,5]
print(" ".join(map(str,lis)))
#1 2 3 4 5
~~~

#sort(),sorted()
リストをソートすることが出来ます。様々なオプションで調整することもできます。(ここではreverseを挙げます)
また、sorted()はもとになるリストを変更せずにソートされたリストを返します。(非破壊的)
.sort()はそのリストを書き換えてソートを行います。(破壊的)


~~~Python
lis=[3,1,4,1,5,9,2]

print(sorted(lis))#[1, 1, 2, 3, 4, 5, 9]
print(lis)#[3,1,4,1,5,9,2]
lis.sort()
print(lis)#[1, 1, 2, 3, 4, 5, 9]
lis.sort(reverse=True)
print(lis)#[9, 5, 4, 3, 2, 1, 1]

~~~

#実用編
ここからはこれまでに取り上げた機能を用いて実際に問題を解いていきます。
問題名がリンクになっているので自分で考えてみたい方はそこから飛んであまり下まで行かずに自分で解いてみてください。

##[ABC192-B uNrEaDaBlE sTrInG](https://atcoder.jp/contests/abc192/tasks/abc192_b)
>先頭から奇数番目の文字が全て英小文字であり、かつ、先頭から偶数番目の文字が全て英大文字であるような文字列を**読みにくい文字列**と呼びます。
>文字列*S*が読みにくい文字列かどうか判定してください。




一撃です。

~~~Python
s="aA"+input()
if s[::2].islower() and s[1::2].isupper():
  print("Yes")
else:
  print("No")
~~~

このようにスライスとisupper(),islower()を駆使することで一瞬で書きあげることが出来ます。
***S***の長さが1の場合に、s[1::2]が空文字列となり無条件に"No"を出力することを防ぐために、あらかじめ***S***の頭に条件を満たした文字列を挿入しています。ちゃんとテストケースでチェックしていればこの想定外の挙動に気づくことが出来ます。

##[ABC173-B Judge Status Summary](https://atcoder.jp/contests/abc173/tasks/abc173_b)

>高橋君は、プログラミングコンテスト AXC002 に参加しており、問題 A にコードを提出しました。
>この問題には*N*個のテストケースがあります。
>各テストケース*i*(*1≤i≤N*) について、ジャッジ結果を表す文字列*S*<sub>*i*</sub>が与えられるので、ジャッジ結果が AC, WA, TLE, RE であったものの個数をそれぞれ求めてください。


辞書型を使えば楽勝です。

~~~Python
n=int(input())
dic={"AC":0,"WA":0,"TLE":0,"RE":0}

for i in range(n):
  s=input()
  dic[s]+=1
for key in ["AC","WA","TLE","RE"]:
  print(key+" x "+str(dic[key]))
~~~

最後の出力に関してはdic.keys()を使ってもAtCoder上であればおそらく[問題はない](https://atcoder.jp/contests/abc173/submissions/22459055)んですが、万が一のためにこの形にしています。
dict型のkeyの順序はPython3.7から[保証されているそう](https://qiita.com/arc279/items/9165b9f9e95fcd5cc67f)です。

###似た問題
[ABC164-C Gacha](https://atcoder.jp/contests/abc164/tasks/abc164_c)

##[ABC192-C Kaprekar Number](https://atcoder.jp/contests/abc192/tasks/abc192_c)
>0以上の整数*x*に対して、*g*<sub>1</sub>(*x*),*g*<sub>2</sub>(*x*),*f*(*x*)を次のように定めます。
>>*g*<sub>1</sub>(*x*)=*x*を十進法で表した時の各桁の数字を大きい順に並び変えてできる整数
>>*g*<sub>2</sub>(*x*)=*x*を十進法で表した時の各桁の数字を小さい順に並び変えてできる整数
>>*f*(*x*)=*g*<sub>1</sub>(*x*)-*g*<sub>2</sub>(*x*)

>整数*N*,*K*が与えられるので、*a*<sub>0</sub>=*N*, *a<sub>i*+1</sub>=*f*(*a<sub>i*</sub>) (*i*≥0)で定まる数列の*a<sub>K*</sub>を求めてください。

ちなみに問題名は[カプレカー数](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%97%E3%83%AC%E3%82%AB%E3%83%BC%E6%95%B0#:~:text=%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE-,D.%20R.,Mathematics%2013%3A%2081%E2%80%9382.)と読むらしいです。
問題文を読むと数字をリストとしてとらえてソートすればいいのがなんとなくわかります。

~~~Python
n,k=map(int,input().split())
 
for i in range(k):
  s=list(str(n))#nをリスト化
  g1=int("".join(sorted(s,reverse=True)))#ソートして文字列として結合した後にintに変換
  g2=int("".join(sorted(s)))
  n=g1-g2
print(n)
~~~
nを文字列にしてリスト化(例:19419→['1','9','4','1,'9'])
そのリストをソートして結合(例:['1','9','4','1,'9']→['1','1','4','9','9']→'11499'→11499)
を行っています。
問題文に書かれていることをそのまま書いているだけです。難しそうですがちゃんと考えて組み合わせればシンプルに素早く書けるようになります。

#最後に
アレを書くならコレも書かなきゃという感じで結構な長さになってしまいました。
set型や諸ライブラリ等まだまだ紹介しきれていないのでいずれPart2を書くつもりです。
実用編書いてて思ったんですけどこれだけで楽々解ける問題ってそんなにないですね……
あくまで小技の紹介なのでこうした方が早いとかはちょっと許してください……
A～C問題は全部埋めるくらいの勢いで過去問巡回すると解くのがかなり早くなります。3完あたりは特に早さでパフォーマンスが開くと思うのでまずは早い3完で高いパフォーマンスを取るのを目標にしてみるといいと思います。