はじめに
AtCoder の問題を Python で解いており、得られた知見をメモとして残しています。
本記事について
本記事について説明します。
構成
本記事では 分類観点 を定義し、分類観点ごとに問題を分類しています。各分類観点では、サンプルコード(入力 / 実行結果)と 解答例 を記載しています。サンプルコード(入力 / 実行結果)と 解答例 は下記の通りです。
項目 | 項目内容 |
---|---|
サンプルコード | 問題から得られた知見と検証によって得られた知見を整理したコード |
入力 | サンプルコードの入力例 |
実行結果 | サンプルコードの実行結果 |
解答例 | AtCoder で AC になったコード |
解答例(TLE) | AtCoder で TLE になったコード |
分類観点の定義
分類観点の定義は下記の通りです。1つの問題から複数の観点で分類できる問題は、複数の観点に分類します。
章 | 観点 | 観点内容 |
---|---|---|
第1章 | 入出力処理観点 | 入出力処理を知っていれば解ける問題 |
第2章 | 演算観点 | 演算を知っていれば解ける問題 |
第3章 | 制御構文観点 | 制御構文を知っていれば解ける問題 |
第4章 | 組み込み型観点 | 組み込み型を知っていれば解ける問題 |
第5章 | 組み込み関数観点 | 組み込み関数を知っていれば解ける問題 |
第6章 | モジュール観点 | モジュールを知っていれば解ける問題 |
第7章 | データ構造観点 | データ構造を知っていれば解ける問題 |
第8章 | アルゴリズム観点 | アルゴリズムを知っていれば解ける問題 |
第9章 | 計算量観点 | 計算量を工夫すれば解ける問題 |
第10章 | 数学観点 | 数学的知見を知っていれば解ける問題 |
第11章 | カテゴリ観点 | カテゴリ特有の解き方を知っていれば解ける問題 |
- | 参考 | - |
分類する問題の範囲
分類する問題の範囲は下記の通りです。ABC-C問題 と ARC-A問題 は一部の問題が同じです。同じ問題の場合、ABC-C問題 として分類します。
- ABC-A問題(ABC001 - ABC253)
- ABC-B問題(ABC001 - ABC253)
- ABC-C問題(ABC001 - ABC253)
- ARC-A問題(ARC001 - ARC137)
- AtCoder Problems における Difficulty 0 - 800 の問題
分類する対象の問題
本記事では、上記分類範囲で示したすべての問題が記載されているわけではありません。私が上記分類観点で知見が得られた問題のみを記載しています。
バージョン / 言語
サンプルコードは Python の下記バージョンで動作することを確認しました。
Python 3.8.2
解答例は AtCoder の下記言語で AC になることを確認しました。
Python (3.8.2)
コーディングスタイル
本記事のサンプルコードは pycodestyle の下記バージョンでコーディングスタイルを確認しました。
pycodestyle 2.8.0
コードリポジトリ
本記事のコードは下記のリポジトリで公開しています。
最後に
サービスを提供している AtCoder株式会社 と、交流している 競技プログラマ の方々に感謝を致します。
第1章 入出力処理観点
1.1 出力
整数(int)
整数を出力する
print(10)
10
整数を変数に格納して出力する
x = 20
print(x)
20
浮動小数点数(float)
浮動小数点数を出力する
print(2.9)
2.9
浮動小数を変数に格納して出力する
x = 3.5
print(x)
3.5
文字列(str)
文字列を出力する
print("Hello World!")
Hello World!
文字列を変数に格納して出力する
x = "Hello World!"
print(x)
Hello World!
文字列の変数のインデックスを指定して文字を出力する
x = "Hello World!"
print(x[0])
print(x[11])
H
!
リスト(list)
1次元リストを出力する
x = [1, 2, 3, 4, 5]
print(x)
[1, 2, 3, 4, 5]
1次元リストの各要素を出力する
x = [1, 2, 3, 4, 5]
for i in x:
print(i)
1
2
3
4
5
1次元リストのインデックス指定して各要素を出力する
x = [1, 2, 3, 4, 5]
for i in range(len(x)):
print(x[i])
1
2
3
4
5
1次元リストをアンパックで出力する
x = [1, 2, 3, 4, 5]
print(*x)
1 2 3 4 5
2次元リストを出力する
x = [[1, 2, 3], [4, 5, 6]]
print(x)
[[1, 2, 3], [4, 5, 6]]
2次元リストの各行を出力する
x = [[1, 2, 3], [4, 5, 6]]
for rows in x:
print(rows)
[1, 2, 3]
[4, 5, 6]
2次元リストの各要素を出力する
x = [[1, 2, 3], [4, 5, 6]]
for rows in x:
for columns in rows:
print(columns)
1
2
3
4
5
6
2次元リストの各要素をインデックス指定して出力する
x = [[1, 2, 3], [4, 5, 6]]
for i in range(len(x)):
for j in range(len(x[i])):
print(x[i][j])
1
2
3
4
5
6
2次元リストの各行をアンパックで出力する
x = [[1, 2, 3], [4, 5, 6]]
print(*x)
[1, 2, 3] [4, 5, 6]
- ABC051 A - Haiku
- ABC042 B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)
- ABC137 B - One Clue
- ABC148 B - Strings with the Same Length
- ABC191 B - Remove It
- キーエンス プログラミング コンテスト 2020 C - Subarray Sum
- 天下一プログラマーコンテスト2014予選A A - 天下一序数
- 天下一プログラマーコンテスト2012 予選A B - 分類たん
- Code Formula 2014 予選A B - ボウリングゲーム
タプル(tuple)
x = 1, 2, 3
print(x)
(1, 2, 3)
区切り文字の指定
- print():キーワード引数 sep を指定する
指定がないと 半角スペース で区切る
x = 1
y = 2
z = 3
print(x, y, z)
1 2 3
改行 を指定する
x = 1
y = 2
z = 3
print(x, y, z, sep="\n")
1
2
3
カンマ を指定する
x = 1
y = 2
z = 3
print(x, y, z, sep=",")
1,2,3
区切り文字なし を指定する
x = 1
y = 2
z = 3
print(x, y, z, sep="")
123
- ABC046 B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)
- ABC148 B - Strings with the Same Length
末尾文字の指定
- print():キーワード引数 end を指定する
指定がないと 改行する
print("x")
print("y")
x
y
末尾文字なし を指定する
print("x", end="")
print("y")
xy
1.2 入力
- input():入力から1行を読み込み、文字列に変換して(末尾の改行を除いて)返す
- map():function の結果を返しながら、全ての要素に適用する iterator を返す
- str.split():文字列を区切った単語のリストで返す
- リスト内包表記
1行 / 1列
整数を変数に格納する
2
x = int(input())
print(x)
2
文字列を1つの変数に格納する
Hello world!
x = input()
print(x)
Hello world!
文字列を複数の変数に格納する
123
x, y, z = input()
print(x, y, z)
1 2 3
abc
x, y, z = input()
print(x, y, z)
a b c
アンパックを使って変数に格納する
abcde
x, *y = input()
print(y)
['b', 'c', 'd', 'e']
abcde
*x, y = input()
print(x)
['a', 'b', 'c', 'd']
abcde
x, *y, z = input()
print(y)
['b', 'c', 'd']
abcde
*x, y, z = input()
print(x)
['a', 'b', 'c']
abcde
x, y, *z = input()
print(z)
['c', 'd', 'e']
1行 / 複数列
整数を複数の変数に格納する
1 2
x, y = map(int, input().split())
print(x)
print(y)
1
2
文字列を複数の変数に格納する
Hello world!
x, y = input().split()
print(x)
print(y)
Hello
world!
整数をリストに格納する
1 2 3 4 5
x = list(map(int, input().split()))
print(x)
[1, 2, 3, 4, 5]
1 2 3 4 5
x = [int(i) for i in input().split()]
print(x)
[1, 2, 3, 4, 5]
文字列をリストに格納する
Hello world !
x = list(input().split())
print(x)
['Hello', 'world', '!']
Hello world !
x = [i for i in input().split()]
print(x)
['Hello', 'world', '!']
アンパックを使って変数に格納する
a b c d e
x, *y = input().split()
print(y)
['b', 'c', 'd', 'e']
a b c d e
*x, y = input().split()
print(x)
['a', 'b', 'c', 'd']
a b c d e
x, *y, z = input().split()
print(y)
['b', 'c', 'd']
a b c d e
*x, y, z = input().split()
print(x)
['a', 'b', 'c']
a b c d e
x, y, *z = input().split()
print(z)
['c', 'd', 'e']
1 2 3 4 5
*x, = map(int, input().split())
print(x)
[1, 2, 3, 4, 5]
複数行 / 1列
整数を複数の変数に格納する
1
2
x = int(input())
y = int(input())
print(x, y)
1 2
1
2
x, y = [int(input()) for i in range(2)]
print(x, y)
1 2
- ABC044 A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)
- ABC087 A - Buying Sweets
- ABC092 A - Traveling Budget
整数をリストに格納する
1
2
3
4
5
x = [int(input()) for i in range(5)]
print(x)
[1, 2, 3, 4, 5]
文字列をリストに格納する
a
b
c
d
e
x = [input() for i in range(5)]
print(x)
['a', 'b', 'c', 'd', 'e']
入力行数(Row=5)が指定され、整数をリストに格納する
5
0
1
2
3
4
rows = int(input())
x = [int(input()) for i in range(rows)]
print(x)
[0, 1, 2, 3, 4]
入力行数(Row=5)が指定され、文字列をリストに格納する
5
a
b
c
d
e
rows = int(input())
x = [input() for i in range(rows)]
print(x)
['a', 'b', 'c', 'd', 'e']
複数行 / 複数列
整数を2次元リストに格納する(入力時に行数が指定されない)
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
x = [list(map(int, input().split())) for i in range(3)]
print(x)
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
複数のリストに格納する(入力時に行数(rows)を指定する)
3
0 a
1 b
2 c
rows = int(input())
number = []
alphabet = []
for i in range(rows):
n, a = input().split()
number.append(int(n))
alphabet.append(a)
print(number)
print(alphabet)
[0, 1, 2]
['a', 'b', 'c']
整数を2次元リストに格納する(入力時に行数(rows)を指定する)
3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
rows = int(input())
x = [list(map(int, input().split())) for i in range(rows)]
print(x)
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
rows = int(input())
x = [[int(j) for j in input().split()] for i in range(rows)]
print(x)
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
rows = int(input())
x = []
for i in range(rows):
x.append(list(map(int, input().split())))
print(x)
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
整数を1次元リストに格納する
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
x = []
for i in range(3):
x += list(map(int, input().split()))
print(x)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
それぞれの変数に格納する
1 2
3 4
a, b = map(int, input().split())
c, d = map(int, input().split())
print(a, b, c, d)
1 2 3 4
w x
y z
a, b = input().split()
c, d = input().split()
print(a, b, c, d)
w x y z
区切り文字の指定
a,b,c,d
x = list(input().split(","))
print(*x)
a b c d
2019/02/26
y, m, d = map(int, input().split("/"))
print(y, m, d)
2019 2 26
第2章 演算観点
2.1 算術演算
演算子 | 記述例 | 意味 |
---|---|---|
+ | a + b | 加算 |
- | a - b | 減算 |
* | a * b | 乗算 |
** | a ** b | べき乗 / べき根 |
/ | a / b | 除算 |
// | a // b | 小数点切り捨て除算 |
% | a % b | 剰余 |
加算
print(1+2)
3
x = 2+3
print(x)
5
x = 3
y = 4
print(x+y)
7
減算
print(2-1)
1
x = 4-2
print(x)
2
x = 3
y = 6
print(x-y)
-3
- ABC001 A - 積雪深差
- ABC007 A - 植木算
- ABC008 A - アルバム
- ABC058 A - ι⊥l
- ABC072 A - Sandglass2
- ABC074 A - Bichrome Cells
- ABC076 A - Rating Goal
- ABC084 A - New Year
- ABC103 A - Task Scheduling Problem
- ABC106 A - Garden
- ABC107 A - Train
- ABC123 A - Five Antennas
- ABC136 A - Transfer
- ABC170 A - Five Variables
- ABC180 A - box
- ABC196 A - Difference Max
- ABC198 A - Div
- ABC202 A - Three Dice
- ABC209 A - Counting
- ABC013 B - 錠
- ABC073 B - Theater
- Code Formula 2014 予選B A - サイコロ
乗算
print(3*2)
6
x = 4*3
print(x)
12
x = 5
y = 6
print(x*y)
30
- ABC004 A - 流行
- ABC017 A - プロコン
- ABC028 A - テスト評価
- ABC031 A - ゲーム
- ABC052 A - Two Rectangles
- ABC069 A - K-City
- ABC076 A - Rating Goal
- ABC106 A - Garden
- ABC121 A - White Cells
- ABC150 A - 500 Yen Coins
- ABC163 A - Circle Pond
- ABC169 A - Multiplication 1
- ABC172 A - Calc
- ABC182 A - twiblr
- ABC184 A - Determinant
- ABC199 A - Square Inequality
階乗
- math.factorial():階乗を整数で返す
import math
print(math.factorial(5))
120
べき乗
print(2**3)
8
print(10**9+7)
1000000007
x = 3**2
print(x)
9
x = 4
y = 2
print(x**y)
16
- ABC074 A - Bichrome Cells
- ABC134 A - Dodecagon
- ABC140 A - Password
- ABC145 A - Circle
- ABC172 A - Calc
- ABC199 A - Square Inequality
- ABC221 A - Seismic magnitude scales
- ABC237 A - Not Overflow
- ABC068 B - Break Number
- ABC097 B - Exponential
- ABC208 B - Factorial Yen Coin
- ABC178 C - Ubiquity
- ABC0185 C - Duodecim Ferra
- ABC0193 C - Unexpressed
- ABC205 C - POW
- ABC189 D - Logical Expression
- ARC036 A - 数え上げ
- CODE FESTIVAL 2015 予選A B - とても長い数列
べき根
print(9**0.5)
3.0
print(9**.5)
3.0
print(9**(1/2))
3.0
print(8**(1/3))
2.0
x = 16**.5
print(x)
4.0
x = 16
y = .5
print(x**y)
4.0
除算
print(6/3)
2.0
print(7/3)
2.3333333333333335
x = 9/3
print(x)
3.0
x = 12
y = 3
print(x/y)
4.0
- ABC117 A - Entrance Examination
- ABC193 A - Discount
- ABC205 A - kcal
- ABC211 A - Blood Pressure
- ABC231 A - Water Pressure
- ABC242 A - T-shirt
- ABC138 B - Resistors in Parallel
- ABC138 C - Alchemist
- 第二回日本最強プログラマー学生選手権 A - Competition
小数点切り捨て除算
print(5//3)
1
print(6//3)
2
print(7//3)
2
print(-5//3)
-2
print(-6//3)
-2
print(-7//3)
-3
import math
print(math.floor(-5/3))
-2
import math
print(math.floor(-6/3))
-2
import math
print(math.floor(-7/3))
-3
- ABC005 A - おいしいたこ焼きの作り方
- ABC030 A - 勝率計算
- ABC055 A - Restaurant
- ABC089 A - Grouping 2
- ABC108 A - Pair
- ABC113 A - Discount Fare
- ABC116 A - Right Triangle
- ABC117 A - Entrance Examination
- ABC128 A - Apple Pie
- ABC142 A - Odds of Oddness
- ABC153 A - Serval vs Monster
- ABC159 A - The Number of Even Pairs
- ABC186 A - Brick
- ABC200 A - Century
- ABC078 B - ISU
- ABC095 B - Bitter Alchemy
- ABC158 B - Count Balls
- ABC164 B - Battle
- ABC203 B - AtCoder Condominium
- ABC239 B - Integer Division
- ARC104 A - Plus Minus
小数点切り上げ除算
- math.ceil():引数以上の最小の整数を返す
import math
print(math.ceil(1.1))
2
import math
print(math.ceil(7/3))
3
x = 7
y = 3
print((x+y-1)//y)
3
- ABC009 A - 引越し作業
- ABC036 A - お茶
- ABC082 A - Round Up the Mean
- ABC153 A - Serval vs Monster
- ABC157 A - Duplex Printing
- ABC015 B - 高橋くんの集計
- ABC123 B - Five Dishes
- ABC134 B - Golden Apple
- ABC139 B - Power Socket
- ABC164 B - Battle
- ABC195 B - Many Oranges
- ABC207 B - Hydrate
- ABC123 C - Five Transportations
- キーエンス プログラミング コンテスト 2020 A - Painting
- 三井住友信託銀行プログラミングコンテスト2019 B - Tax Rate
- 第二回日本最強プログラマー学生選手権 A - Competition
剰余
print(6 % 3)
0
print(7 % 3)
1
print(8 % 3)
2
print(-6 % 3)
0
print(-7 % 3)
2
print(-8 % 3)
1
- ABC009 A - 引越し作業
- ABC011 A - 来月は何月?
- ABC014 A - けんしょう先生のお菓子配り
- ABC016 A - 12月6日
- ARC035 A - テレビ
- ABC054 A - One Card Poker
- ABC057 A - Remaining Time
- ABC064 A - RGB Cards
- ABC067 A - Sharing Cookies
- ABC081 A - Placing Marbles
- ABC086 A - Product
- ABC087 A - Buying Sweets
- ABC088 A - Infinite Coins
- ABC102 A - Multiple of 2 and N
- ABC105 A - AtCoder Crackers
- ABC118 A - B +/- A
- ABC135 A - Harmony
- ABC153 A - Serval vs Monster
- ABC157 A - Duplex Printing
- ABC168 A - ∴ (Therefore)
- ABC173 A - Payment
- ABC176 A - Takoyaki
- ABC181 A - Heavy Rotation
- ABC192 A - Star
- ABC195 A - Health M Death
- ABC204 A - Rock-paper-scissors
- ABC220 A - Find Multiple
- ABC223 A - Exact Price
- ABC227 A - Last Card
- ABC233 A - 10yen Stamp
- ABC243 A - Shampoo
- ABC249 A - Jogging
- ABC034 B - ペア
- ABC041 B - 直方体
- ABC060 B - Choose Integers
- ABC146 B - ROT N
- ABC158 B - Count Balls
- ABC160 B - Golden Coins
- ABC200 B - 200th ABC-200
- ABC232 B - Caesar Cipher
- ABC238 B - Pizza
- ABC099 C - Strange Bank
- ABC133 C - Remainder Minimization 2019
- ABC161 C - Replacing Integer
- ABC174 C - Repsept
- ABC178 C - Ubiquity
- ABC200 C - Ringo's Favorite Numbers 2
- ABC238 C - digitnum
- ABC167 D - Teleporter
- ABC174 D - Alter Altar
- ARC008 A - たこ焼き買えるかな?
- 三井住友信託銀行プログラミングコンテスト2019 C - 100 to 105
- CODE FESTIVAL 2014 Easy B - チーム作り
- CODE FESTIVAL 2014 予選A B - とても長い文字列
10*n+7
2.2 代入文
x, y = 1, 2
print(x, y)
x, y = y, x
print(x, y)
1 2
2 1
- ABC006 B - トリボナッチ数列
- ABC079 B - Lucas Number
- ARC007 B - 迷子のCDケース
- AGC014 A - Cookie Exchanges
- 天下一プログラマーコンテスト2015予選B A - 天下一プログラマーコンテスト1998
2.3 累算代入文
演算子 | 記述例 | 等式 |
---|---|---|
+= | a += b | a = a + b |
-= | a -= b | a = a - b |
*= | a *= b | a = a * b |
**= | a **= b | a = a ** b |
/= | a /= b | a = a / b |
//= | a //= b | a = a // b |
%= | a %= b | a = a % b |
2.4 論理演算
演算子 | 記述例 | 意味 |
---|---|---|
and | a and b | a も b も真であれば真 |
or | a or b | a または b が真であれば真 |
not | not a | a が偽であれば真 |
print(True and True)
True
print(True and False)
False
print(False and False)
False
print(True or True)
True
print(True or False)
True
print(False or False)
False
print(not True)
False
print(not False)
True
- ABC094 A - Cats and Dogs
- ABC097 A - Colorful Transceivers
- ABC100 A - Happy Birthday!
- ABC038 B - ディスプレイ
- ABC155 B - Papers, Please
- ARC002 A - うるう年
- Tenka1 Programmer Beginner Contest 2019 A - On the Way
2.5 比較演算
演算子 | 記述例 | 意味 |
---|---|---|
== | a == b | a が b と等しい |
!= | a != b | a が b と等しくない |
> | a > b | a が b より大きい |
>= | a >= b | a が b 以上 |
< | a < b | a が b より小さい |
<= | a <= b | a が b 以下 |
print(10 == 10)
True
print(10 == 20)
False
print(10 != 20)
True
print(10 != 10)
False
print(20 > 10)
True
print(10 > 20)
False
print(10 >= 10)
True
print(10 >= 11)
False
print(10 < 20)
True
print(20 < 10)
False
print(10 <= 10)
True
print(10 <= 9)
False
2.6 所属検査演算
演算子 | 記述例 | 意味 |
---|---|---|
in | a in b | a が b に含まれる |
not in | a not in b | a が b に含まれない |
print("a" in "abc")
True
print("z" not in "abc")
True
print("a" in ["a", "b", "c"])
True
print("z" not in ["a", "b", "c"])
True
print(1 in [1, 2, 3])
True
print(9 not in [1, 2, 3])
True
2.7 ブール演算
bool関数でFalse
になる条件
種類 | 演算子 |
---|---|
数値 | 0 または 0.0 |
文字列 | 空文字列 |
コンテナ | 空要素 |
論理値 | False |
特殊 | None |
演算式 | not True |
ブール値を数値に変換
print(int(True))
1
print(int(False))
0
print(+(3 > 2))
1
print(+(3 < 2))
0
print(-(3 > 2))
-1
print(-(3 < 2))
0
print(True+0)
1
print(False+0)
0
- ABC022 A - Best Body
- ABC024 A - 動物園
- ABC096 A - Day of Takahashi
- ABC105 A - AtCoder Crackers
- ABC130 A - Rounding
- ABC172 B - Minor Change
- ABC130 C - Rectangle Cutting
- ARC015 B - 真冬日?真夏日?
- 三井住友信託銀行プログラミングコンテスト2019 A - November 30
2.8 ビット演算
演算子 | 記述例 | 意味 |
---|---|---|
& | a & b | a と b のビット単位の AND を与える |
^ | a ^ b | a と b のビット単位の XOR(排他的OR)を与える |
| | a | b | a と b のビット単位の OR を与える |
~ | ~a | a(整数)のビット単位反転を与える |
演算 | 結果 |
---|---|
bin(0b1010 & 0b0110) | 0b10 |
bin(0b1010 ^ 0b0110) | 0b1100 |
bin(0b1010 | 0b0110) | 0b1110 |
print(bin(0b1010 & 0b0110))
print(bin(0b1010 ^ 0b0110))
print(bin(0b1010 | 0b0110))
0b10
0b1100
0b1110
- ABC027 A - 長方形
- ABC213 A - Bitwise Exclusive Or
- ABC155 B - Papers, Please
- ABC215 B - log2(N)
- ABC197 C - ORXOR
- ABC171 E - Red Scarf
- AGC035 A - XOR Circle
ビット単位反転(bitwise invert):a
のビット単位反転は-(a+1)
として定義されている
print(~2)
-3
print(~-4)
3
2.9 シフト演算
演算子 | 記述例 | 意味 |
---|---|---|
<< | a << b | a を左に b ビットシフト |
>> | a >> b | a を右に b ビットシフト |
左にビットシフト
演算 | 結果 | 10進数 |
---|---|---|
bin(1) | 0b1 | 1 |
bin(1 << 1) | 0b10 | 2 |
bin(1 << 2) | 0b100 | 4 |
bin(1 << 3) | 0b1000 | 8 |
bin(1 << 4) | 0b10000 | 16 |
print(1)
print(1 << 1)
print(1 << 2)
print(1 << 3)
print(1 << 4)
print(bin(1))
print(bin(1 << 1))
print(bin(1 << 2))
print(bin(1 << 3))
print(bin(1 << 4))
1
2
4
8
16
0b1
0b10
0b100
0b1000
0b10000
右にビットシフト
演算 | 結果 | 10進数 |
---|---|---|
bin(10) | 0b1010 | 10 |
bin(10 >> 1) | 0b101 | 5 |
bin(10 >> 2) | 0b10 | 2 |
bin(10 >> 3) | 0b1 | 1 |
bin(10 >> 4) | 0b0 | 0 |
print(10)
print(10 >> 1)
print(10 >> 2)
print(10 >> 3)
print(10 >> 4)
print(bin(10))
print(bin(10 >> 1))
print(bin(10 >> 2))
print(bin(10 >> 3))
print(bin(10 >> 4))
10
5
2
1
0
0b1010
0b101
0b10
0b1
0b0
第3章 制御構文観点
3.1 条件式
if/elif/else
x = 1
print("x is 1" if x == 1 else "x is 2" if x == 2 else "other")
x is 1
x = "a"
print("x is a" if x == "a" else "x is b" if x == "b" else "other")
x is a
x, y = "a", 1
print("a", y) if x == "a" else print("b", y) if x == "b" else print("other")
a 1
- ABC020 A - クイズ
- ABC028 A - テスト評価
- ABC030 A - 勝率計算
- ABC034 A - テスト
- ABC053 A - ABC/ARC
- ABC056 A - HonestOrDishonest
- ABC065 A - Expired?
- ABC072 A - Sandglass2
- ABC075 A - One out of Three
- ABC078 A - HEX
- ABC083 A - Libra
- ABC091 A - Two Coins
- ABC094 A - Cats and Dogs
- ABC096 A - Day of Takahashi
- ABC099 A - ABD
- ABC104 A - Rated for Me
- ABC112 A - Programming Education
- ABC122 A - Double Helix
- ABC130 A - Rounding
- ABC135 A - Harmony
- ABC136 A - Transfer
- ABC138 A - Red or Not
- ABC141 A - Weather Prediction
- ABC142 A - Odds of Oddness
- ABC150 A - 500 Yen Coins
- ABC152 A - AC or WA
- ABC153 A - Serval vs Monster
- ABC154 A - Remaining Balls
- ABC156 A - Beginner
- ABC157 A - Duplex Printing
- ABC164 A - Sheep and Wolves
- ABC166 A - A?C
- ABC173 A - Payment
- ABC174 A - Air Conditioner
- ABC177 A - Don't be late
- ABC178 A - Not
- ABC183 A - ReLU
- ABC190 A - Very Very Primitive Game
- ABC194 A - I Scream
- ABC199 A - Square Inequality
- ABC203 A - Chinchirorin
- ABC204 A - Rock-paper-scissors
- ABC212 A - Alloy
- ABC214 A - New Generation ABC
- ABC228 A - On and Off
- ABC238 A - Exponential or Quadratic
- ABC240 A - Edge Checker
- ABC242 A - T-shirt
- ABC243 A - Shampoo
- ABC016 B - A±B Problem
- ABC031 B - 運動管理
- ABC038 B - ディスプレイ
- ABC059 B - Comparison
- ABC149 B - Greedy Takahashi
- ABC130 C - Rectangle Cutting
- ABC205 C - POW
- ARC002 A - うるう年
- ARC015 B - 真冬日?真夏日?
- AGC003 A - Wanna go back home
- M-SOLUTIONS プロコンオープン 2020 A - Kyu in AtCoder
- Tenka1 Programmer Beginner Contest 2019 A - On the Way
- SoundHound Inc. Programming Contest 2018 -Masters Tournament- A - F
- CODE FESTIVAL 2016 qual B B - Qualification simulator
- 東京海上日動 プログラミングコンテスト2020 A - Nickname
if/in
x = "abc"
print("True" if "ab" in x else "False")
True
x = ["a", "b", "c"]
print("True" if "a" in x else "False")
True
x = [1, 2, 3]
print("True" if 1 in x else "False")
True
- ABC006 A - 世界のFizzBuzz
- ABC049 A - 居合を終え、青い絵を覆う / UOIAUAI
- ABC073 A - September 9
- ABC109 A - ABC333
- ABC114 A - 753
- ABC162 A - Lucky 7
- ABC171 A - αlphabet
- ABC248 A - Lacked Number
- ABC029 B - カキ
- ABC089 B - Hina Arare
- ABC103 B - String Rotation
- ABC122 B - ATCoder
- ABC212 B - Weak Password
- ABC230 B - Triple Metre
- ABC033 C - 数式の書き換え
- ABC170 C - Forbidden List
- ABC186 C - Unlucky 7
- ABC244 D - Swap Hats
- AGC003 A - Wanna go back home
- AGC003 A - Wanna go back home
- CODE FESTIVAL 2017 qual C A - Can you get AC?
- MUJIN プログラミングチャレンジ Programming Challenge A - MUJIN
- Indeedなう(予選B) B - 高橋くんと文字列操作
複数の条件式
x = 1
y = 1
z = 1
print("True" if x == y == z else "False")
True
a = 1
b = 2
c = 3
d = 4
print("True" if a < b < c < d else "False")
True
- ABC061 A - Between Two Integers
- ABC079 A - Good Integer
- ABC094 A - Cats and Dogs
- ABC131 A - Security
- ABC144 A - 9x9
- ABC191 A - Vanishing Pitch
- ABC208 A - Rolling Dice
- ABC219 A - AtCoder Quiz 2
- ABC228 A - On and Off
- ABC237 A - Not Overflow
- CODE FESTIVAL 2016 qual C A - CF
3.2 繰り返し文
for
for i in range(5):
print(i)
0
1
2
3
4
for i in range(2, 5):
print(i)
2
3
4
for i in range(2, 5, 2):
print(i)
2
4
x = ["a", "b", "c"]
for i in x:
print(i)
a
b
c
X = ["a", "b", "c"]
Y = [1, 2, 3]
for x, y in zip(X, Y):
print(x, y)
a 1
b 2
c 3
- ABC241 A - Digit Machine
- ABC248 A - Lacked Number
- ABC137 B - One Clue
- ABC142 B - Roller Coaster
- ABC162 B - FizzBuzz Sum
- ABC181 B - Trapezoid Sum
- ABC184 B - Quizzes
- ABC200 B - 200th ABC-200
- ABC204 B - Nuts
- ABC214 B - How many?
- ABC224 B - Mongeness
- ABC245 B - Mex
- ABC170 C - Forbidden List
- ABC144 C - Walk on Multiplication Table
- ARC012 B - アキレスと亀
- CODE FESTIVAL 2014 予選B B - 歩く人
- CODE FESTIVAL 2015 予選A B - とても長い数列
- CODE FESTIVAL 2015 予選A B - とても長い数列
- 天下一プログラマーコンテスト2012 予選B A - 孫子算経
- 天下一プログラマーコンテスト2012 予選A A - 算盤の書
for/else
x = False
for i in range(5):
if x:
print("True")
break
else:
print("False")
False
- ABC165 A - We Love Golf
- ABC220 A - Find Multiple
- ABC144 B - 81
- ABC170 B - Crane and Turtle
- ABC190 B - Magic 3e
- ABC085 C - Otoshidama
- ABC136 C - Build Stairs
- ABC149 C - Next Prime
- ABC157 C - Guess The Number
- ABC158 C - Tax Increase
- ABC187 C - 1-SAT
- ABC131 D - Megalomania
- ARC010 A - 名刺交換
- ARC036 A - ぐっすり
- ARC014 B - あの日したしりとりの結果を僕達はまだ知らない。
- Indeedなう(予選B) B - 高橋くんと文字列操作
- Code Formula 2014 予選A A - 立方数
while
i = 0
while i < 5:
print(i)
i += 1
0
1
2
3
4
- ABC032 A - 高橋君と青木君の好きな数
- ABC045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)
- ABC065 B - Trained?
- ABC066 B - ss
- ABC081 B - Shift only
- ABC116 B - Collatz Problem
- ABC139 B - Power Socket
- ABC156 B - Digits
- ABC165 B - 1%
- ABC206 B - Savings
- ABC208 B - Factorial Yen Coin
- ABC245 B - Mex
- ABC248 B - Slimes
- ABC144 C - Walk on Multiplication Table
- ABC149 C - Next Prime
- ABC188 C - ABC Tournament
- ABC0193 C - Unexpressed
- ABC196 C - Doubled
- ABC153 D - Caracal vs Monster
- ARC106 A - 106
- ARC119 A - 119 × 2^23 + 1
- AGC014 A - Cookie Exchanges
- HHKB プログラミングコンテスト 2020 C - Neq Min
- M-SOLUTIONS プロコンオープン 2020 B - Magic 2
- 天下一プログラマーコンテスト2015予選B A - 天下一プログラマーコンテスト1998
- CODE FESTIVAL 2014 予選B B - 歩く人
- 天下一プログラマーコンテスト2013予選A A - 天下一株式会社採用情報
第4章 組み込み型観点
4.1 int
- 数値型
- 整数型におけるビット単位演算
- 整数型における追加のメソッド
- int():整数を返す
print(int(2.9))
2
print(int(3.0))
3
print(int(3.1))
3
print(int(-2.9))
-2
print(int(-3.0))
-3
print(int(-3.1))
-3
- ABC206 A - Maxi-Buying
- ABC226 A - Round decimals
- ABC232 A - QQ solver
- ABC235 A - Rotate
- ABC039 B - エージェント高橋君
- ABC077 B - Around Square
- ABC165 B - 1%
10進数への変換
- int(x,base=10):整数を返す
2進数⇒10進数
print(int("10", 2))
2
8進数⇒10進数
print(int("10", 8))
8
16進数⇒10進数
print(int("10", 16))
16
bit_length
- int.bit_length():整数を符号と先頭の0は除いて二進法で表すために必要なビットの数を返す
N = 10
print(N.bit_length())
4
4.2 float
- 数値型
- 浮動小数点数に対する追加のメソッド
- float():浮動小数点数を返す
print(float(1))
1.0
print(1+0.0)
1.0
print(5e10)
50000000000.0
print(1.1e-3)
0.0011
整数判定
-
float.is_integer():浮動小数点数が整数値なら
True
を、そうでなければFalse
を返す
x = 1.0
print(x.is_integer())
True
x = 1.1
print(x.is_integer())
False
有効桁数
- ABC117 A - Entrance Examination
- ABC142 A - Odds of Oddness
- ABC189 B - Alcoholic
- Donutsプロコンチャレンジ2015 A - ドーナツの体積
4.3 str
- テキストシーケンス型
- str:イミュータブル(変更不可能)なシーケンス
- 文字列メソッド
- str():文字列を返す
print(str(1))
1
文字列の連結
print("foo"+"bar")
foobar
x = "Fizz"
y = "Buzz"
print(x+y)
FizzBuzz
- ABC010 A - ハンドルネーム
- ABC029 A - 複数形
- ABC068 A - ABCxxx
- ABC090 A - Diagonal String
- ABC149 A - Strings
- ABC179 A - Plural Form
- ABC216 A - Signed Difficulty
- ABC247 A - Move Right
- ABC168 B - ... (Triple Dots)
- ABC200 B - 200th ABC-200
文字列の繰り返し
print("HelloWorld!"*2)
HelloWorld!HelloWorld!
x = "1"
print(x*5)
11111
- ABC115 A - Christmas Eve Eve Eve
- ABC197 A - Rotate
- ABC020 B - 足し算
- ABC152 B - Comparing Strings
- ABC154 B - I miss you...
- ABC196 C - Doubled
- ACL Beginner Contest A - Repeat ACL
- CODE FESTIVAL 2015 予選B A - ダブル文字列
文字列の参照
x = "abc"
print(x[0], x[1], x[2])
a b c
x = "abc"
print(x[-1], x[-2], x[-3])
c b a
- ABC025 A - 25個の文字列
- ABC038 A - お茶
- ABC041 A - 添字
- ABC048 A - AtCoder *** Contest
- ABC059 A - Three-letter acronym
- ABC060 A - Shiritori
- ABC060 A - Shiritori
- ABC062 A - Grouping
- ABC070 A - Palindromic Number
- ABC079 A - Good Integer
- ABC090 A - Diagonal String
- ABC131 A - Security
- ABC139 A - Tenki
- ABC160 A - Coffee
- ABC168 A - ∴ (Therefore)
- ABC189 A - Slot
- ABC218 A - Weather Forecast
- ABC232 A - QQ solver
- ABC236 A - chukodai
- ABC244 A - Last Letter
- ABC069 B - i18n
- ABC172 B - Minor Change
- ABC218 B - qwerty
- ABC221 B - typo
- CODE FESTIVAL 2014 予選A B - とても長い文字列
文字列の比較
x = "Hello"
y = "Hello"
print("True" if x == y else "False")
True
x = "Hello"
y = "Good"
print("True" if x == y else "False")
False
x = "a"
y = "b"
print("x < y" if x < y else "x > y")
x < y
x = "b"
y = "a"
print("x < y" if x < y else "x > y")
x > y
- ABC038 A - お茶
- ABC056 A - HonestOrDishonest
- ABC060 A - Shiritori
- ABC070 A - Palindromic Number
- ABC078 A - HEX
- ABC079 A - Good Integer
- ABC119 A - Still TBD
- ABC139 A - Tenki
- ABC215 A - Your First Judge
- ABC217 A - Lexicographic Order
- ABC082 B - Two Anagrams
- ABC147 B - Palindrome-philia
- ABC150 B - Count ABC
文字列の逆順
x = "Hello World!"
print(x[::-1])
!dlroW olleH
- ABC012 A - スワップ
- ABC070 A - Palindromic Number
- ABC077 A - Rotation
- ABC090 B - Palindromic Numbers
- ABC229 B - Hard Calculation
- ARC003 B - さかさま辞書
- CODE FESTIVAL 2017 qual B A - XXFESTIVAL
文字列の出現回数
- str.count():文字列の出現回数
- 共通のシーケンス演算
x = "abbccc"
print(x.count("c"))
3
x = "abbccc"
print(x.count("d"))
0
x = "123435"
print(x.count("3"))
2
- ABC081 A - Placing Marbles
- ABC095 A - Something on It
- ABC101 A - Eating Symbols Easy
- ABC162 A - Lucky 7
- ABC175 A - Rainy Season
- ABC028 B - 文字数カウント
- ABC044 B - 美しい文字列 / Beautiful Strings
- ABC084 B - Postal Code
- ABC150 B - Count ABC
- ABC124 C - Coloring Colorfully
- ARC001 A - センター採点
- CADDi 2018 for Beginners A - 12/22
- ZONeエナジー プログラミングコンテスト “HELLO SPACE” A - UFO襲来
文字列の置換
- str.replace():文字列の置換
x = "abcabcabc"
print(x.replace("b", "p"))
apcapcapc
x = "abcabcabc"
print(x.replace("b", "p", 2))
apcapcabc
- ABC017 A - プロコン
- ABC027 A - 長方形
- ABC064 A - RGB Cards
- ABC085 A - Already 2018
- ABC105 A - AtCoder Crackers
- ABC107 A - Train
- ABC109 A - ABC333
- ABC111 A - AtCoder Beginner Contest 999
- ABC117 A - Entrance Examination
- ABC232 A - QQ solver
- ABC017 B - choku語
- ABC020 B - 足し算
- ABC041 B - 直方体
- ABC104 B - AcCepted
- ABC202 B - 180°
- ARC019 A - お買い物クライシス
- ARC045 A - スペース高橋君
- ARC136 A - A ↔ BB
- ARC202 B - 180°
- 天下一プログラマーコンテスト2014予選B A - HAGIXILE
- Code Formula 2014 予選A B - ボウリングゲーム
- CODE FESTIVAL 2015 予選A A - CODE FESTIVAL 2015
- CODE FESTIVAL 2017 qual B A - XXFESTIVAL
- NOMURA プログラミングコンテスト 2020 B - Postdocs
文字列のスライス
x = "012345"
print(x[1:4])
123
x = "012345"
print(x[1:4:2])
13
x = "012345"
print(x[:3])
012
x = "012345"
print(x[3:])
345
x = "012345"
print(x[:-1])
01234
x = "012345"
print(x[-1:])
5
x = "012345"
print(x[::2])
024
x = "012345"
print(x[1::2])
135
x = "012345"
print(x[:-1:2])
024
x = "012345"
print(x[::-1])
543210
x = "012345"
print(x[::-2])
531
- ABC064 A - RGB Cards
- ABC085 A - Already 2018
- ABC167 A - Registration
- ABC197 A - Rotate
- ABC224 A - Tires
- ABC235 A - Rotate
- ABC236 A - chukodai
- ABC247 A - Move Right
- ABC011 B - 名前の確認
- ABC032 B - 高橋君とパスワード
- ABC072 B - OddString
- ABC098 B - Cut and Count
- ABC114 B - 754
- ABC141 B - Tap Dance
- ABC145 B - Echo
- ABC150 B - Count ABC
- ABC159 B - String Palindrome
- ABC168 B - ... (Triple Dots)
- ABC233 B - A Reverse
- ABC122 C - GeT AC
文字列の探索
- str.index():文字列の探索
x = "abcabc"
print(x.index("c"))
2
x = "abcabc"
print(x.index("bc"))
1
x = "abcabc"
print(x.index("z"))
ValueError: substring not found
文字列のユニーク化
x = "abcabc"
print(set(x))
{'a', 'c', 'b'}
- ABC033 A - 暗証番号
- ABC093 A - abc of ABC
- ABC132 A - Fifty-Fifty
- ABC158 A - Station and Bus
- ABC189 A - Slot
- ABC063 B - Varied
文字列のコピー
x = "Hello World!"
y = x[:5]
print(y)
Hello
x = "Hello World!"
y = x[:-1]
print(y)
Hello World
- ABC018 B - 文字列の反転
- ABC043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit)
- ABC066 B - ss
- ABC198 B - Palindrome with leading zeros
文字列の判定
-
str.isdecimal():文字列中の全ての文字が十進数字で、かつ 1 文字以上あるなら
True
を、そうでなければFalse
を返す -
str.isdigit():文字列中の全ての文字が数字で、かつ 1 文字以上あるなら
True
を、そうでなければFalse
を返す -
str.isnumeric():文字列中の全ての文字が数を表す文字で、かつ 1 文字以上あるなら
True
を、そうでなければFalse
を返す -
str.isalpha():文字列中の全ての文字が英字で、かつ 1 文字以上あるなら
True
を、そうでなければFalse
を返す -
str.isalnum():文字列中の全ての文字が英数字で、かつ 1 文字以上あるなら
True
を、そうでなければFalse
を返す
x = "1234567890"
print(x.isdecimal())
True
x = "10"
print(x.isdigit())
True
x = "一二三四五六七八九〇壱億参阡萬"
print(x.isnumeric())
True
x = "abcあいうアイウ漢字"
print(x.isalpha())
True
x = "abc100"
print(x.isalnum())
True
- ABC078 A - HEX
- ABC071 B - Not Found
- ABC084 B - Postal Code
- ABC090 B - Palindromic Numbers
- ARC052 A - 何期生?
文字列の検索
- str.find() / str.rfind() :文字列の検索
x = "abcabcabc"
print(x.find("b"))
1
x = "abcabcabc"
print(x.find("b", 3, 9))
4
x = "abcabcabc"
print(x.find("z"))
-1
x = "abcabcabc"
print(x.rfind("b"))
7
x = "abcabcabc"
print(x.rfind("b", 0, 6))
4
x = "abcabcabc"
print(x.rfind("z"))
-1
- ABC053 B - A to Z String
- ARC210 B - Bouzu Mekuri
- ABC039 C - ピアニスト高橋君
- CODE FESTIVAL 2016 qual C A - CF
- Indeedなう(予選B) B - 高橋くんと文字列操作
大文字小文字変換
- str.upper():すべての文字列を大文字に変換する
- str.lower():すべての文字列を小文字に変換する
- str.capitalize():文字列の先頭文字を大文字に変換する
- str.title():各単語の先頭文字を大文字に変換する
x = "this is a pen."
print(x.upper())
THIS IS A PEN.
x = "THIS IS A PEN."
print(x.lower())
this is a pen.
x = "this is a pen."
print(x.capitalize())
This is a pen.
x = "this is a pen."
print(x.title())
This Is A Pen.
- ABC059 A - Three-letter acronym
- ABC011 B - 名前の確認
- ABC249 B - Perfect String
- HHKB プログラミングコンテスト 2020 A - Keyboard
大文字小文字判定
- str.isupper():大文字判定
- str.islower():小文字判定
x = "ABC"
print(x.isupper())
True
x = "abc"
print(x.islower())
True
文字列の変換
- str.maketrans():変換テーブルを作成する
- str.translate():変換テーブルに基づいてマッピングする
x = "this is a pen."
print(x.translate(str.maketrans({"t": "T", " ": None, ".": "!"})))
Thisisapen!
x = "bcad"
print(x.translate(str.maketrans("abcd", "1234")))
2314
文字列のエンコード/デコード
- str.encode():文字列のエンコードされたバージョンをバイト列オブジェクトとして返す
- bytes.decode():与えられたバイト列からデコードされた文字列を返す
x = "abcd"
print(x.encode())
print(bytes(i+1 for i in x.encode()).decode())
b'abcd'
bcde
文字列のゼロ埋め
- str.zfill():左詰めした文字列のコピーを返す
N = "10"
print(N.zfill(4))
0010
f文字列
4.4 list
- シーケンス型
- list:ミュータブル(変更可能)なシーケンス
- ミュータブルなシーケンス型
要素の参照
x = ["a", "b", "c"]
print(x[0], x[1], x[2])
a b c
x = ["a", "b", "c"]
print(x[-1], x[-2], x[-3])
c b a
要素の追加
- list.append():要素の追加
- ミュータブルなシーケンス型
x = ["a", "b", "c"]
x.append("d")
print(x)
['a', 'b', 'c', 'd']
x = [0, 1, 2]
x.append(3)
print(x)
[0, 1, 2, 3]
x = ["a", "b", "c"]
x.append(["d", "e"])
print(x)
['a', 'b', 'c', ['d', 'e']]
要素の拡張
- list.extend():要素の拡張
- ミュータブルなシーケンス型
x = ["a", "b", "c"]
x.extend(["d", "e"])
print(x)
['a', 'b', 'c', 'd', 'e']
要素の挿入
- list.insert():要素の挿入
- ミュータブルなシーケンス型
x = ["a", "b", "c"]
x.insert(1, "z")
print(x)
['a', 'z', 'b', 'c']
x = ["a", "b", "c"]
x.insert(1, ["x", "y"])
print(x)
['a', ['x', 'y'], 'b', 'c']
要素の探索
- list.index():要素の探索
- 共通のシーケンス演算
x = ["a", "b", "c", "d", "e", "f"]
print(x.index("c"))
2
x = ["a", "b", "c", "d", "c", "c"]
print(x.index("c"))
2
x = [1, 2, 3, 4, 5]
print(x.index(3))
2
x = ["a", "b", "c", "d", "c", "c"]
print(x.index("z"))
ValueError: 'z' is not in list
- ABC013 A - A
- ABC018 A - 豆まき
- ABC141 A - Weather Prediction
- ABC146 A - Can't Wait for Holiday
- ABC151 A - Next Alphabet
- ABC170 A - Five Variables
- ABC033 B - 町の合併
- ABC113 B - Palace
- ARC210 B - Bouzu Mekuri
- ABC213 B - Booby Prize
- ARC003 A - GPA計算
- ARC053 B - A to Z String
- ARC053 B - A to Z String
- CODE FESTIVAL 2015 予選B B - 採点
要素の取り出し
- list.pop():要素の取り出し
- ミュータブルなシーケンス型
x = ["a", "b", "c", "d", "e", "f"]
print(x.pop(1))
print(x)
b
['a', 'c', 'd', 'e', 'f']
x = [1, 2, 3, 4, 5]
print(x.pop(3))
print(x)
4
[1, 2, 3, 5]
x = [1, 2, 3, 4, 5]
print(x.pop())
print(x)
5
[1, 2, 3, 4]
x = []
print(x.pop())
IndexError: pop from empty list
- ABC045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)
- ABC066 B - ss
- ABC244 C - Yamanote Line Game
要素の取り除き
- list.remove():要素の取り除き
- ミュータブルなシーケンス型
x = ["a", "b", "c", "d", "e", "f"]
x.remove("d")
print(x)
['a', 'b', 'c', 'e', 'f']
x = ["a", "a", "b", "b", "c", "c"]
x.remove("b")
print(x)
['a', 'a', 'b', 'c', 'c']
x = ["a", "a", "b", "b", "c", "c"]
x.remove("z")
print(x)
ValueError: list.remove(x): x not in list
要素の削除
- del():要素の削除
- ミュータブルなシーケンス型
x = ["a", "b", "c", "d", "e", "f"]
del x[1]
print(x)
['a', 'c', 'd', 'e', 'f']
x = ["a", "b", "c", "d", "e", "f"]
del x[-1]
print(x)
['a', 'b', 'c', 'd', 'e']
x = ["a", "b", "c", "d", "e", "f"]
del x[2:4]
print(x)
['a', 'b', 'e', 'f']
x = ["a", "b", "c", "d", "e", "f"]
del x[:]
print(x)
[]
要素の出現回数
x = ["a", "b", "b", "c", "c", "c"]
print(x.count("c"))
3
x = ["a", "b", "b", "c", "c", "c"]
print(x.count("d"))
0
x = [1, 2, 3, 4, 3, 5]
print(x.count(3))
2
- ABC042 A - 和風いろはちゃんイージー / Iroha and Haiku (ABC Edition)
- ABC132 A - Fifty-Fifty
- ABC015 B - 高橋くんの集計
- ABC091 B - Two Colors Card Game
- ABC166 B - Trick or Treat
- ABC241 B - Pasta
- ARC001 A - センター採点
要素の結合
- str.join():要素の結合
x = ["a", "b", "c", "d", "e"]
print("".join(x))
abcde
x = ["a", "b", "c", "d", "e"]
print(",".join(x))
a,b,c,d,e
x = ["a", "b", "c", "d", "e"]
print(" ".join(x))
a b c d e
- ABC111 A - AtCoder Beginner Contest 999
- ABC042 B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)
- ABC058 B - ∵∴∵
- ABC148 B - Strings with the Same Length
- ABC219 B - Maritozzo
- ABC242 B - Minimize Ordering
- ABC192 C - Kaprekar Number
- ARC045 A - スペース高橋君
- Code Formula 2014 予選A B - ボウリングゲーム
- 天下一プログラマーコンテスト2014予選A A - 天下一序数
- 天下一プログラマーコンテスト2012 予選A B - 分類たん
要素のユニーク化
x = [1, 2, 3, 2, 1, 3]
print(list(set(x)))
[1, 2, 3]
x = ["b", "a", "c", "a", "b"]
print(list(set(x)))
['b', 'c', 'a']
x = [[1, 0], [0, 0], [1, 1], [1, 0], [0, 1], [0, 0]]
print(list(map(list, set(map(tuple, x)))))
[[1, 0], [0, 1], [1, 1], [0, 0]]
- ABC046 A - AtCoDeerくんとペンキ / AtCoDeer and Paint Cans
- ABC152 A - AC or WA
- ABC155 A - Poor
- ABC009 B - 心配性な富豪、ファミリーレストランに行く。
- ABC032 B - 高橋君とパスワード
- ABC085 B - Kagami Mochi
- ABC205 B - Permutation Check
要素のスライス
x = ["0", "1", "2", "3", "4", "5"]
print(x[1:4])
['1', '2', '3']
x = ["0", "1", "2", "3", "4", "5"]
print(x[1:4:2])
['1', '3']
x = ["0", "1", "2", "3", "4", "5"]
print(x[:3])
['0', '1', '2']
x = ["0", "1", "2", "3", "4", "5"]
print(x[3:])
['3', '4', '5']
x = ["0", "1", "2", "3", "4", "5"]
print(x[:-1])
['0', '1', '2', '3', '4']
x = ["0", "1", "2", "3", "4", "5"]
print(x[-1:])
['5']
x = ["0", "1", "2", "3", "4", "5"]
print(x[::2])
['0', '2', '4']
x = ["0", "1", "2", "3", "4", "5"]
print(x[1::2])
['1', '3', '5']
x = ["0", "1", "2", "3", "4", "5"]
print(x[:-1:2])
['0', '2', '4']
x = ["0", "1", "2", "3", "4", "5"]
print(x[::-1])
['5', '4', '3', '2', '1', '0']
x = ["0", "1", "2", "3", "4", "5"]
print(x[::-2])
['5', '3', '1']
- ABC066 A - ringring
- ABC026 B - N重丸
- ABC066 B - ss
- ABC067 B - Snake Toy
- ABC088 B - Card Game for Two
- ABC093 B - Small and Large Integers
- ABC115 B - Christmas Eve Eve
- ABC117 B - Polygon
- ABC129 B - Balance
- ABC153 C - Fennec vs Monster
- ARC005 A - 大好き高橋君
- ARC049 A - "強調"
- AGC001 A - BBQ Easy
- CODE FESTIVAL 2017 qual B A - XXFESTIVAL
- CODE FESTIVAL 2017 qual A A - Snuke's favorite YAKINIKU
- CODE FESTIVAL 2016 qual A A - CODEFESTIVAL 2016
- CODE FESTIVAL 2015 予選A A - CODE FESTIVAL 2015
- SoundHound Inc. Programming Contest 2018 -Masters Tournament- B - Acrostic
- Indeedなう(予選B) B - 高橋くんと文字列操作
- CODE FESTIVAL 2014 決勝 B - 暗算ゲーム
- 東京海上日動 プログラミングコンテスト2020 A - Nickname
- Code Formula 2014 予選B B - 11の倍数
リスト内包表記
x = [i for i in range(10)]
print(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
x = [i for i in range(10) if i % 2 == 0]
print(x)
[0, 2, 4, 6, 8]
x = [i//2 for i in range(10) if i % 2 == 0]
print(x)
[0, 1, 2, 3, 4]
x = [2, 4, 6, 8, 10]
x = [i//2 for i in x]
print(x)
[1, 2, 3, 4, 5]
x = [1*i + 10*j + 100*k for k in range(2) for j in range(3) for i in range(4)]
print(x)
[0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 100, 101, 102, 103, 110, 111, 112, 113, 120, 121, 122, 123]
- ABC051 B - Sum of Three Integers
- ABC081 B - Shift only
- ABC087 B - Coins
- ABC105 B - Cakes and Donuts
- ABC162 B - FizzBuzz Sum
- ABC191 B - Remove It
要素のソート
x = [[0, 1], [1, 1], [1, 0], [0, 0]]
x.sort(key=lambda x: (x[0], x[1]))
for i in x:
print(i)
[0, 0]
[0, 1]
[1, 0]
[1, 1]
x = [[0, 1], [1, 1], [1, 0], [0, 0]]
x.sort(key=lambda x: (x[0], -x[1]))
for i in x:
print(i)
[0, 1]
[0, 0]
[1, 1]
[1, 0]
x = [[0, 1], [1, 1], [1, 0], [0, 0]]
x.sort(key=lambda x: (-x[0], -x[1]))
for i in x:
print(i)
[1, 1]
[1, 0]
[0, 1]
[0, 0]
x = [[0, 1], [1, 1], [1, 0], [0, 0]]
x.sort(key=lambda x: (x[0], x[1]), reverse=True)
for i in x:
print(i)
[1, 1]
[1, 0]
[0, 1]
[0, 0]
4.5 tuple
要素の参照
x = ("Hello", "World", 1)
print(x)
print(x[0])
('Hello', 'World', 1)
Hello
4.6 dict
要素の参照
x = {"a": 1, "b": 2, "c": 3}
print(x["a"])
1
x = dict(a=1, b=2, c=3)
print(x["a"])
1
- ABC141 A - Weather Prediction
- ABC146 A - Can't Wait for Holiday
- ABC154 A - Remaining Balls
- ABC045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)
- ABC119 B - Digital Gifts
- ABC036 C - 座圧
- ARC012 A - 週末
- 第6回 ドワンゴからの挑戦状 予選 A - Falling Asleep
要素の集計
keys = ["a", "b", "c", "b", "a", "b"]
dictionary = {}
for key in keys:
if key in dictionary:
dictionary[key] += 1
else:
dictionary[key] = 1
print(dictionary)
{'a': 2, 'b': 3, 'c': 1}
4.7 set
和
A \cup B
print({"a", "b", "c"} | {"c", "d", "e"})
{'a', 'b', 'd', 'e', 'c'}
差
A - B
print({"a", "b", "c"} - {"c", "d", "e"})
{'a', 'b'}
- ABC148 A - Round One
- ABC248 A - Lacked Number
- ABC071 B - Not Found
- ABC217 B - AtCoder Quiz
- ABC245 B - Mex
積
A \cap B
print({"a", "b", "c"} & {"c", "d", "e"})
{'c'}
- ABC098 B - Cut and Count
- ABC118 B - Foods Loved by Everyone
- ABC243 B - Hit and Blow
- ABC079 C - Cat Snuke and a Voyage
- ABC187 C - 1-SAT
対称差
A ⊕ B
print({"a", "b", "c"} ^ {"c", "d", "e"})
{'a', 'b', 'e', 'd'}
- ABC027 A - 長方形
- ABC075 A - One out of Three
- ABC246 A - Four Points
- ABC071 B - Not Found
- ABC217 B - AtCoder Quiz
- ABC236 B - Who is missing?
- ABC073 C - Write and Erase
- 第二回日本最強プログラマー学生選手権 B - Xor of Sequences
部分集合
A \subseteq B
print({"a", "b"} <= {"a", "b", "c"})
True
print({"a", "z"} <= {"a", "b", "c"})
False
文字の集合
import string
x = string.ascii_lowercase
print(x)
abcdefghijklmnopqrstuvwxyz
x = sorted(map(chr, range(97, 123)))
print(x)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
x = sorted(map(chr, range(65, 91)))
print(x)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
4.8 range
r = range(2, 10)
print(r)
range(2, 10)
r = range(2, 10)
print(r[:3])
range(2, 5)
r = range(2, 10)
print(set(r[:3]))
{2, 3, 4}
r = range(2, 10)
print(r[3:])
range(5, 10)
r = range(2, 10)
print(set(r[3:]))
{5, 6, 7, 8, 9}
r = range(2, 10)
print(r[-3:])
range(7, 10)
r = range(2, 10)
print(set(r[-3:]))
{8, 9, 7}
r = range(2, 10)
print(r[:-3])
range(2, 7)
r = range(2, 10)
print(set(r[:-3]))
{2, 3, 4, 5, 6}
第5章 組み込み関数観点
5.1 abs
- abs():絶対値を返す
x = -1
print(abs(x))
1
x = -1.1
print(abs(x))
1.1
- ABC071 A - Meal Delivery
- ABC097 A - Colorful Transceivers
- ABC188 A - Three-Point Shot
- ABC056 B - NarrowRectanglesEasy
- ABC114 B - 754
- 第5回 ドワンゴからの挑戦状 予選 A - Thumbnail
- Indeedなう(予選B) A - 高橋くんとマンハッタン
5.2 all
-
all():iterable の全ての要素が真ならば(もしくは iterable が空ならば)
True
、そうでない場合はFalse
を返す
print(all([True, True]))
True
print(all([True, False]))
False
print(all([False, False]))
False
- ABC131 A - Security
- ABC044 B - 美しい文字列 / Beautiful Strings
- ABC081 B - Shift only
- ABC109 B - Shiritori
- ABC155 B - Papers, Please
5.3 any
-
any():iterable のいずれかの要素が真ならば
True
、空ならFalse
を返す
print(any([True, True]))
True
print(any([True, False]))
True
print(any([False, False]))
False
5.4 bin/oct/hex
10進数⇒2進数
print(bin(2))
0b10
10進数⇒8進数
print(oct(8))
0o10
10進数⇒16進数
print(hex(16))
0x10
10進数⇒2進数
print(0b10)
2
10進数⇒8進数表示
print(0o10)
8
10進数⇒16進数表示
print(0x10)
16
2進数⇒10進数
print(int("10", 2))
2
8進数⇒10進数
print(int("10", 8))
8
16進数⇒10進数
print(int("10", 16))
16
5.5 divmod
- divmod():複素数でない2つの数を引数として取り、除算を行ったときの商と剰余からなる対を返す
a, b = divmod(5, 2)
print(a, b)
2 1
5.6 enumerate
- enumerate():カウントと iterable 上の iteration によって得られた値を含むタプルを返す
x = ["a", "b", "c"]
for number, alphabet in enumerate(x):
print(number, alphabet)
0 a
1 b
2 c
5.7 eval
print(eval("1+2"))
3
- ABC016 A - 12月6日
- ABC017 A - プロコン
- ABC035 A - テレビ
- ABC050 A - Addition and Subtraction Easy
- ABC063 A - Restricted
- ABC232 A - QQ solver
- ABC041 B - 直方体
- ABC073 B - Theater
- ARC018 A - BMI
5.8 len
- len():オブジェクトの長さ(要素の数)を返す
print(len("aiueo"))
5
print(max(["abc", "d", "ef", "ghij"], key=len))
ghij
print(min(["abc", "d", "ef", "ghij"], key=len))
d
- ABC015 A - 高橋くんの研修
- ABC033 A - 暗証番号
- ABC046 A - AtCoDeerくんとペンキ / AtCoDeer and Paint Cans
- ABC093 A - abc of ABC
- ABC132 A - Fifty-Fifty
- ABC155 A - Poor
- ABC158 A - Station and Bus
- ABC189 A - Slot
- ABC216 B - Same Name
- ABC225 A - Distinct Strings
- ABC063 B - Varied
- ABC069 B - i18n
- ABC154 B - I miss you...
- ABC205 B - Permutation Check
- ABC211 B - Cycle Hit
- ABC212 B - Weak Password
- ABC226 B - Counting Arrays
- ABC240 B - Count Distinct Integers
- ABC154 C - Distinct or Not
- ABC164 C - gacha
- Indeedなう(予選A) - 掛け算の筆算
5.9 map
- map():function の結果を返しながら、全ての要素に適用する iterator を返す
1 2
x, y = map(float, input().split())
print(x, y)
1.0 2.0
-1 -2
x, y = map(abs, map(int, input().split()))
print(x, y)
1 2
x = [[1, 6, 8], [3, 5, 7], [2, 4, 9]]
a, b, c = map(max, zip(*x))
print(a, b, c)
3 6 9
x = list(map(str, range(1, 5)))
print(x)
['1', '2', '3', '4']
- ABC110 C - String Transformation
- ABC192 C - Kaprekar Number
- ARC018 A - BMI
- ARC013 B - 引越しできるかな?
- ARC015 B - 真冬日?真夏日?
- 天下一プログラマーコンテスト2014予選A A - 天下一序数
5.10 max
- max():iterable の中で最大の要素、または2つ以上の引数の中で最大のものを返す
print(max(1, 2))
2
print(max(2, 1, 3))
3
print(max([2, 1, 3]))
3
print(max(["b", "a", "c", "d"]))
d
print(max(["ab", "aa", "ca", "bd"]))
ca
print(max(["a", "bcde", "fg", "hij"], key=len))
bcde
x = ["a", "b", "c", "b"]
print(max(x, key=x.count))
b
- ABC002 A - 正直者
- ABC015 A - 高橋くんの研修
- ABC037 A - 饅頭
- ABC044 A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)
- ABC052 A - Two Rectangles
- ABC072 A - Sandglass2
- ABC098 A - Add Sub Mul
- ABC100 A - Happy Birthday!
- ABC103 A - Task Scheduling Problem
- ABC124 A - Buttons
- ABC136 A - Transfer
- ABC137 A - +-x /
- ABC143 A - Curtain
- ABC144 A - 9x9
- ABC209 A - Counting
- ABC210 A - Cabbages
- ABC052 B - Increment Decrement
- ABC056 B - NarrowRectanglesEasy
- ABC064 B - Traveling AtCoDeer Problem
- ABC115 B - Christmas Eve Eve
- ABC117 B - Polygon
- ABC149 B - Greedy Takahashi
- ABC151 B - Achieve the Goal
- ABC178 B - Product Max
- ABC231 B - Election
- CODE FESTIVAL 2014 予選B A - あるピアニスト
5.11 min
- min():iterable の中で最小の要素、または2つ以上の引数の中で最小のものを返す
print(min(1, 2))
1
print(min(2, 1, 3))
1
print(min([2, 1, 3]))
1
print(min(["b", "a", "c", "d"]))
a
print(min(["ab", "aa", "ca", "bd"]))
aa
print(min(["a", "bcde", "fg", "hij"], key=len))
a
x = ["a", "b", "c", "b", "c", "c"]
print(min(x, key=x.count))
a
- ABC037 A - 饅頭
- ABC040 A - 赤赤赤赤青
- ABC066 A - ringring
- ABC080 A - Parking
- ABC092 A - Traveling Budget
- ABC103 A - Task Scheduling Problem
- ABC120 A - Favorite Sound
- ABC129 A - Airplane
- ABC133 A - T or T
- ABC185 A - ABC Preparation
- ABC207 A - Repression
- ABC210 A - Cabbages
- ABC005 B - おいしいたこ焼きの食べ方
- ABC013 B - 錠
- ABC064 B - Traveling AtCoDeer Problem
- ABC076 B - Addition and Multiplication
- ABC094 B - Toll Gates
- ABC113 B - Palace
- ABC131 B - Bite Eating
- ABC131 B - Bite Eating
- ABC152 B - Comparing Strings
- ABC158 B - Count Balls
- ABC167 B - Easy Linear Programming
- ABC193 B - Play Snuke
- ABC199 B - Intersection
- ABC095 C - Half and Half
- ABC140 C - Maximal Value
- CADDi 2018 for Beginners B - AtCoder Alloy
5.12 ord/chr
- ord():1 文字の Unicode 文字を表す文字列に対し、その文字の Unicode コードポイントを表す整数を返す
- chr():Unicode コードポイントが整数である文字を表す文字列を返す
print([chr(i) for i in range(97, 97+26)])
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
print([chr(i) for i in range(ord("a"),ord("z")+1)])
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
x = "abc"
[print(chr(i), end=" ") for i in range(ord("a"), ord("z")+1) if chr(i) in x]
a b c
- ABC013 A - A
- ABC151 A - Next Alphabet
- ABC171 A - αlphabet
- ABC151 A - Next Alphabet
- ABC146 B - ROT N
- ABC218 B - qwerty
- ABC232 B - Caesar Cipher
- ABC171 C - One Quadrillion and One Dalmatians
- CODE FESTIVAL 2016 Final A - Where's Snuke?
5.13 pow
- pow():べき乗を返す
print(pow(3, 2))
9
print(pow(3, 1000, 10**9+7))
56888193
- ABC134 A - Dodecagon
- ABC140 A - Password
- ABC145 A - Circle
- ABC172 A - Calc
- ABC199 A - Square Inequality
- ABC034 C - 経路
- ABC178 C - Ubiquity
5.14 sorted
- sorted():iterable の要素を並べ替えた新たなリストを返す
昇順
x = [2, 1, 3]
print(sorted(x))
[1, 2, 3]
降順
x = [2, 1, 3]
print(sorted(x)[::-1])
[3, 2, 1]
- ABC018 A - 豆まき
- ABC019 A - 高橋くんと年齢
- ABC047 A - キャンディーと2人の子供 / Fighting over Candies
- ABC066 A - ringring
- ABC103 A - Task Scheduling Problem
- ABC110 A - Maximize the Formula
- ABC201 A - Tiny Arithmetic Sequence
- ABC207 A - Repression
- ABC009 B - 心配性な富豪、ファミリーレストランに行く。
- ABC026 B - N重丸
- ABC046 B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)
- ABC064 B - Traveling AtCoDeer Problem
- ABC067 B - Snake Toy
- ABC082 B - Two Anagrams
- ABC102 B - Maximum Difference
- ABC117 B - Polygon
- ABC161 B - Popular Vote
- ABC213 B - Booby Prize
- ABC242 B - Minimize Ordering
- ABC113 C - ID
- ABC134 C - Exception Handling
- ABC153 C - Fennec vs Monster
- ARC042 A - 掲示板
- ARC105 A - Fourtune Cookies
5.15 split
x = "Hello,World"
print(*x.split(","))
Hello World
5.16 strip/rstrip/lstrip
x = "0012300"
print(x.strip("0"))
print(x.rstrip("0"))
print(x.lstrip("0"))
123
00123
12300
5.17 sum
- sum():合計を返す
x = [1, 2, 3]
print(sum(x))
6
- ABC063 A - Restricted
- ABC066 A - ringring
- ABC139 A - Tenki
- ABC147 A - Blackjack
- ABC202 A - Three Dice
- ABC207 A - Repression
- ABC015 B - 高橋くんの集計
- ABC029 B - カキ
- ABC051 B - Sum of Three Integers
- ABC067 B - Snake Toy
- ABC115 B - Christmas Eve Eve
- ABC117 B - Polygon
- ABC131 B - Bite Eating
- ABC142 B - Roller Coaster
- ABC147 B - Palindrome-philia
- ABC153 B - Common Raccoon vs Monster
- ABC163 B - Homework
- ABC171 B - Mix Juice
- ABC172 B - Minor Change
- ABC209 B - Can you buy them all?
- ABC222 B - Failing Grade
- ABC140 C - Maximal Value
- ABC143 C - Slimes
- 天下一プログラマーコンテスト2013予選A B - 天下一難易度設定
数字和
- 数字和:digit sum
- 数字和 - Wikipedia
x = 1234
print(sum(map(int, str(x))))
10
x = "1234"
print(sum(map(int, x)))
10
- ABC023 A - 加算王
- ABC187 A - Large Digits
- ABC248 A - Lacked Number
- ABC080 B - Harshad Number
- ABC083 B - Some Sums
- ABC101 B - Digit Sums
- ABC176 B - Multiple of 9
- CODE FESTIVAL 2014 決勝 B - 暗算ゲーム
- Code Formula 2014 予選B B - 11の倍数
5.18 zip
- zip():それぞれの iterable から要素を集めた iterator を作り、タプルを返す
X = [1, 2, 3]
Y = ["a", "b", "c"]
for x, y in zip(X, Y):
print(x, y)
1 a
2 b
3 c
x = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(x)
print(list(map(list, zip(*x))))
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
- ABC139 A - Tenki
- ABC058 B - ∵∴∵
- ABC121 B - Can you solve this?
- ABC147 B - Palindrome-philia
- ABC148 B - Strings with the Same Length
- ABC172 B - Minor Change
- ABC188 B - Orthogonality
- ABC243 B - Hit and Blow
- ABC157 C - Guess The Number
- ARC025 A - ゴールドラッシュ
- ARC013 B - 引越しできるかな?
- CODE FESTIVAL 2016 qual B A - Signboard
- 第6回 ドワンゴからの挑戦状 予選 A - Falling Asleep
第6章 モジュール観点
6.1 bisect
bisect_left / bisect_right
- bisect.bisect_left()
- bisect.bisect_right()
- bisect:配列二分法アルゴリズム
import bisect
x = [1, 3, 5, 7, 9]
print(bisect.bisect_left(x, 5))
# 2
"""
x = [1, 3, 5, 7, 9]
1 2 3 4 5
^
"""
print(bisect.bisect_right(x, 5))
# 3
"""
x = [1, 3, 5, 7, 9]
1 2 3 4 5
^
"""
print(bisect.bisect_left(x, 6))
# 3
"""
x = [1, 3, 5, 7, 9]
1 2 3 4 5
^
"""
print(bisect.bisect_right(x, 6))
# 3
"""
x = [1, 3, 5, 7, 9]
1 2 3 4 5
^
"""
x = [1, 1, 1, 3, 3, 3, 5, 5, 5]
print(bisect.bisect_left(x, 3))
# 3
"""
x = [1, 1, 1, 3, 3, 3, 5, 5, 5]
1 2 3 4 5 6 7 8 9
^
"""
print(bisect.bisect_right(x, 3))
# 6
"""
x = [1, 1, 1, 3, 3, 3, 5, 5, 5]
1 2 3 4 5 6 7 8 9
^
"""
print(bisect.bisect_left(x, 4))
# 6
"""
x = [1, 1, 1, 3, 3, 3, 5, 5, 5]
1 2 3 4 5 6 7 8 9
^
"""
print(bisect.bisect_right(x, 4))
# 6
"""
x = [1, 1, 1, 3, 3, 3, 5, 5, 5]
1 2 3 4 5 6 7 8 9
^
"""
- ABC094 B - Toll Gates
- ABC130 B - Bounding
- ABC036 C - 座圧
- ABC084 C - Snuke Festival
- ABC113 C - ID
- ABC212 C - Min Difference
- ABC119 D - Lazy Faith
6.2 calendar
- calendar:一般的なカレンダーに関する関数群
isleap
-
calendar.isleap():閏年なら
True
を、そうでなければFalse
を返す
import calendar
print(calendar.isleap(2020))
True
leapdays
- calendar.leapdays():範囲指定された期間の閏年の回数を返す
import calendar
print(calendar.leapdays(2020, 2025))
2
6.3 collections
- collections:コンテナデータ型
Counter
import collections
x = ["a", "a", "a", "a", "b", "c", "c"]
c = collections.Counter(x)
print(c)
# Counter({'a': 4, 'c': 2, 'b': 1})
print(type(c))
# <class 'collections.Counter'>
print(issubclass(type(c), dict))
# True
print(c.keys())
# dict_keys(['a', 'b', 'c'])
print(c.values())
# dict_values([4, 1, 2])
print(c.items())
# dict_items([('a', 4), ('b', 1), ('c', 2)])
print(c.most_common())
# [('a', 4), ('c', 2), ('b', 1)]
print(c.most_common()[0])
# ('a', 4)
print(c.most_common()[-1])
# ('b', 1)
print(c.most_common()[0][0])
# a
print(c.most_common()[0][1])
# 4
print(c.most_common()[::-1])
# [('b', 1), ('c', 2), ('a', 4)]
print(c.most_common(2))
# [('a', 4), ('c', 2)]
values, counts = zip(*c.most_common())
print(values)
# ('a', 'c', 'b')
print(counts)
# (4, 2, 1)
print(c["a"])
# 4
print(c["b"])
# 1
print(c["c"])
# 2
print(c["d"])
# 0
- ABC132 A - Fifty-Fifty
- ABC008 B - 投票
- ABC173 B - Judge Status Summary
- ABC231 B - Election
- ABC241 B - Pasta
- ABC071 C - 怪文書 / Dubious Document
- ABC073 C - Write and Erase
- ABC081 C - Not so Diverse
- ABC082 C - Good Sequence
- ABC103 C - ////
- ABC110 C - String Transformation
- ABC137 C - Green Bin
- ABC202 C - Made Up
- ABC206 C - Swappable
- ABC210 C - Colorful Candies
- ABC249 C - Just K
- ABC233 D - Count Interval
- ARC024 A - くつがくっつく
- ARC081 C - Make a Rectangle
- Indeedなう(予選A) B - Indeedなう!
- CODE FESTIVAL 2015 予選B B - 採点
- CODE FESTIVAL 2017 qual B B - Problem Set
deque
import collections
queue = collections.deque(["a", "b", "c"])
queue.append("d")
print(queue)
queue.popleft()
print(queue)
deque(['a', 'b', 'c', 'd'])
deque(['b', 'c', 'd'])
defaultdict
import collections
x = [("a", 1), ("b", 1), ("a", 2), ("c", 2)]
d = collections.defaultdict(list)
for key, value in x:
d[key].append(value)
print(d)
defaultdict(<class 'list'>, {'a': [1, 2], 'b': [1], 'c': [2]})
6.4 datetime
サンプルコード
実行結果
6.5 decimal
サンプルコード
実行結果
- ABC226 A - Round decimals
- ABC196 B - Round Down
- ABC169 C - Multiplication 3
- パナソニックプログラミングコンテスト2020 C - Sqrt Inequality
6.7 fractions
- fractions:有理数
gcd
サンプルコード
実行結果
6.6 functools
- functools:高階関数と呼び出し可能オブジェクトの操作
reduce
from functools import reduce
from operator import add
from operator import sub
from operator import mul
x = [20, 1, 2, 3, 4, 5]
print(reduce(add, x))
# 35(=20+1+2+3+4+5)
print(reduce(sub, x))
# 5(=20-1-2-3-4-5)
print(reduce(mul, x))
# 2300(=20*1*2*3*4*5)
# Lambda式に変換が可能
print(reduce(lambda a, b: a+b, x)) # 35
print(reduce(lambda a, b: a-b, x)) # 5
print(reduce(lambda a, b: a*b, x)) # 2400
6.8 heapq
- heapq:ヒープキューアルゴリズム
heappush / heappop
import heapq
hq = [2, -20, 5, 0, -1, 100, 27]
heapq.heappush(hq, -30)
print(hq)
heapq.heappop(hq)
print(hq)
[-30, 2, 5, -20, -1, 100, 27, 0]
[2, -20, 5, 0, -1, 100, 27]
nlargest / nsmallest
import heapq
hq = [2, -20, 5, 0, -1, 100, 27]
print(heapq.nlargest(3, hq))
print(heapq.nsmallest(3, hq))
[100, 27, 5]
[-20, -1, 0]
heapreplace
サンプルコード
実行結果
6.9 itertools
- itertools:効率的なループ実行のための iterator 生成関数
accumulate
サンプルコード
実行結果
combinations
_4 C _2 = \frac{_4 P _2}{2!} = 6通り
from itertools import combinations
x = ["a", "b", "c", "d"]
print(list(combinations(x, 2)))
print(len(list(combinations(x, 2))))
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]
6
from itertools import combinations
for a, b, c in combinations("MARCH", 3):
print(a, b, c)
M A R
M A C
M A H
M R C
M R H
M C H
A R C
A R H
A C H
R C H
combinations_with_replacement
from itertools import combinations_with_replacement
x = ["a", "b", "c", "d"]
print(list(combinations_with_replacement(x, 3)))
[('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'a', 'd'), ('a', 'b', 'b'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'c'), ('a', 'c', 'd'), ('a', 'd', 'd'), ('b', 'b', 'b'), ('b', 'b', 'c'), ('b', 'b', 'd'), ('b', 'c', 'c'), ('b', 'c', 'd'), ('b', 'd', 'd'), ('c', 'c', 'c'), ('c', 'c', 'd'), ('c', 'd', 'd'), ('d', 'd', 'd')]
from itertools import combinations_with_replacement
x = ["a", "b", "c", "d"]
print(len(list(combinations_with_replacement(x, 3))))
20
groupby
サンプルコード
実行結果
- ABC019 B - 高橋くんと文字列圧縮
- ABC063 C - 一次元リバーシ / 1D Reversi
- ABC143 C - Slimes
- AGC039 A - Connection and Disconnection
permutations
4! = 4 × 3 × 2 × 1 = 24通り
from itertools import permutations
x = ["a", "b", "c", "d", "e"]
print(list(permutations(x)))
print(len(list(permutations(x))))
[('a', 'b', 'c', 'd'), ('a', 'b', 'd', 'c'), ('a', 'c', 'b', 'd'), ('a', 'c', 'd', 'b'), ('a', 'd', 'b', 'c'), ('a', 'd', 'c', 'b'), ('b', 'a', 'c', 'd'), ('b', 'a', 'd', 'c'), ('b', 'c', 'a', 'd'), ('b', 'c', 'd', 'a'), ('b', 'd', 'a', 'c'), ('b', 'd', 'c', 'a'), ('c', 'a', 'b', 'd'), ('c', 'a', 'd', 'b'), ('c', 'b', 'a', 'd'), ('c', 'b', 'd', 'a'), ('c', 'd', 'a', 'b'), ('c', 'd', 'b', 'a'), ('d', 'a', 'b', 'c'), ('d', 'a', 'c', 'b'), ('d', 'b', 'a', 'c'), ('d', 'b', 'c', 'a'), ('d', 'c', 'a', 'b'), ('d', 'c', 'b', 'a')]
24
_4 P _2 = 4 \times 3 = 12通り
from itertools import permutations
x = ["a", "b", "c"]
print(list(permutations(x, 2)))
print(len(list(permutations(x, 2))))
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')]
12
- ABC225 A - Distinct Strings
- ABC123 B - Five Dishes
- ABC150 C - Count Order
- ABC0183 C - Travel
- ABC232 C - Graph Isomorphism
- ARC013 A - 梱包できるかな?
product
サンプルコード
実行結果
- ABC029 C - Brute-force Attack
- ABC114 C - 755
- ABC173 C - H and V
- ABC182 C - To 3
- ABC190 C - Bowls and Dishes
- エイシング プログラミング コンテスト 2020 C - XYZ Triplets
6.10 math
- math:数学関数
cos
サンプルコード
実行結果
factorial
サンプルコード
実行結果
floor
- 床関数(切り捨て):floor
- math.floor()
import math
print(math.floor(5/3))
1
import math
print(math.floor(6/3))
2
gcd
サンプルコード
実行結果
log
サンプルコード
実行結果
pi
import math
print(math.pi)
3.141592653589793
radians
サンプルコード
実行結果
sqrt
- 平方根:square root
- math.sqrt()
import math
print(math.sqrt(4))
2.0
6.11 numpy
- numpy:数値計算
argsort
サンプルコード
実行結果
argwhere
サンプルコード
実行結果
array
サンプルコード
実行結果
array
サンプルコード
実行結果
diff
サンプルコード
実行結果
norm
サンプルコード
実行結果
6.12 re
- re:正規表現操作(Regular Expression operations)
findall
- re.findall():string 中の pattern による重複しないマッチを文字列のリストとして返す
サンプルコード
実行結果
fullmatch
- re.fullmatch():string 全体が正規表現 pattern にマッチするなら、対応する マッチオブジェクト を返す
サンプルコード
実行結果
match
- re.match():string の先頭で0文字以上がこの正規表現とマッチするなら、対応する マッチオブジェクト を返す
サンプルコード
実行結果
- ABC023 B - 手芸王
- ABC104 B - AcCepted
- ABC049 C - 白昼夢 / Daydream
- ABC076 C - Dubious Document 2
- CODE FESTIVAL 2016 qual C A - CF
- CODE FESTIVAL 2017 Final A - AKIBA
search
- re.search():string を走査し、この正規表現がマッチを生じさせる最初の場所を探して、対応する マッチオブジェクト を返す
サンプルコード
実行結果
split
- re.split():string を pattern で分割し、リストを返す
サンプルコード
実行結果
sub
- re.sub():string を重複しない pattern を置換した文字列を返す
サンプルコード
実行結果
FF
6.13 sys
setrecursionlimit
サンプルコード
実行結果
第7章 データ構造観点
7.1 スタック
- スタック:Stack
stack = [3, 4, 5]
stack.append(6)
print(stack)
stack.pop()
print(stack)
[3, 4, 5, 6]
[3, 4, 5]
stack = ["a", "b", "c"]
stack.pop()
print(stack)
stack.append("d")
print(stack)
['a', 'b']
['a', 'b', 'd']
import queue
q = queue.LifoQueue()
x = [3, 4, 5]
for l in x:
q.put(l)
while not q.empty():
print(q.get())
5
4
3
- ABC043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit)
- ABC120 C - Unification
- ABC240 D - Strange Balls
- ABC243 D - Moves on Binary Tree
- CODE FESTIVAL 2017 qual B B - Problem Set
7.2 キュー
- キュー:Queue
queue = [3, 4, 5]
queue.append(6)
print(queue)
queue.pop(0)
print(queue)
[3, 4, 5, 6]
[4, 5, 6]
queue = ["a", "b", "c"]
queue.pop(0)
print(queue)
queue.append("d")
print(queue)
['b', 'c']
['b', 'c', 'd']
from collections import deque
queue = deque(["a", "b", "c"])
queue.append("d")
print(queue)
queue.popleft()
print(queue)
deque(['a', 'b', 'c', 'd'])
deque(['b', 'c', 'd'])
import queue
q = queue.Queue()
x = [3, 4, 5]
for l in x:
q.put(l)
while not q.empty():
print(q.get())
3
4
5
- ABC045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)
- ABC066 C - pushpush
- ABC188 C - ABC Tournament
- ABC158 D - String Formation
- ABC161 D - Lunlun Number
- ABC237 D - LR insertion
第8章 アルゴリズム観点
8.1 探索
全探索
- ABC087 B - Coins
- ABC105 B - Cakes and Donuts
- ABC123 B - Five Dishes
- ABC143 B - TAKOYAKI FESTIVAL 2019
- ABC194 B - Job Assignment
- ABC224 B - Mongeness
- ABC045 C - たくさんの数式 / Many Formulas
- ABC080 C - Shopping Street
- ABC107 C - Candles
- ABC0183 C - Travel
- ABC0193 C - Unexpressed
- ABC0207 C - Many Segments
-
ABC002 D - 派閥
- 解答例
-
ABC018 D - バレンタインデー
- 解答例
-
ABC031 D - 語呂合わせ
- 解答例
-
ABC039 D - 画像処理高橋君
- 解答例
-
ABC075 D - Axis-Parallel Rectangle
- 解答例
- ARC029 A - 高橋君とお肉
- ARC036 A - ぐっすり
- ARC041 A - コインの反転
- ARC119 A - 119 × 2^23 + 1
- エイシング プログラミング コンテスト 2020 C - XYZ Triplets
深さ優先探索(DFS)
- DFS:Depth First Search
再帰関数を利用
サンプルコード
実行結果
- ATC001 A - 深さ優先探索
-
ABC054 C - One-stroke Path
- 解答例
-
ABC059 C - Sequence
- 解答例
- ABC209 D - Collision
- ABC213 D - Takahashi Tour 木のオイラーツアー(Euler Tour)
スタックを利用
サンプルコード
実行結果
- ATC001 A - 深さ優先探索
- ABC029 C - Brute-force Attack
-
ABC054 C - One-stroke Path
- 解答例
-
ABC059 C - Sequence
- 解答例
- ABC114 C - 755
-
ABC233 C - Product
- 解答例
幅優先探索(BFS)
- BFS:Breadth First Search
サンプルコード
実行結果
- ABC007 C - 幅優先探索
- ABC168 D - .. (Double Dots)
- ABC209 D - Collision
- ABC211 D - Number of Shortest paths
ビット探索
N = 3
for bit in range(1 << N):
bit_string = [0]*N
for digit in range(N):
if (bit >> digit) & 1:
bit_string[digit] = 1
else:
bit_string[digit] = 0
print(bit_string)
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]
N = 3
for bit in range(1 << N):
print(bit, end=":{")
for number in range(N):
if bit & (1 << number):
print(number, end=",")
print("}")
0:{}
1:{0,}
2:{1,}
3:{0,1,}
4:{2,}
5:{0,2,}
6:{1,2,}
7:{0,1,2,}
- ABC045 C - たくさんの数式
- ABC079 C - Train Ticket
- ABC128 C - Switches
- ABC147 C - HonestOrUnkind2
- ABC167 C - Skill Up
- ABC173 C - H and V
- ABC182 C - To 3
- ABC190 C - Bowls and Dishes
- ABC197 C - ORXOR
-
ABC0207 C - Many Segments
- 解答例
- ABC249 C - Just K
- ARC025 A - ゴールドラッシュ
二分探索
- ABC030 C - 飛行機乗り
- ABC084 C - Snuke Festival
- ABC146 C - Buy an Integer
-
ABC023 D - 射撃王
- 解答例
-
ABC026 D - 高橋君ボール1号
- 解答例
-
ABC034 D - 食塩水
- 解答例
- ABC119 D - Lazy Faith
- ABC143 D - Triangles
- ABC205 D - Kth Excluded
- ABC248 D - Range Count Query
順列探索
8.2 シミュレーション
- ABC037 B - 編集
- ABC112 B - Time Limit Exceeded
- ABC121 B - Can you solve this?
- ABC139 B - Power Socket
- ABC140 B - Buffet
- ABC184 B - Quizzes
- ABC185 B - Smartphone Addiction
- ABC228 B - Takahashi's Secret
- ABC135 C - City Savers
- ABC141 C - Attack Survival
- ABC151 C - Welcome to AtCoder
- ABC174 C - Repsept
- ABC188 C - ABC Tournament
- ABC192 C - Kaprekar Number
- ABC246 C - Coupon
- ABC225 D - Play Train
- ARC010 A - 名刺交換
- Tenka1 Programmer Beginner Contest B - Exchange
8.3 貪欲法
貪欲法(Greedy Algorithm)
- ABC053 B - A to Z String
- ABC067 B - Snake Toy
- ABC076 B - Addition and Multiplication
- ABC096 B - Maximum Sum
- ABC115 B - Christmas Eve Eve
- ABC123 B - Five Dishes
- ABC142 B - Roller Coaster
- ABC011 C - 123引き算
- ABC048 C - Boxes and Candies
- ABC176 C - Step
- ABC203 C - Friends and Travel costs
- ARC123 B - Increasing Triples
- キーエンス プログラミング コンテスト 2021 B - Mex Boxes
8.4 動的計画法(DP)
- DP:Dynamic Programming
- フィボナッチ数列
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1)+fib(n-2)
N = int(input())
print(fib(N))
n = int(input())
dp = [0]*(n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1]+dp[i-2]
print(dp[n])
- EDPC A - Frog 1
- ABC011 C - 123引き算
- ABC034 C - 経路
- ABC040 C - 柱柱柱柱柱
- ABC129 C - Typical Stairs
- ABC139 C - Lower
- ABC233 C - Product
- ABC240 C - Jumping Takahashi
- ABC245 C - Choose Elements
- ABC248 C - Dice Sum
- ABC118 D - Match Matching
- ABC122 D - We Like AGC
- ABC189 D - Logical Expression
- ABC220 D - FG operation
- ABC232 D - Weak Takahashi
- M-SOLUTIONS プロコンオープン 2020 D - Road to Millionaire
- 三井住友信託銀行プログラミングコンテスト2019 C - 100 to 105
- 天下一プログラマーコンテスト2015予選B A - 天下一プログラマーコンテスト1998
- 天下一プログラマーコンテスト2012 予選A A - 算盤の書
8.5 UnionFind
-
ABC040 D - 道路の老朽化対策について
- 解答例
-
ABC120 D - Decayed Bridges
- 解答例
-
ABC075 C - Bridge
- 解答例
-
ABC054 C - One-stroke Path
- 解答例
-
ABC015 C - 高橋くんのバグ探し
- 解答例
8.6 しゃくとり法
8.7 グラフ
- ABC021 B - 嘘つきの高橋くん
- ABC061 B - Counting Roads
- ABC225 B - Star or Not
- ABC016 C - 友達の友達
- ABC054 C - One-stroke Path
- ABC075 C - Bridge
- ABC079 C - Cat Snuke and a Voyage
- ABC166 C - Peaks
- ABC232 C - Graph Isomorphism
-
ABC012 D - バスと避けられない運命
- 解答例
-
ABC014 D - 閉路
- 解答例
-
ABC019 D - 高橋くんと木の直径
- 解答例
-
ABC035 D - トレジャーハント
- 解答例
-
ABC051 D - Candidates of No Shortest Paths
- 解答例
-
ABC061 D - Score Attack
- 解答例
-
ABC070 D - Transit Tree Path
- 解答例
-
ABC073 D - joisino's travel
- 解答例
-
ABC074 D - Restoring Road Network
- 解答例
- ARC030 A - 閉路グラフ
8.8 フロー
-
ABC010 D - 浮気予防
- 解答例
8.9 エラトステネスのふるい
8.10 ワーシャル・フロイド法
-
ABC016 C - 友達の友達
- 解答例
-
ARC109 A - Hands
- 解答例
8.11 クラスカル法/プリム法
8.12 ダイクストラ法
-
ARC109 A - Hands
- 解答例
第9章 計算量観点
加算
乗算(桁数)
剰余
ソート
つるかめ算
最大公約数(GCD)
いもす法
- ABC181 B - Trapezoid Sum
- ABC017 C - ハイスコア
- ABC035 C - オセロ
- ABC014 C - AtColor
-
ABC001 D - 感雨時刻の整理
- 解答例
- ARC124 A - LR Constraints
累積和
- 累積和:Cumulative sum
x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in range(1