はじめに
Pythonにはリスト内包表記という便利な記法があります。リスト内包表記の記法は以下のようになっています。
[ (式) for (変数名) in (イテラブルオブジェクト) ]
イテラブルオブジェクトとはlistやdictのようなイテレーションが可能なオブジェクトのことです。
変数名にはイテラブルオブジェクトの要素が1つずつ取り出され束縛されます。
式には定数や変数、x < y, i * 2といった演算の戻り値が該当します。
とても簡潔で便利なリスト内包表記ですが、実はチューリング完全であることが知られています。つまり、リスト内包表記では計算機によって原理上可能な処理をすべて行うことができるということです！
このリスト内包表記がうどんの麺のように見えることから、
- コードは1行
- コードの先頭は
[ - コードの末尾は
]
以上3つの制約を満たすコードを1本うどんコードと命名し、AtCoderの問題をリスト内包表記をひたすらに悪用した1本うどんコードで解いてみました。
0. Knapsack 1
突き出しは競技プログラミングの代表例ナップサック問題です！
[print(ks([0]*(W+1), WV, N, W)) for NW in [list(map(int, input().split()))] for N, W in zip(NW[0:1], NW[1:]) for WV in [[list(map(int, input().split())) for _ in range(0, N)]] for ks in [lambda dp,WV,N,W: dp[W] if N == 0 else ks(list(reversed([dp[w-WV[N-1][0]]+WV[N-1][1] if w-WV[N-1][0] >= 0 and dp[w-WV[N-1][0]]+WV[N-1][1] > dp[w] else dp[w] for w in range(W, -1, -1)])), WV, N-1, W)]]
え？何が書いてあるか分からない？本当に動くのか？もちろんちゃんと動きますよ。
動くのは分かったけどワケワカンナイヨーという方が大半だと思います。というか記事執筆時点で筆者にも上のコードが何をやっているのかよく分からなくなってきているので、まずは簡単な例から見ていきましょう。
1. Placing Marbles
問題文
すぬけ君は1,2,3の番号がついた3つのマスからなるマス目を持っています。 各マスには0か1が書かれており、マス$i$には$s_i$が書かれています。すぬけ君は1が書かれたマスにビー玉を置きます。ビー玉が置かれるマスがいくつあるか求めてください。
普通に書くと以下のようになります。
s = input()
print(s.count('1'))
pythonのinput()は1行を文字列として読み込むので、文字の'1'を数えてあげればよいです。
このコードを1本うどんコードに直してみましょう！
[print(input().count('1'))]
そのままですね。
鋭い方は、print()がリストの中に入っているのはヤバくないかと感じるかもしれません。しかし、pythonの関数は必ず値を返すようになっており、デフォルトの戻り値はNoneです。print()の戻り値はNoneなのでリストの要素として正しく評価されます。
2. Product
問題文
シカのAtCoDeerくんは二つの正整数$a$,$b$ を見つけました。$a$と$b$の積が偶数か奇数か判定してください。
普通に書くと以下のようになります。
a, b = map(int, input().split())
if a*b % 2 == 1: print("Odd")
else: print("Even")
map(int, input().split())の部分で入力を空白区切りで受け取って、それぞれ整数に変換しています。
素直にあまりを見て偶奇を判定してあげればよいです。
このコードを1本うどんコードに直してみましょう！
[num := list(map(int, input().split())), print("EOvdedn"[num[0]*num[1]%2::2])]
なにやら怪しい構文が２つも出てきましたね。順に解説します。
代入式(セイウチ演算子)
Python3.8から追加された機能です。左辺を変数名として右辺の値を束縛し即時評価します。
if (n := len(miroku)) > 567*(10 ** 7):
print("this list is too long! {n} elements, expected <= 100000")
代入文はn := len(miroku)の部分でlen(miroku)の値をnに束縛しています。このように代入式によってlen()を何度も呼び出すことを回避できます。
本来は1本うどんコードのような用途で代入文を使用してはいけませんが、リストの中では変数定義ができないため、代入文によって変数に値を束縛しています。
スライス
スライスはリストの一部を切り出したオブジェクトです。スライスの記法は以下のようになっています。
slice = List[start:stop:step]
Listのstart番目のインデックスからstep番目のインデックスまで、step-1個ずつ飛ばしで要素を格納したリストを得られます。
いくつか例を見てみましょう。
a = [0, 1, 2, 4, 5, 6, 7, 8, 9]
a_1 = a[0:5:1] # a_1 = [0, 1, 2, 3, 4]
a_2 = A[0:5:2] # a_2 = [0, 2, 4]
a_3 = A[0::2] # a_3 = [0, 2, 4, 6, 8]
値を省略することもでき、省略するとstart=0, stop=len(List),step=1となります。
Pythonでは文字列は文字のリストですから,
print("YNeos"[0::2]) # Yes
print("YNeos"[1::2]) # No
というスライスが得られる訳です。可読性が下がるのでスライスをこのように利用してはいけませんが、リストの中でif elseを書くよりは可読性が高いので1本うどんコードでは積極的に利用していきます。
これら2つが分かるようになると先のudon.pyが読めるようになっていると思います。
ここからはギアを上げてforを使ったリスト内包表記をしていきたいと思います！
3. Card Game for Two
問題文
$N$枚のカードがあります. $i$枚目のカードには, $a_i$という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
そのとき一番大きい数が書かれたカードを取るのが最適なので、その場合のAliceとBobの得点を求めて足せば良いです。
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
Alice = sum(A[0::2])
Bob = sum(A[1::2])
print(Alice - Bob)
早速スライスを活用しています。これは正しいスライスの使い方ですね。
それではこのコードを1本うどんコードに直して行きましょう！
[print(sum(A[0::2]) - sum(A[1::2])) for _ in [input()] for A in [sorted(list(map(int, input().split())), reverse=True)]]
一気に読みにくくなりましたね。しかし、これが今回書いた1本うどんコードの中で最も簡素なものです。
ちょっと読みやすくしてみましょう。
[
print(sum(A[0::2]) - sum(A[1::2])) # 式は最後に
for _ in [input()] # 最初の評価されるのはここの input()
for A in [sorted(list(map(int, input().split())), reverse=True)] # 2番目はここのinput()
]
インデントして少しだけ見やすくなりました。
[ (式) for (変数名) in (イテラブルオブジェクト) ]
リスト内包表記では。イテラブルオブジェクト > 変数名 > 式 の順で評価されます。
また、for文を入れ子にしたときは一番外側のforから評価されます。
最初のfor文のイテラブルオブジェクトは[input()]ですが、これは式のみのリスト内表表記とみなすことができ、先に中のinput()が評価されてから、リストとして評価されます。
これらのことが分かるとbasic.pyとudon.pyが全く同じことをしていると分かりますね。
今回はfor文を使って入力を受け取りましたが、コード長が少し長くなってしまうので基本的には代入式を使って入力を受け取ります。
イテラブルオブジェクトをリスト内包表記で生成するのは可読性を著しく損なうので止めましょう
4. Otoshidama
問題文
日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が$N$枚入っていて、合計で$Y$円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
制約
$1≤N≤2000$
$1000≤Y≤2×10^7$
$N$は整数である。
$Y$は 1000 の倍数である。
$O(N^3)$ではTLEするのでちょっと難しいですが、実は10000円札と5000円札の枚数を決めれば合計が$Y$円になるまでに1000円札が何枚必要か自然に決まるので計算量を$O(N^2)$に落とせます。
普通に書くとこのようになります。
N, Y = map(int, input().split())
a, n, s = [-1, -1, -1]
for x in range(0, N+1):
for y in range(0, N+1-x):
z = N - (x + y)
if 10000*x + 5000*y + 1000*z == Y:
a, n, s = [x, y, z]
print(a, n, s)
このコードを1本うどんコードに直してみましょう！今回ははじめからインデントしておきます。
[NY := list(map(int, input().split())), ans := [-1,-1,-1], [ans := [x, y, NY[0]-x-y] for x in range(0, NY[0]+1) for y in range(0, NY[0]+1-x) if 10000*x + 5000*y + 1000*(NY[0]-x-y) == NY[1]], print(ans[0], ans[1], ans[2])]
[
NY := list(map(int, input().split())),
ans := [-1,-1,-1],
[
ans := [x, y, NY[0]-x-y]
for x in range(0, NY[0]+1)
for y in range(0, NY[0]+1-x)
if 10000*x + 5000*y + 1000*(NY[0]-x-y) == NY[1]
],
print(ans[0], ans[1], ans[2])
]
代入式では複数の変数名に値を束縛することはできないので$N$と$Y$をまとめてリストとして受け取っています。
やっていることは同じですね。少し特殊なのがリスト内表表記内でのifの使い方です。
[ (for式) for (変数名) in (イテラブルオブジェクト) if (if式)]
リスト内表表記内ではifを使うことができます。ここでのifは制御構文としてのif文ではなく、内包表記でのみ使えるcomp_ifという構文です。comp_ifの中の(if式)がTrueになるときだけfor文の中の式(for式)が評価されます。
つまり上のudon_indent.pyではans := [x, y, NY[0]-x-y]が評価されるのはif 10000*x + 5000*y + 1000*(NY[0]-x-y) == NY[1]がTrueになるときだけ、ということになります。
今更ですが、リスト内包表記をリストを作成する以外の目的で使用するのは可読性を著しく損なうので止めましょう
5. Some Sums
問題文
$1$以上$N$以下の整数のうち、$10$進法での各桁の和が$A$以上$B$以下であるものの総和を求めてください。
実際に確かめて足せば良いです。一旦文字列にしてから、各桁を整数に戻して足します。
N, A, B = map(int, input().split())
ans = 0
for n in range(0, N+1):
s = sum(list(map(int, str(n))))
if A <= s <= B:
ans += n
print(ans)
このコードを1本うどんコードに直してみましょう！
[NAB:=list(map(int, input().split())), print(sum([n if NAB[1] <= sum(list(map(int, str(n)))) <= NAB[2] else 0 for n in range(0, NAB[0]+1)]))]
毎度のことながら見にくいのでインデントします。
[
NAB:=list(map(int, input().split())),
print(
sum(
[
n if NAB[1] <= sum(list(map(int, str(n)))) <= NAB[2] else 0
for n in range(0, NAB[0]+1)
]
)
)
]
for文の中でifが使えることから当然if elseも使うことができます。が、こちらも制御構文としてのif else文ではなく、三項演算のif elseです。ifに3つも意味を持たせるなよ。
[(Trueの場合の値) if (if式) else (Falseの場合の値) (for式) for (変数名) in (イテラブルオブジェクト) ]
if elseを使う場合は前に来ます。式なので。他に語るべきことは何もないので、何も語りません。
6. 二分探索の練習問題
問題文
長さ $N$ の整数列 $A_0,…,A_{N−1}$ が与えられます。この数列は小さい値から順番に並ぶようにソートされています。
また、整数$K$が与えられます。$A_i ≥ K$であるようなインデックス$i$のうち、最小のものを出力してください。ただし、そのような $i$ が存在しない場合は $-1$ を出力してください。
問題文に書いてあることを素直にやります。Pythonには二分探索用のライブラリがあるのでそれを利用します。
import bisect
N, K = map(int, input().split())
A = list(map(int, input().split()))
idx = bisect.bisect_left(A, K)
if idx == len(A):
idx = -1
print(idx)
このコードを1本うどんコードに直してみましょう！既に嫌な予感がしている人がいるかもしれません。正しいです。
[K := list(map(int, input().split()))[1], A:= list(map(int, input().split())), print(-1 if (idx := [bisect.bisect_left(A, K) for bisect in [__import__("bisect")]][0]) == len(A) else idx)]
moduleというつけ汁によって完成する一本うどんコードはさながら水沢うどんといったところでしょうか。
[
K := list(map(int, input().split()))[1],
A:= list(map(int, input().split())),
print(
-1 if (idx := [bisect.bisect_left(A, K) for bisect in [__import__("bisect")]][0]) == len(A)
else idx
)
]
moduleはオブジェクトなので、当然リスト内包表記内でも使えます(えぇ……)。
ついでに言うと__funcname__のように__で挟まれたメソッドはMagic Methodといって内部で使用されるメソッドです。たとえばクラスのインスタンスの作成時には__init__が呼ばれ+演算子使用時には__add__が呼ばれます。このように大体の操作に対応するMagic Methodが存在します。制御構文以外の全ての構文はMagic Method呼び出しの糖衣構文らしいです。
__init__とかはオーバーロードできないと困るのでオーバーロードができるのはまあ分かるんですが、なんで外部からMagic Methodが呼び出せるようになってるんですかね？
そういう訳で、Magic Methodを外部から呼び出すのは可読性を著しく損なうので止めましょう。
余談ですが__funcnameのように定義されるメソッドはPrivate Methodと呼ばれますが、普通に外部から呼び出せますし、CONSTのように大文字のみで定義される変数は定数として扱われますが、普通に変更可能です。 Privateや定数を名乗るな。
7. Knapsack 1
ナップザック問題、満を持しての再登場です！
問題文
$N$ 個の品物があります。品物には $1,2,…,N$ と番号が振られています。各 $i$ $(1≤i≤N)$ について、品物 $i$ の重さは $w_i$で、価値は $v_i$です。
太郎君は、$N$ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は $W$ であり、持ち帰る品物の重さの総和は $W$ 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。
制約
入力はすべて整数である。
$1≤N≤100$
$1≤W≤10^5$
$1≤w_i≤W$
$1≤v_i≤10^9$
先を見据えてin-placeにDPをします。
N ,W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(0, N):
weight, value = map(int, input().split())
for w in range(W, weight-1, -1):
if dp[w-weight] + value > dp[w]:
dp[w] = dp[w-weight] + value
print(dp[W])
このコードを1本うどんコードに直してみましょう！ところでこれ、読んでる人いるんですかね？
[print(ks([0]*(W+1), WV, N, W)) for NW in [list(map(int, input().split()))] for N, W in zip(NW[0:1], NW[1:]) for WV in [[list(map(int, input().split())) for _ in range(0, N)]] for ks in [lambda dp,WV,N,W: dp[W] if N == 0 else ks(list(reversed([dp[w-WV[N-1][0]]+WV[N-1][1] if w-WV[N-1][0] >= 0 and dp[w-WV[N-1][0]]+WV[N-1][1] > dp[w] else dp[w] for w in range(W, -1, -1)])), WV, N-1, W)]]
例によってインデントします。
[
print(ks([0]*(W+1), WV, N, W))
for NW in [list(map(int, input().split()))]
for N, W in zip(NW[0:1], NW[1:])
for WV in [[list(map(int, input().split())) for _ in range(0, N)]]
for ks in
[
lambda dp,WV,N,W:
dp[W]
if N == 0
else ks
(
list(reversed(
[
dp[w-WV[N-1][0]]+WV[N-1][1]
if w-WV[N-1][0] >= 0 and dp[w-WV[N-1][0]]+WV[N-1][1] > dp[w]
else dp[w]
for w in range(W, -1, -1)
]))
, WV, N-1, W
)
]
]
コードが長すぎてもはやどこでインデントしたらいいか分かりません。たすけて〜〜〜
このコードの圧倒的なコシ(理解不能さ)はさながら讃岐うどんといったところでしょうか。
こんなコード書いてくるやつがいたらこっちの精神が伊勢うどんにようにブチブチに切れてしまいそうです。
lambda関数はオブジェクトなのでリスト内包表記で使用することができます。できちゃだめだろ
しかもlambdaに名前をつけることができるのでlambda再帰ができます。できちゃだめだろ
セグメンテーションフォルトはifの短絡評価によって回避しています。
リスト内包表記でlambda関数を回すなんてやってはいけませんし、lambda再帰なんて言語道断です。可読性を著しく損なうので止めましょう。
8. Union Find
ラスボス、Union Findです。Union Findとは素集合を管理するデータ構造です。
問題文
この問題は、講座用問題です。ページ下部に解説が掲載されています。$N$ 頂点の、単純とは限らない無向グラフを考えます。 初期状態では、頂点のみが存在し、辺は全く存在せず、全ての頂点が孤立しているとします。以下の $2$ 種類のクエリが、$Q$ 回与えられます。
・ 連結クエリ： 頂点 $A$ と、頂点 $B$ を繋ぐ辺を追加します。
・ 判定クエリ： 頂点 $A$ と、頂点 $B$ が、連結であるかどうか判定します。連結であれば Yes、そうでなければ No を出力します。
クエリを順番に処理し、判定クエリへの回答を出力して下さい。 この際、同じ辺が何度も追加されることや、自分自身への辺が追加されることもある事に注意してください。
連結であるとは、頂点 $A$ から頂点 $B$ まで辺をたどって到達可能であることを意味します。 $A$ と $B$ が同じ頂点の場合、連結であると定義します。 グラフは無向であるため、連結クエリによって頂点 $A$,$B$ 間の辺が追加されると、$A$ から $B$ へも $B$ から $A$ へも辿れるようになります。
class UnionFind:
def __init__(self, N):
self.par = [i for i in range(0, N)]
def find(self, x):
if x != self.par[x]:
self.par[x] = self.find(self.par[x])
return self.par[x]
def unite(self, x, y):
x = self.find(x)
y = self.find(y)
self.par[y] = x
def same(self, x, y):
return self.find(self.par[x]) == self.find(self.par[y])
N, Q = map(int, input().split())
uf = UnionFind(N)
for _ in range(0, Q):
P, A, B = map(int, input().split())
if P == 0:
uf.unite(A, B)
else:
print("YNeos"[not uf.same(A, B)::2])
このコードを1本うどんコードに直してみましょう！
[NQ:=list(map(int,input().split())),[uf.unite(PAB[1],PAB[2]) if PAB[0]==0 else uf.same(PAB[1],PAB[2]) for uf in [type("UnionFind",(),{"__init__":(lambda self,N:setattr(self,"par", [i for i in range(0, N)])),"find":(lambda self,x: self.par[x] if x!=self.par[x] and self.par.__setitem__(x,self.find(self.par[x])) else self.par[x]),"unite":(lambda self,x,y: self.par.__setitem__(self.find(y),self.find(x))),"same":(lambda self,x,y:print("YNeos"[self.par[self.find(x)]!=self.par[self.find(y)]::2]))})(NQ[0])] for _ in range(0, NQ[1]) for PAB in [list(map(int, input().split()))]]]
[
NQ:=list(map(int,input().split())),
[
uf.unite(PAB[1],PAB[2]) if PAB[0]==0 else uf.same(PAB[1],PAB[2])
for uf in
[
type("UnionFind",(),
{
"__init__":(lambda self,N:setattr(self,"par", [i for i in range(0, N)])),
"find":(lambda self,x: self.par[x] if x!=self.par[x] and self.par.__setitem__(x,self.find(self.par[x])) else self.par[x]),
"unite":(lambda self,x,y: self.par.__setitem__(self.find(y),self.find(x))),
"same":(lambda self,x,y:print("YNeos"[self.par[self.find(x)]!=self.par[self.find(y)]::2]))
})(NQ[0])
]
for _ in range(0, NQ[1])
for PAB in [list(map(int, input().split()))]
]
]
type関数ではオブジェクトの型をチェックすることができます。が、type関数で新しい型を定義することもできます。関数に異なる２つの機能を持たせちゃダメだろ。type関数で新しい型を定義する場合はjson形式で関数名と関数のペアを指定します。関数はlambda関数でも良いので、よしなに定義します。
find関数では再帰で代入もしないといけないのでifの短絡評価とMagic Methodでむりやり実現しています。
本来は1本うどんコードのような用途で代入文を使用してはいけません。
イテラブルオブジェクトをリスト内包表記で生成するのは可読性を著しく損なうので止めましょう。
今更ですが、リスト内包表記をリストを作成する以外の目的で使用するのは可読性を著しく損なうので止めましょう。
Magic Methodを外部から呼び出すのは可読性を著しく損なうので止めましょう。
リスト内包表記でlambda関数を回すなんてやってはいけませんし、lambda再帰なんて言語道断です。可読性を著しく損なうので止めましょう。
ifの短絡評価を用いてif文を表現するのは止めましょう。
type関数を新しい型を定義するために使ってはいけません。
9. まとめ
いかがでしたか？ここまで耐え抜いて頂いて感謝しています。僕はもうダメです。1本うどんコードなんて二度と書きません。
追記
GitHubにコードを上げたので見たい方はこちらを見てください。
ugis70194/Python3_UDON_codes